خوارزمية جشعة
خوارزمية جشعة هي خوارزمية التي تستند على الحدس المهني الذي يتم عن طريقه اختيار الإمكانية الأفضل المرئية في المرحلة الحالية, من دون الأخذ بالحسبان تأثير هذه الخطوة على تكملة الحل. الخوارزميات الجشعة مشهورة في حل مشاكل الاستمثال، حيث يتم بواستطهن محاولة الوصول إلى الجواب الأفضل.
مسألة الرحالة التاجر: تاجر يريد أن يمر بعدد من الأحياء لبيع بضاعته. هدفه هو إيجاد المسار الأقصر الذي يمر بكل الأحياء. وفق طريقة الخوارزمية الجشعة، على التاجر أن ينظر كل مرة إلى خريطته ويسافر إلى أقرب حي لم يزره بعد.
في هذه الحالة طريقة الخوارزمية الجشعة لا تعطي بالضرورة الحل الأفضل. كما هو واضح، من الممكن أن يتجاهل التاجر حياً معيناً لأنه وجد حي آخر أقرب إليه, وأن يضطر بنهاية الأمر إلى العودة إلى هذا الحي بنهاية المسار ويسلك طريقاً أطول.
مثال آخر هو تحديد عدد القطع النقدية الأقل المطلوب لجمع 36 قطعة نقدية، حيث أن قيم القطع النقطية هم: 1، 5، 10 و 20. وفق طريقة الخوارزيمة الجشعة، بكل مرحلة نختار القطعة النقدية ذات القيمة الأكبر، ولكن أقل من باقي القيمة المطلوبة لإكمال المجموع.
بشكل عام، للخوارزميات الجشعة خمسة عناصر هي:
الخوارزمية الجشعة الجشعين تنتج حلولا جيدة لبعض المسائل الرياضية، دون غيرها. معظم المشاكل التي يطبق عليها هذه الخوارزميا لها خاصيتين:
بعد كل مرحلة، البرمجة الديناميكية تتخذ القرارات على أساس كل القرارات التي اتخذت في المرحلة السابقة، وربما تعيد النظر في مسار المرحلة السابقة للخوارزمية كطريقا للحل.
بالنسبة للعديد من المشاكل الأخرى، تفشل الخوارزميات الجشعة لإنتاج الحل الأمثل، وربما قد تنتج حلول فريدة من نوعها قد تكون أسوأ حل ممكن. ومن الأمثلة على ذلك مشكلة الرحالة التاجر رجل المبيعات المذكورة أعلاه: لكل عدد من المدن، وهناك نقل المسافات بين المدن التي أقرب جار للكشف عن مجريات الأمور لتنتج أسوأ جولة محتملة فريدة من نوعها .
ويمكن وصف الخوارزميات الجشعة بأنها "قصيرة النظر"، وأيضا "غير قابلة للاسترداد. فهي مثالية فقط للمشاكل التي قد تكون "أفضل بنية تحتية".على الرغم من هذا، لكثير من المشاكل البسيطة (مثل: إعطاء التغير)، خوارزميات الأنسب هي الخوارزميات الجشعة. ومع ذلك، فمن المهم ، أن نلاحظ أن خوارزمية الجشع ويمكن استخدام كخوارزمية لتحديد ترتيب أولويات الخيارات ضمن البحث، أو فرع وقيد (التزام ) للخوارزمية. هناك عدد قليل من اشكال مختلفة لخوارزمية الجشع:
الخوارزميات الجشعة في الغالب (ولكن ليس دائما) تفشل في العثور على الحل الأمثل على الصعيد الشامل(الاعم او العالمي)، لأنها عادة لا تعمل بشكل شامل على كافة البيانات. يمكنهم تقديم التزامات لبعض الخيارات في وقت مبكر جدا والتي تمنعهم من العثور على أفضل حل شامل في وقت لاحق. على سبيل المثال، الخوارزميات التلوين الجشع المعروفة لمشكلة التلوين لرسم البياني ولجميع المشاكل مسألة كثيرة حدود غير قطعية كاملة لا تجد دائما الحلول المثلى. ومع ذلك، فهي مفيدة لأنها سريعة التفكير، كثيرا ما توفر تقديرات تقريبية إلى ألافضل.
إذا كانت الخوارزمية الجشع تثمر لانتاج الحل الأمثل الشمول (الاعم) لفئة مشكلة معينة معطاة، فإنه يصبح عادة الأسلوب المفضل لأنه أسرع من الطرق المثلى الأخرى مثل البرمجة الديناميكية. ومن أمثلة هذه الخوارزميات الجشعة هي خوارزمية كروسكال وخوارزمية بريم لإيجاد الحد الأدنى من الأشجار minimum spanning tree التي تغطي، وخوارزمية للعثور على الأشجار هوفمان المثلى شجرة هوفمان.
نظري matroid، ونظرية أعم من greedoids، توفر فئات كاملة من هذه الخوارزميات.
ويبدو أن الخوارزميات الجشعة تظهر في توجيه شبكة تسيير (شبكات) كذلك. باستخدام التوجيه الجشع، يتم توجيه رسالة إلى العقدة المجاورة التي هي "الأقرب" إلى الوجهة. يمكن تحديد مفهوم مكان العقدة (وبالتالي "التقارب") من خلال موقعه الفعلي، كما هو الحال في التوجيه الجغرافي geographic routing المستخدمة من قبل مخصصة الشبكات ad hoc networks. الموقع قد يكون أيضا بناء اصطناعيا كاملا كما هو الحال في توجيه العالم الصغير small world routing وجدول تجزئة توزيع
distributed hash table