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

-

في نهج الخوارزمية الجشعة يتم حل المشكلة عن طريق اختيار أفضل خيار متاح في الوقت الحالي. لا داعي للقلق بشأن ما إذا كانت أفضل نتيجة حالية ستحقق النتيجة المثلى الإجمالية. حيث تحاول الخوارزميات الجشعة إيجاد حل موضعي أمثل، والذي قد يؤدي في النهاية إلى حلول محسّنة (globally optimized solutions). ومع ذلك لا توفر الخوارزميات الجشعة بشكل عام حلولاً مُحسَّنة (globally optimized solutions).

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

ومع ذلك، يمكننا تحديد ما إذا كان يمكن استخدام الخوارزمية مع أي مشكلة إذا كانت المشكلة لها الخصائص التالية:

• خاصية الاختيار الجشع Greedy Choice Property

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

•  البنية التحتية المثلى Optimal Substructure

إذا كان الحل الشامل الأمثل للمشكلة يتوافق مع الحل الأمثل لمشكلاتها الفرعية، فيمكن حل المشكلة باستخدام نهج جشع (greedy approach). هذه الخاصية تسمى البنية التحتية المثلى(optimal substructure).

مزايا هذه الخوارزمية Advantages of Greedy Approach

• أسهل في الوصف (easier to describe).
• يمكن أن تؤدي هذه الخوارزمية أداءً أفضل من الخوارزميات الأخرى (ولكن ليس في جميع الحالات).

عيوب هذه الخوارزمية Drawback of Greedy Approach

• لا تنتج الخوارزمية الجشعة دائمًا الحل الأمثل. هذا هو العيب الرئيسي للخوارزمية

مثال:

عد النقود Counting Coins

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

1, 2, 5, 10 $

وطُلب منا حساب $ 18، فسيكون تطبيق الإجراء الجشع كالتالي:

• اختر عملة واحدة بقيمة 10 دولارات (القيمة الأعلى اجباري في هذه النهج)، والعدد المتبقي هو 8
• ثم اختر عملة واحدة من فئة 5 دولار، والعدد المتبقي هو 3
• ثم حدد عملة واحدة 2 دولار ، والعدد المتبقي هو 1
• وأخيرًا، فإن اختيار قطعة نقدية واحدة من فئة 1 دولار يحل المشكلة.

النتيجة :

 18 $= 10 +5+2+1 $

لاحظ انه احتجنا إلى اختيار 4 عملات فقط لهذا العدد.

طيب الان ماذا لو قمنا بتغيير بسيط للمشكلة.

لنفرض انه لدينا عملات معدنية بالقيم 1 ، 8 ، 10 .

اذا حاولنا الحصول على القيمة 18 من العملات السابقة ستكون النتيجة:

18$ = 10 + 8 $

لكن للحصول على العدد 15، الامر مختلف حيث يجب استخدام عددًا أكبر من العملات المعدنية. 

للحصول على الرقم 15 سيكون النهج 

15$ = 10 +1 +1+1+1+1 

بذلك يكون إلاجمالي 6 عملات معدنية.

 بينما يمكن حل نفس المشكلة باستخدام 3 عملات فقط (7 + 7 + 1) وهذا النهج بالتأكيد لا يستخدم مع النهج الجشع

أمثلة

فيما يلي مجموعة من الأمثلة التي تستخدم خوارزميات النهج الجشع. 

• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Graph - Map Coloring
• Graph - Vertex Cover
• Knapsack Problem
• Job Scheduling Problem

هناك الكثير من المشاكل المماثلة التي تستخدم نهج الجشع لإيجاد الحل الأمثل.