كتب greedy algorithm

أمثلة

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

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

مثال آخر هو تحديد عدد القطع النقدية الأقل المطلوب لجمع 36 قطعة نقدية، حيث أن قيم القطع النقطية هم: 1، 5، 10 و 20. وفق طريقة الخوارزيمة الجشعة، بكل مرحلة نختار القطعة النقدية ذات القيمة الأكبر، ولكن أقل من باقي القيمة المطلوبة لإكمال المجموع.

المواصفات

بشكل عام، للخوارزميات الجشعة خمسة عناصر هي:

1. مجموعة مرشحة يتم انشاء الحل منها
2. اختيار الوظيفة والتي يتم من خلالها اختيار أفضل مرشح لإضافته إلى الحل
3. الغرض من الوظيفة والتي تستخدم لتحديد ما إذا كان يمكن استخدام مرشح للمساهمة في الحل
4. الهدف من الوظيفة والتي تحدد قيمة للحل أو حل جزئي
5. وظيفة الحل والتي تحدد عندما نكتشف الحل الكامل

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

الجشع في اختيارالممتلكات

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

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

البنيه الامثل

" المشكلة المعروضة البنيه الافضل إذا كان الحل الأمثل للمشكلة يتضمن الحلول المثلى للمشاكل فرعية."

حالات الفشل

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

الانواع

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

• نقى خوارزميات الجشع
• تعامد الخوارزميات الجشعة
• • تمهل خوارزميات الجشع

التطبيقات

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

نظري matroid، ونظرية أعم من greedoids، توفر فئات كاملة من هذه الخوارزميات.

ويبدو أن الخوارزميات الجشعة تظهر في توجيه شبكة تسيير (شبكات) كذلك. باستخدام التوجيه الجشع، يتم توجيه رسالة إلى العقدة المجاورة التي هي "الأقرب" إلى الوجهة. يمكن تحديد مفهوم مكان العقدة (وبالتالي "التقارب") من خلال موقعه الفعلي، كما هو الحال في التوجيه الجغرافي geographic routing المستخدمة من قبل مخصصة الشبكات ad hoc networks. الموقع قد يكون أيضا بناء اصطناعيا كاملا كما هو الحال في توجيه العالم الصغير small world routing وجدول تجزئة توزيع distributed hash table

الامثله

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