تحسين التقسيم

في تصميم الخوارزميات ، يُعدّ تحسين التقسيم أسلوبًا لتمثيل تقسيم مجموعة ما كبنية بيانات تسمح بتحسين هذا التقسيم عن طريق تقسيم مجموعاته إلى عدد أكبر من المجموعات الأصغر. وبهذا المعنى، فهو يُشابه بنية بيانات الاتحاد والبحث ، التي تُحافظ أيضًا على التقسيم إلى مجموعات منفصلة، ​​ولكن عملياتها تدمج أزواجًا من المجموعات. في بعض تطبيقات تحسين التقسيم، مثل البحث المعجمي بالعرض أولًا ، تُحافظ بنية البيانات أيضًا على ترتيب المجموعات في التقسيم.

يُعدّ تحسين التقسيم عنصرًا أساسيًا في العديد من الخوارزميات الفعّالة على الرسوم البيانية والآلات المحدودة ، بما في ذلك تصغير DFA ، وخوارزمية كوفمان-غراهام للجدولة المتوازية، والبحث المعجمي بالعرض أولًا في الرسوم البيانية. ^{[ 1 ] [ 2 ] [ 3 ]}

تحافظ خوارزمية تحسين التقسيم على مجموعة من المجموعات المنفصلة Si _. في بداية الخوارزمية، تحتوي هذه المجموعة على مجموعة واحدة تضم جميع عناصر بنية البيانات. في كل خطوة من خطوات الخوارزمية، تُقدَّم مجموعة _X للخوارزمية ، ويتم تقسيم كل مجموعة Si في المجموعة التي تحتوي على عناصر من X إلى مجموعتين : التقاطع Si ∩ X والفرق Si _{\ X.}

يمكن تنفيذ مثل هذه الخوارزمية بكفاءة من خلال الحفاظ على هياكل البيانات التي تمثل المعلومات التالية: ^{[ 4 ] [ 5 ]}

• التسلسل المرتب للمجموعات S _i في العائلة، في شكل مثل القائمة المرتبطة ثنائياً التي تسمح بإدخال مجموعات جديدة في منتصف التسلسل
• يرتبط بكل مجموعة S _i مجموعة من عناصرها ، على شكل قائمة مرتبطة ثنائياً أو مصفوفة ، مما يسمح بحذف العناصر الفردية من المجموعة بسرعة. بدلاً من ذلك، يمكن تمثيل هذا المكون من بنية البيانات بتخزين جميع عناصر جميع المجموعات في مصفوفة _واحدة ، مرتبة حسب المجموعة التي تنتمي إليها، وتمثيل مجموعة العناصر في أي مجموعة S _i بموقعَي بدايتها ونهايتها في هذه المصفوفة.
• يرتبط بكل عنصر المجموعة التي ينتمي إليها.

لإجراء عملية تحسين، يمرّ الخوارزمية على عناصر المجموعة المعطاة X. لكل عنصر x ، يجد الخوارزمية المجموعة Si التي تحتوي على x، ويتحقق مما إذا كانت قد بدأت مجموعة ثانية لـ Si ∩ X. إذا _لم تكن قد بدأت، فإنه يُنشئ المجموعة الثانية ويضيف Si _إلى قائمة _L للمجموعات التي تم تقسيمها بواسطة العملية. بعد ذلك، وبغض النظر عما إذا تم تكوين مجموعة جديدة أم لا، يزيل الخوارزمية _x من Si ويضيفه إلى Si ∩ X. _في التمثيل الذي تُخزّن فيه جميع العناصر في مصفوفة واحدة، يمكن نقل x من مجموعة إلى أخرى عن طريق تبديل x مع العنصر الأخير من Si _، ثم إنقاص فهرس نهاية Si _وفهرس بداية المجموعة الجديدة. أخيرًا، بعد معالجة جميع عناصر X بهذه الطريقة، يمرّ الخوارزمية على L ، ويفصل كل مجموعة حالية Si عن المجموعة الثانية التي تم تقسيمها منها، ويُبلغ عن كلتا المجموعتين على أنهما قد تم تكوينهما حديثًا بواسطة عملية التحسين _.

