ملخص

مراجعة النقاط الرئيسية

• تُستخدم خوارزميات الجشع (greedy algorithms) عادةً لحل مسائل التحسين. ويقوم مبدأها على اتخاذ قرارات مثلى محلياً في كل مرحلة من مراحل القرار، طمعاً في الحصول على حل مثلى على المستوى الشامل.
• تتخذ خوارزميات الجشع خياراً جشعاً تلو الآخر على نحو تكراري، فتحوّل المسألة في كل جولة إلى مسألة فرعية أصغر، حتى تُحل المسألة.
• لا تقتصر ميزة خوارزميات الجشع على سهولة التنفيذ، بل إن كفاءتها في حل المسائل عالية أيضاً. وبالمقارنة بالبرمجة الديناميكية، يكون التعقيد الزمني لخوارزميات الجشع عادةً أقل.
• في مسألة صرف النقود، يمكن لخوارزميات الجشع أن تضمن إيجاد الحل الأمثل في بعض تركيبات العملات؛ أما في تركيبات أخرى، فقد تجد حلولاً رديئة للغاية.
• تتمتع المسائل الصالحة للحل بخوارزميات الجشع بخاصيتين رئيسيتين: خاصية الاختيار الجشع والبنية الفرعية المثلى. وتمثل خاصية الاختيار الجشع مدى فعالية الاستراتيجية الجشعة.
• في بعض المسائل المعقدة، ليس إثبات خاصية الاختيار الجشع بالأمر البسيط. وبالمقارنة، فإن دحضها أسهل، كما في مسألة صرف النقود.
• يتكون حل مسائل الجشع أساساً من ثلاث خطوات: تحليل المسألة، وتحديد الاستراتيجية الجشعة، وإثبات الصحة. ومن بين هذه الخطوات، يُعدّ تحديد الاستراتيجية الجشعة الخطوة الجوهرية، وغالباً ما يكون إثبات الصحة هو الصعوبة الرئيسية.
• تسمح مسألة حقيبة الظهر الكسرية، انطلاقاً من مسألة حقيبة الظهر 0-1، باختيار أجزاء من العناصر، ولذلك يمكن حلها باستخدام خوارزميات الجشع. ويمكن إثبات صحة الاستراتيجية الجشعة باستخدام البرهان بالتناقض.
• يمكن حل مسألة السعة القصوى باستخدام التعداد الشامل بتعقيد زمني $O(n^2)$. ومن خلال تصميم استراتيجية جشعة تُحرّك الضلع الأقصر إلى الداخل في كل جولة، يمكن تحسين التعقيد الزمني إلى $O(n)$.
• في مسألة القطع لتعظيم الحاصل، نستنتج على التوالي استراتيجيتين جشعتين: ينبغي الاستمرار في تقسيم جميع الأعداد الصحيحة $\geq 4$، وعامل التقسيم الأمثل هو $3$. ويتضمن الكود عمليات الرفع إلى قوة، ويعتمد التعقيد الزمني على طريقة تنفيذ الرفع إلى قوة، ويكون عادةً $O(1)$ أو $O(\log n)$.