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

الخوارزمية الجشعة (greedy) فئة من الخوارزميات البنائية تتخذ في كل خطوة القرار الذي يبدو أمثل محلياً ولا تتراجع أبداً. تعود جذورها إلى أعمال تجميعية كلاسيكية (Kruskal 1956 وPrim 1957 للشجرة الممتدة الدنيا؛ Dijkstra 1959 لأقصر مسار). متى يعطي النهج الجشع الأمثل العام تحدده نظرية المتروييد: مبرهنة Rado-Edmonds (Edmonds 1971) تفيد بأن نظام مجموعات فرعية يُحل بأمثلية بالخوارزمية الجشعة لكل دوال الوزن إذا وفقط إذا كان متروييداً. ولذلك تحل الشجرة الممتدة الدنيا (Kruskal/Prim)، وترميز Huffman (Huffman 1952)، وزمن الإكمال الموزون على آلة واحدة (قواعد SPT/EDD، Smith 1956) جشعياً بأمثلية. في المقابل، حقيبة الظهر، bin packing، set covering وVRP لها حلول جشعة بمعامل تقريب معروف فقط (مثل Chvátal 1979 ln(n)+1 لـ set covering) وليست عامة الأمثلية. عملياً تؤدي الخوارزميات الجشعة ثلاثة أدوار: (1) إرشادية بنائية سريعة (warm-start)، (2) عائلة خوارزميات تقريب بضمان، (3) حل ابتدائي للبحث المحلي أو الميتا-إرشاديات. إرشادياً، TSP الجشع (أقرب جار)، طريقة savings لـ Clarke-Wright (1964) لـ VRP، وعائلة LPT/SPT في الجدولة أمثلة قياسية صناعياً. Cormen وLeiserson وRivest وStein (CLRS، 2009) الفصل 16 هو المرجع التحليلي.