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

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

ما هي الخوارزميات الجشعة Greedy algorithms؟

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

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

كيف تقرر الخوارزمية أي خيار هو الأمثل؟

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

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

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

• من السهل جدًا التوصل إلى خوارزمية جشعة (أو حتى عدة خوارزميات جشعة) لمشكلة ما.

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

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

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