فرق تسد
نموذج فرِّق تسُد هو من نماذج الخوارزميات الشائعة ويستند في عمله على التعاود recursion.
يقسِّم نموذج فرِّق تسد المسألة إلى مسائل فرعية تشبه المسألة الأصلية، ويقدّم حلولًا للمسائل الفرعية بطريقة تعاودية، ثم يدمج حلول المسائل الفرعية وذلك لتقديم حلٍّ للمسألة الأصلية. ولمّا كان نموذج فرِّق تسد يعمل بطريقة تعاودية، فيلزم أن تكون كل مسألة فرعية أصغر من المسألة الأصلية، ويجب أن يكون هناك حالة أساس لجميع المسائل الفرعية.
يمكن تقسيم طريقة عمل هذا النموذج إلى خطوات ثلاث:
- تقسيم Divide المسألة إلى عدد من المسائل الفرعية التي تكون نسخًا أصغر من المسألة الأصلية.
- التغلب Conquer على المسائل الفرعية وذلك بحلّها بطريقة تعاودية، ويمكن حل المسائل الفرعية كحالات أساسية إن كانت صغيرة بما فيه الكفاية.
- دمج Combine حلول المسائل الفرعية لتشكيل الحل النهائي للمسألة الأصلية.
تستخدم الخوارزميات التالية منهج فرّق تسد في عملها:
- البحث الثنائي: تقارن الخوارزمية في كل خطوة العنصر المدخل
xمع قيمة العنصر الموجود في منتصف المصفوفة، وإن كانت القيمتان متطابقتين تعيد الخوارزمية موقع العنصر الموجود في منتصف المصفوفة، وإن لم تتطابق القيمتان وكانت قيمةxأقل من قيمة العنصر الموجود في منتصف المصفوفة، تعاود الخوارزمية العمل على الجانب الأيسر من العنصر المتوسط، وإن لم تتطابق القيم تنتقل إلى الجزء الأيمن من المصفوفة. - الترتيب السريع: تختار الخوارزمية عنصرًا محوريًا، وتعيد ترتيب عناصر المصفوفة بطريقة تأخذ العناصر التي تكون أصغر من العنصر المحوري الجانب الأيسر منه، والعناصر التي تكون أكبر من العنصر المحوري الجانب الأيمن. وترتب الخوارزمية في النهاية المصفوفات الفرعية بطريقة تعاودية على جانبي العنصر المحوري.
- الترتيب بالدمج: تقسّم الخوارزمية المصفوفة إلى نصفين وترتبهما تعاوديًا وتدمجمها النصفين المرتبين بعضهما ببعض.
- أقرب زوج من النقاط:
تبحث الخوارزمية عن أقرب زوج من النقاط في مجموعة من النقاط التي تنتمي إلى السطح x-y. يمكن حل المسألة بتعقيد زمني قدره O(n^2) وذلك بحساب المسافات التي تفصل بين أزواج النقاط كلها ومقارنة المسافات لمعرفة المسافة الأقصر. يمكن تقليص التعقيد الزمني إلى المقدار O(nLogn) باستخدام نموذج فرِّق تسد.
منهجية فرّق تسد مقابل البرمجة الديناميكية
تقسّم كلتا المنهجيتين فرّق تسد والبرمجة الديناميكية المسألة المعطاة إلى مسائل فرعية لتحلّها بعد ذلك. ولكن تستخدم منهجية فرّق تسد عندما لا تجري معالجة المسألة الفرعية نفسها مرات عديدة. أما في حال تكرار المسائل الفرعية فيجب حينئذ استخدام البرمجة الديناميكية لحلّها. فعلى سبيل المثال لا تجري معالجة نفس المسائل الفرعية في خوارزمية البحث الثنائي بصورة متكررة؛ لذا تنتمي هذه الخوارزمية إلى منهج فرِّق تسد، أما خوارزمية متتالية فيبوناتشي فتعالج فيها نفس المسائل الفرعية عدة مرات؛ لذا يُفضل استخدام البرمجة الديناميكية لحلّها.
مسألة إيجاد أقرب زوج من النقاط
تعثر هذه الخوارزمية على أقرب زوج من النقاط في مصفوفة تتكون من عدد معين n من النقاط في مستوى معين.
مصادر
- صفحة Divide and Conquer في توثيق الخوارزميات في موقع GeeksforGeeks.