فرق تسد هو نمط خوارزمي. في الأساليب الخوارزمية، يتمثل التصميم في مناقشة مدخلات ضخمة، وتقسيم المدخلات إلى أجزاء صغيرة، وتحديد المشكلة على كل قطعة صغيرة، ثم دمج الحلول المتعددة التعريف في حل عالمي. تسمى آلية حل المشكلة هذه بإستراتيجية فرق تسد.
تتكون خوارزمية Divide and Conquer من نزاع باستخدام الخطوات الثلاث التالية.
على العموم يمكننا متابعة فرق تسد نهج في عملية من ثلاث خطوات.
أمثلة: تعتمد خوارزميات الكمبيوتر المحددة على نهج Divide & Conquer:
- مشكلة الحد الأقصى والحد الأدنى
- بحث ثنائي
- الفرز (دمج الفرز، الفرز السريع)
- برج هانوي.
أساسيات استراتيجية فرق تسد:
هناك نوعان أساسيان من استراتيجية فرق تسد:
- الصيغة العلائقية
- حالة التوقف
1. الصيغة العلائقية: إنها الصيغة التي نولدها من التقنية المحددة. بعد إنشاء الصيغة، نقوم بتطبيق استراتيجية D&C، أي نقوم بتفكيك المشكلة بشكل متكرر وحل المشكلات الفرعية المعطلة.
2. حالة التوقف: عندما نكسر المشكلة باستخدام استراتيجية Divide & Conquer، فإننا نحتاج إلى معرفة مقدار الوقت الذي نحتاج فيه إلى تطبيق Divide & Conquer. لذا فإن الحالة التي تكون فيها الحاجة إلى إيقاف خطوات التكرار الخاصة بالتوسيع والكحت تسمى حالة التوقف.
تطبيقات نهج فرق تسد:
تعتمد الخوارزميات التالية على مفهوم تقنية فرق تسد:
مزايا فرق تسد
- تميل لعبة فرق تسد إلى حل إحدى أكبر المشكلات بنجاح، مثل برج هانوي، وهو لغز رياضي. من الصعب حل المشكلات المعقدة التي ليس لديك فكرة أساسية عنها، ولكن بمساعدة نهج فرق تسد، فقد قلل هذا الجهد لأنه يعمل على تقسيم المشكلة الرئيسية إلى نصفين ثم حلها بشكل متكرر. هذه الخوارزمية أسرع بكثير من الخوارزميات الأخرى.
- يستخدم الذاكرة المؤقتة بكفاءة دون أن يشغل مساحة كبيرة لأنه يحل المشكلات الفرعية البسيطة داخل الذاكرة المؤقتة بدلاً من الوصول إلى الذاكرة الرئيسية الأبطأ.
- إنها أكثر كفاءة من نظيرتها في تقنية القوة الغاشمة.
- وبما أن هذه الخوارزميات تمنع التوازي، فإنها لا تنطوي على أي تعديل ويتم التعامل معها من خلال أنظمة تتضمن المعالجة المتوازية.
مساوئ فرق تسد
- نظرًا لأن معظم خوارزمياتها مصممة من خلال دمج التكرار، فإنها تتطلب إدارة عالية للذاكرة.
- مكدس صريح قد يفرط في استخدام المساحة.
- قد يؤدي ذلك إلى تعطل النظام إذا تم تنفيذ التكرار بدقة أكبر من المكدس الموجود في وحدة المعالجة المركزية.