خوارزمية فرق تسد Divide and Conquer Algorithm

-

خوارزمية فرق تسد Divide and Conquer Algorithm هي استراتيجية لحل مشكلة كبيرة من خلال تقسيم المشكلة إلى مشاكل فرعية أصغر وحل المشكلات الفرعية بشكل مستقل والجمع بينها للحصول على المخرجات المرغوبة.

عندما نستمر في تقسيم المشاكل الفرعية إلى مشاكل فرعية أصغر، فقد نصل في النهاية إلى مرحلة لا يمكن فيها الانقسام. تسمى هذه المرحلة الأخيرة التي لا يمكن تقسيمها ب المشكلة الذرية (atomic). يتم حل هذه المشكلة الفرعية "الذرية" الأصغر (الكسور). يتم أخيرًا دمج حل جميع المشكلات الفرعية من أجل الحصول على حل للمشكلة الأصلية.

كيف تعمل خوارزميات فرق تسد How Divide and Conquer Algorithms Work؟

لا بد من تطبيق مجموعة من الخطوات لعمل هذه الخوارزمية وهذه الخطوات هي:

• التقسّيم(Divide): قسّم المشكلة المحددة إلى مشاكل فرعية باستخدام التكرار (recursion).
• السيطرة او التغلب على المشكلات(Conquer): حل المشاكل الفرعية الأصغر بشكل متكرر. إذا كانت المشكلة الفرعية صغيرة بما يكفي، فقم بحلها مباشرةً.
• الجمع او الدمج (Combine): اجمع او أدمج بين حلول المشكلات الفرعية التي تعد جزءًا من العملية التكرارية لحل المشكلة الفعلية.

مثال.

المطلوب في هذا المثال إعادة ترتيب الأرقام في المصفوفة باستخدام خوارزمية Divide and Conquer