شرح خوارزمية Greedy Algorithms

الخوارزمية الجشعة هي الخوارزمية التي تبني الحل خطوة خطوة أو قطعة قطعة وتعتمد على اختيار الخيار الأمثل (يعظم الربح) عند كل نقطة اختيار, أي أنها تخلق خيار مثالي محلي على أمل أن هذا السلوك سيقودنا الى حل مثالي شامل (أي حل مثالي لكامل المسألة).
كما أنه لا يمكننا اثبات صحة حل مسألة تعتمد على الخوارزمية الجشعة ولكن يكفي إعطاء مثال لإثبات أن الخوارزمية خاطئة. لنأخذ المثال التالي ولنحاول حلها بطريقة الخوارزمية الجشعة:
لنفرض لدينا قاعة وعدد من المقررات التي نريد اعطاء محاضرة منها في هذه القاعة مع توقيت بداية و نهاية كل من هذه المحاضرات والمطلوب ما هو أكبر عدد من الأنشطة او المحاضرات التي نستيطع القيام بها في هذه القاعة؟
تذكر أن يكفي إعطاء مثال لاثبات ان الخوارزمية خاطئة.
1_سنحاول حل هذه المسألة بختيار الأنشطة ذات الامتداد الزمني(توقيت النهاية-توقيت البداية) الأقصر,ولكن هذه الفكرة خاطئة ويمكن اعطاء هذا المثال لاثبات ذلك: النشاط الاول من 8 الى 11. النشاط الثاني من 10:30 الى 12. النشاط الثالث من 11:30 الى 3. بناءان على الفكرة السابقة سيتم اختيار النشاط الثاني فقط بينما من الأفضل اختيار النشاطين الأول و الثالث.
2_سنحاول هذه المرة باختيار الأنشطة ذات الزمن البداية الأصغر,ولكن هذه الفكرة خاطئة ايضا ويمكن اعطاء هذا المثال لأثبات ذلك:
النشاط الأول من 8 الى 1. النشاط الثاني من 9 الى  10. النشاط الثالث من 10 الى 11. النشاط الرابع  من 11:30 الى  12:30
بناءان على الفكرة السابقة سيتم اختيار النشاط الأول فقط بينما من الأفضل اختيار النشاط الثاني و الثالث و الرابع. إذاً ما هي فكرة حل هذه المسألة؟
يتم حل هذه المسألة بأخذ الأحداث التي تنتهي أولا مع مراعاة عدم تداخل تواقيتها، أي أقوم بترتيب الأنشطة حسب زمن انتهائها (من النشاط الذي ينتهي أولا الى النشاط الذي ينتهي اخيرا) ثم أقوم بأخذ النشاط الذي ينتهي أولا و من ثم أبحث عن اول نشاط يبدأ بعد انتهائه(كي لا يحدث تداخل في تواقيت الأنشطة) ومن ثم أبحث عن أول نشاط يبدأ بعد انتهاء أخر نشاط أخذناه وهكذا...
ويكون pseudocode الخاص بالمسألة كالتالي:

input: n activities
output:  a max size subset of compatible activities
sort activities by increasing finish time A1,A2,A3 where F1<F2<F3<..<Fn
E<-{1}
T<-F1
for i=2 to n do
{
  if(Si>=T)then
    {
     add i to E
     T<-Fi
    }
}
output E

يجدر الإشارة أن الـ Greedy Algorithms أو الخوارزميات الجشعة ليست خوارزمية Algorithm و إنما هي أسلوب خوارزميات Algorithm Paradigm وهو الشكل العام لتصميم الخوارزمية و منطقها دون التوغل في تفاصيلها . 

و أصل التسمية نفسه يعود إلى أسلوبها , فهي الأسلوب الذي يفرض أن تجد حلول مثلى محلية localized optimum solution, والتي من الممكن فيما بعد أن تتحول الى حلول مثلى عامة globally optimized solutions. و لذلك سميت بالخوارزميات الجشعة, لأنها تختار الحلول المحلية المثلى , أي أنها تؤمن حلا للخطوة الحالية من الخوارزمية من دون الأخذ بالحسبان تأثير هذه الخطوة على تكملة الحل , فهي جشعة لا تنتظر أو تؤمن حلولا مثلى عامة . 

و يستعمل لشرحها عادة مسألة الرحالة التاجر الذي يريد أن يمر بعدد من الأحياء لبيع بضاعته.

هدف هذا التاجر هو إيجاد المسار الأقصر الذي يمر بكل الأحياء , فيستهدف بذلك كل القرية أو المدينة .

وفق طريقة الخوارزمية الجشعة، على التاجر أن ينظر كل مرة إلى خريطته ويسافر إلى أقرب حي لم يزره بعد . أي أن الهدف هنا هو الحل الأمثل المحلي و الخاص بالخطوة الحالية أي الـ localized optimum solution , و ذلك بغض النظر عن تأثير هاته الخطوة على تكملة الحل , فبتطبيق منطق الخوارزميات الجشعة لن نهتم إن كان التاجر سيضطر في نهاية الأمر إلى العودة إلى هذا الحي بنهاية المسار ويسلك طريقاً أطول . أي أننا لا نهتم بالدرجة الأولى بتوفير حلول مثلى عامة globally optimized solutions. 

يمكنك القراءة عن الكثير من الخوارزميات و المسائل التي تقوم بإستعمال هذا النهج من مثل : 

• مسألة عد العملات counting coins . 

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

و قد تحتاج أيضا التعرف أكثر الفرق بين الخوارزمية Algorithm و أسلوب الخوارزميات Algorithm Paradigm.