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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
استخدام لخوارزيمة جشعة لتحديد عدد القطع النقدية الأقل المطلوب لجمع ٣٦ قطعة نقدية، حيث أن قيم القطع النقطية هم: ١، ٥، ١٠ و ٢٠

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

أمثلة[عدل]

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

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


مثال أخر هو تحديد عدد القطع النقدية الأقل المطلوب لجمع ٣٦ قطعة نقدية، حيث أن قيم القطع النقطية هم: ١، ٥، ١٠ و ٢٠. وفق طريقة الخوارزيمة الجشعة، بكل مرحلة نختار القطعة النقدية ذات القيمة الأكبر، ولكن أقل من باقي القيمة المطلوبة لإكمال المجموع.

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

ترميز هوفمان

Midori Extension.svg هذه بذرة مقالة بحاجة للتوسيع. شارك في تحريرها.