טכניקות אלגוריתמיותבינוני6 דק' קריאה
אלגוריתמים חמדניים - למתי בחירה מקומית מובילה לאופטימום גלובלי?
מתי גישה חמדנית עובדת, מתי היא נכשלת, ודוגמאות קלאסיות כמו עץ פורש מינימלי וקידוד הופמן.
אלגוריתם חמדן (Greedy Algorithm) מקבל בכל שלב את ההחלטה שנראית הטובה ביותר ברגע נתון, מבלי לחזור ולשנות אותה. הגישה פשוטה ומהירה - אך לא תמיד מובילה לאופטימום הגלובלי.
מתי גישה חמדנית עובדת?
- Greedy Choice Property - בחירה מקומית אופטימלית שייכת לפתרון הגלובלי האופטימלי
- Optimal Substructure - אחרי בחירה, הבעיה הנותרת היא תת-בעיה זהה במבנה
דוגמה שעובדת - עודף במטבעות
לתת עודף עם המטבעות הגדולים ביותר קודם, עובד למערכות מטבעות 'נורמליות' (1, 5, 10, 50, 100). אבל למערכת לא רגילה כמו {1, 3, 4} ועודף 6 - חמדן יבחר 4+1+1=3 מטבעות, האופטימום הוא 3+3=2 מטבעות.
תמיד צריך להוכיח שגישה חמדנית מובילה לאופטימום! לא מספיק 'להרגיש' שזה עובד - בעיות רבות (Knapsack 0/1, TSP) נראות חמדניות אבל דורשות DP או backtracking.
אלגוריתמים חמדניים מפורסמים
- Dijkstra - מסלול קצר ביותר (חמדנות לפי המרחק הקטן ביותר)
- Prim ו-Kruskal - עץ פורש מינימלי
- Huffman Coding - קידוד אופטימלי לדחיסה
- Activity Selection - בחירת מקסימום פעילויות שלא חופפות
Greedy מול DP
Greedy מקבל החלטה אחת ולעולם לא חוזר בו - מהיר אבל מוגבל. DP בודק את כל האפשרויות לפני בחירה - איטי יותר אבל תמיד אופטימלי. אם Greedy עובד, הוא מועדף.