يستغرق تنفيذ عملية تحسين واحدة بهذه الطريقة زمنًا قدره O ( | X | ) ، وهو زمن مستقل عن عدد العناصر في مجموعة البيانات ، وكذلك مستقل عن العدد الإجمالي للمجموعات في بنية البيانات. وبالتالي، فإن زمن تنفيذ سلسلة من عمليات التحسين يتناسب طرديًا مع الحجم الإجمالي للمجموعات المُعطاة للخوارزمية في كل خطوة من خطوات التحسين.

كان أحد التطبيقات المبكرة لتحسين التقسيم في خوارزمية هوبكروفت (1971) لتقليل عدد حالات الأوتوماتون الحتمي المحدود . في هذه المسألة، يُعطى مُدخل أوتوماتون حتمي محدود ، ويجب إيجاد أوتوماتون مكافئ له بأقل عدد ممكن من الحالات. تحافظ خوارزمية هوبكروفت على تقسيم حالات الأوتوماتون المُدخل إلى مجموعات فرعية، بحيث تُقابل أي حالتين في مجموعتين فرعيتين مختلفتين حالتين مختلفتين في الأوتوماتون الناتج. في البداية، توجد مجموعتان فرعيتان، إحداهما تحتوي على جميع حالات القبول للأوتوماتون، والأخرى تحتوي على الحالات المتبقية. في كل خطوة، تُختار إحدى المجموعتين الفرعيتين _Si وأحد رموز الإدخال x للأوتوماتون، ويتم تحسين مجموعات الحالات الفرعية إلى حالات يؤدي فيها الانتقال المُسمى x إلى Si _، وحالات يؤدي فيها الانتقال x إلى حالة أخرى. عندما يتم تقسيم مجموعة S _i تم اختيارها مسبقًا عن طريق التحسين، لا يلزم سوى اختيار واحدة من المجموعتين الناتجتين (الأصغر بينهما)؛ وبهذه الطريقة، تشارك كل حالة في المجموعات X لمدة O ( s log n ) خطوة تحسين، وتستغرق الخوارزمية الإجمالية وقتًا قدره O ( ns log n ) ، حيث n هو عدد الحالات الأولية و s هو حجم الأبجدية. ^{[ 6 ]}

طبّق سيثي (1976) تقنية تحسين التقسيم في تطبيق فعّال لخوارزمية كوفمان-غراهام للجدولة المتوازية. بيّن سيثي إمكانية استخدام هذه التقنية لإنشاء ترتيب طوبولوجي معجمي لرسم بياني موجه غير دوري مُعطى في زمن خطي؛ ويُعدّ هذا الترتيب الطوبولوجي المعجمي إحدى الخطوات الرئيسية في خوارزمية كوفمان-غراهام. في هذا التطبيق، تُمثّل عناصر المجموعات المنفصلة رؤوس الرسم البياني المُدخل، بينما تُمثّل المجموعات X المُستخدمة لتحسين التقسيم مجموعات جيران الرؤوس. وبما أن العدد الإجمالي لجيران جميع الرؤوس هو نفسه عدد حواف الرسم البياني، فإن الخوارزمية تستغرق زمنًا خطيًا بالنسبة لعدد الحواف، أي حجم المُدخل. ^{[ 7 ]}

يُعدّ تحسين التقسيم خطوةً أساسيةً في البحث المعجمي بالعرض أولاً ، وهو خوارزمية بحث في الرسوم البيانية تُستخدم في التعرّف على الرسوم البيانية الوترية والعديد من فئات الرسوم البيانية المهمة الأخرى. وكما ذُكر سابقاً، فإنّ عناصر المجموعة المنفصلة هي رؤوس، والمجموعة X تُمثّل مجموعات الجيران ، لذا فإنّ الخوارزمية تستغرق وقتاً خطياً. ^{[ 8 ] [ 9 ]}