ملخص

مراجعة النقاط الرئيسية

• التقسيم والتغلب استراتيجية شائعة في تصميم الخوارزميات تتألف من مرحلتين: التقسيم (partition) والتغلب (merge)، وتُنفَّذ عادةً بالتعاود.
• تشمل معايير الحكم على كون المسألة من مسائل التقسيم والتغلب: هل يمكن تفكيك المسألة، وهل المسائل الفرعية مستقلة، وهل يمكن دمج حلول المسائل الفرعية.
• ترتيب الدمج تطبيق نموذجي لاستراتيجية التقسيم والتغلب. فهو يقسّم المصفوفة تعاودياً إلى مصفوفتين فرعيتين متساويتين في الطول حتى لا يبقى سوى عنصر واحد، ثم يدمجهما طبقةً بعد طبقة لإتمام الترتيب.
• يمكن أن يؤدي إدخال استراتيجية التقسيم والتغلب إلى تحسين كفاءة الخوارزمية غالباً. فهي من جهة تقلل عدد العمليات، ومن جهة أخرى تسهّل تحسين التوازي من قِبل النظام.
• يستطيع التقسيم والتغلب حل كثير من مسائل الخوارزميات، كما يُستخدم على نطاق واسع في بنى البيانات وتصميم الخوارزميات، فأصبح حاضراً في كل مكان.
• مقارنةً بالبحث الشامل، يكون البحث التكيّفي أكثر كفاءة. وعادةً ما تُنفَّذ خوارزميات البحث ذات التعقيد الزمني $O(\log n)$ استناداً إلى استراتيجية التقسيم والتغلب.
• البحث الثنائي تطبيق نموذجي آخر للتقسيم والتغلب. وهو لا يتضمن خطوة دمج حلول المسائل الفرعية. ويمكننا تنفيذ البحث الثنائي عبر التقسيم والتغلب التعاودي.
• في مسألة بناء شجرة ثنائية، يمكن تقسيم بناء الشجرة (المسألة الأصلية) إلى بناء الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى (المسألتين الفرعيتين)، ويمكن تحقيق ذلك بتقسيم مجالات فهارس الاجتياز المسبق والاجتياز الوسطي.
• في مسألة أبراج هانوي، يمكن تقسيم مسألة حجمها $n$ إلى مسألتين فرعيتين حجم كل منهما $n-1$ ومسألة فرعية واحدة حجمها $1$. وبعد حل هذه المسائل الفرعية الثلاث بالترتيب، تُحل المسألة الأصلية.