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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

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

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

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

أمثلة تاريخية مبكرة[عدل]

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

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

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

ايجابيات[عدل]

حل مسائل صعبة[عدل]

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

كفائة الخوارزمية[عدل]

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

حوسبة متوازية[عدل]

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

الوصول للذاكرة[عدل]

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

التحكم في التقريب[عدل]

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

انظر أيضا[عدل]

مراجع[عدل]

  1. ^ أ ب دونالد كانوث, فن برمجة الحاسوب: مجلد 3, ترتيب وبحث, الإصدار الثاني (Addison-Wesley, 1998).
  2. ^ دونالد كانوث، دونالد (1998). فن برمجة الحاسوب: مجلد 3 ترتيب وبحث. صفحة 159. ISBN 0-201-89685-0.