אלגוריתמים חמדניים - למתי בחירה מקומית מובילה לאופטימום גלובלי?
מתי גישה חמדנית עובדת, מתי היא נכשלת, ודוגמאות קלאסיות כמו עץ פורש מינימלי וקידוד הופמן.
אלגוריתם חמדן (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 עובד, הוא מועדף.
שאלות נפוצות
מה זה אלגוריתם חמדני?
אלגוריתם שבונה פתרון צעד אחר צעד, ובכל צעד בוחר את האפשרות שנראית הטובה ביותר באותו רגע, בלי לחזור אחורה ובלי לשקול את ההשלכות העתידיות. הוא פשוט ומהיר, אבל נכון רק כשמבנה הבעיה מבטיח שרצף של בחירות מקומיות אופטימליות מוביל לאופטימום גלובלי.
מתי גישה חמדנית נכשלת?
כשבחירה מקומית טובה חוסמת אפשרות טובה יותר בהמשך. הדוגמה הקלאסית היא בעיית התרמיל 0/1: בחירת הפריט בעל היחס ערך-למשקל הגבוה ביותר יכולה למלא את התרמיל ולמנוע צירוף פריטים אחר שערכו גבוה יותר. במקרים כאלה נדרש תכנון דינמי, שבוחן את כל הצירופים ביעילות.
מהן דוגמאות קלאסיות לאלגוריתמים חמדניים?
אלגוריתמי קרוסקל ופרים למציאת עץ פורש מינימלי, קידוד הופמן לדחיסת נתונים, בעיית בחירת הפעילויות שבה בוחרים תמיד את הפעילות שמסתיימת מוקדם ביותר, ובעיית עודף המטבעות במערכות מטבעות קנוניות. גם דייקסטרה חמדני במהותו — הוא בוחר בכל צעד את הצומת הקרוב ביותר שטרם טופל.