الخوارزميات الجشعة

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

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

أ) اجعل فئات العملات المعدنية هي 1 و 5 و 10 و S = 27.
1) خذ 10 ، S: 27 - & GT. 17
2) خذ 10 ، S: 17 - & GT. 7
3) خذ 5 ، S: 7 - & GT. 2
4) خذ 1 ، S: 2 - & GT. 1
5) خذ 1 ، S: 1 - & GT. 0
نتيجة لذلك ، سجلوا مبلغ خمس عملات معدنية. يمكنك بشكل مستقل (على سبيل المثال ، القوة الغاشمة) التأكد من أنه مقابل 4 عملات أو أقل لن تتمكن من تسجيل 27.

ب) اجعل فئات العملات المعدنية هي 1 و 5 و 7 و S = 24.
1) خذ 7 ، S: 24 - & GT. 17
2) خذ 7 ، S: 17 - & GT. 10
3) خذ 7 ، S: 10 - & GT. 3
4) خذ 1 ، S: 3 - & GT. 2
5) خذ 1 ، S: 2 - & GT. 1
6) خذ 1 ، S: 1 - & GT. 0.
سجلنا ست قطع نقدية ، لكن يمكننا الحصول على S بأربع عملات - اثنتان بقيمة اسمية 7 واثنتان بقيمة اسمية 5.

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