خوارزمية فرق تسد

في علم الحاسوب، خوارزمية فرق تسد (بالإنجليزية: divide and conquer)‏ هي بارادايم تصميم خوارزميات مهم مبني على استدعاء ذاتي متعدد الفروع. تعمل خوارزمية فرق تسد عن طريق تقسيم المسألة بشكل عودي إلى مسألتين جزئيتين أو أكثر من نفس النوع، حتى تصبح المسائل الجزئية بسيطة بما فيه الكفاية لتحل بشكل مباشر. ومن ثم تدمج حلول المسائل الجزئية لتعطي حلاً للمسألة الجزئية.

هذا الأسلوب هو الأساس للعديد من الخوارزميات الكفئة لجميع الأنواع من المسائل، مثل الترتيب (على سبيل المثلا ترتيب دمجي، ترتيب سريع)، البحث (خوارزمية بحث ثنائي)، ضرب أعداد كبيرة، تحليل نحوي، حساب تحويل فوريي المنقطع، والمضروب.

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

عادة ما يتم برهنة صحة خوارزمية فرق تسد بالاستقراء الرياضي، ويتم تحديد كلفتها الحسابية غالبا عن طريق حل علاقات تكرارية.

أمثلة تاريخية مبكرة

البحث الثنائي، خوارزمية فرق تسد حيث تقسم فيها المسألة الأصلية على التوالي إلى مسائل جزئية بنصف حجم المسألة الأصلية تقريبا. بينما يظهر وصف واضح للخوارزمية على الحواسيب في مقال لجون ماتشلي، ترجع فكرة استخدام قائمة مرتبة من العناصر لتسهيل البحث على الأقل إلى وقت بلاد بابل في عام 200 ق.م. خوارزمية فرق تسد أخرى مع مسألة جزئية واحدة هي خوارزمية أقليدس لحساب القاسم المشترك الأكبر لعددين. والتي تعود لقرون عديدة قبل الميلاد.

خوارزمية فرق تسد بمسألتين جزئيتين مبكرة والتي طورت للحواسيب وتم تحليلها بشكل صحيح هي خوارزمية الترتيب الدمجي، والتي اخترعها جون فون نيومانفي عام 1945.

مثال آخر لخوارزمية فرق تسد والتي لم تشتمل في الأصل على الحواسيب، اعطى دونالد كانوث طريقة عادة ما يستعملها مكتب البريد لنقل البريد: يتم ترتيب الرسائل في حقائب منفردة لمناطق جغرافية مختلفة، وكل حقيبة مرتبة لدفعات لمناطق جزئية أصغر، وهكذا حتى يتم تسليمها.

ايجابيات

حل مسائل صعبة

فرق تسد هي أداة قوية لحل مسائل مفاهيمية صعبة، مثل أحجية برج هانوا التقليدية: كل ما تتطلبه الخوارزمية هو طريقة لتقسيم المسألة لمسائل جزئية، حل الحالات البسطية ودمج المسائل الجزئية للمسألة الأصلية.

كفاءة الخوارزمية

غالباً ما يساعد بارادايم فرق تسد في اكتشاف خوارزميات كفئة. كانت فرق تسد المفتاح، على سبيل المثال، لطريقة كاراتسوب للضرب، خوارزميتا الترتيب السريع والتريب الدمجي، خوارزمية ستراسين لضرب المصفوفات، وتحويل فوريي السريع. في كل الأمثلة، أدى نهج فرق تسد إلى تطوير تكلفة الحل. مثلا، إذا كان لحالات الأساس حجم ثابت محدود، تقسيم المسألة ودمج الحلول الجزئية هو نسبي لحجم المسألة n، وهنالك عدد محدود من المسائل الجزئية p بحجم ~ n/p في كل مرحلة، ولذلك تكلفة خوارزمية فرق تسد تكون (O(n log n.

حوسبة متوازية

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

الوصول للذاكرة

تميل خوارزميات فرق تسد بطبيعة الحال إلى الاستفادة المثلى من الذاكرة الخابية.

التحكم في التقريب

في الحسابات مع تقريب حسابي، على سبيل المثال مع أعداد الفاصلة العائمة، خوارزمية فرق تسد قد تسفر عن نتائج أدق من ما تعادلها ظاهرياً من الطرق التكرارية.

انظر أيضا

• استقراء رياضي
• خوارزمية بحث ثنائي
• ترتيب دمجي
• ترتيب سريع