אלגוריתם חמדן
במדעי המחשב, אלגוריתם חמדן (באנגלית: Greedy Algorithm) הוא אלגוריתם המתבסס על היוריסטיקה שלפיה בוחרים את האפשרות הטובה ביותר הנראית לעין בשלב הנוכחי, מבלי לקחת בחשבון את ההשפעה של צעד זה על המשך הפתרון. אלגוריתמים חמדנים נפוצים בפתרון בעיות מיטוב, שבהן מנסים למצוא את הפתרון הטוב ביותר.
יעילות
עריכהלעיתים כאשר לא ניתן למצוא את הפתרון האופטימלי בזמן סביר, שימוש באלגוריתם חמדן עשוי לתת קירוב טוב לפתרון המיטבי בזמן קצר. בהתחשב בעובדה שבעיות אופטימיזציה רבות הן NP-קשות, שימוש באלגוריתמים חמדניים יכול להיות יעיל במיוחד.
במקרים מסוימים האלגוריתם החמדן הוא גם האלגוריתם האופטימלי. כלומר, סדרת בחירות חמדניות נותנת לפעמים את הפתרון האופטימלי הכללי לבעיה. למשל, האלגוריתם של פרים למציאת עץ פורש מינימלי בגרף.
כדי להוכיח שאלגוריתם חמדן יוביל לפתרון אופטימלי ניתן להשתמש בתורת המטרואידים. במקרים רבים של בעיות שאפשר לפתור בגישה חמדנית, ניתן להציג מופע של הבעיה כמטרואיד שבו קבוצת הבסיס הוא אוסף כל האיברים שמתוכם ניתן לבחור (למשל, אוסף כל הצלעות בגרף) ואוסף הקבוצות הבלתי תלויות הוא בדיוק אוסף תתי קבוצות "חוקיות" לפי הגדרת הבעיה (למשל, צלעות שאינן מכילות מעגל, בבעיית עץ פורש מינימלי). לא כל בעיה שאפשר לפתור בגישה חמדנית היא בהכרח מטרואיד (לדוגמה, בעיית התרמיל השלם). ניתן להשתמש גם בהוכחה בדרך השלילה או בלמת החלפה, אך שיטות הוכחה אלו נוטות להיות פחות אלגנטיות.
דוגמאות
עריכה
בעיית הסוכן הנוסע: סוכן מכירות רוצה לעבור במספר יישובים כדי למכור את הסחורה שלו. המטרה היא למצוא את המסלול הקצר ביותר שיעבור דרך כל היישובים. על פי שיטת האלגוריתם החמדן, הסוכן הנוסע צריך להסתכל בכל פעם במפה ולנסוע ליישוב הקרוב ביותר שבו לא ביקר עדיין. במקרה זה שיטת האלגוריתם החמדן לא תיתן בהכרח את הפתרון הטוב ביותר. כפי שניתן לראות באיור, יכול להיות מצב שבו הסוכן ידלג על יישוב מסוים משום שישנו יישוב אחר קרוב יותר, כך שייאלץ לחזור ליישוב שעליו דילג בסוף המסלול ולעשות דרך ארוכה יותר.
בעיית בחירת פעילויות: יש לבחור פעילויות מתוך רשימה כך שלוח הזמנים יתמלא בכמה שיותר זמן פעילות. האלגוריתם יבחר בכל פעם את הפעילות הקרובה הארוכה ביותר, ישמור את שעת הסיום שלה ויחפש את הפעילות הבאה הארוכה ביותר אשר מתחילה לאחר השעה השמורה.
בעיית תרמיל הגב: יש לבחור את מספר המטבעות הנמוך ביותר הנדרש כדי להגיע לסכום של 36 אגורות, כאשר ערכי המטבעות הם: 20, 10, 5 ו-1. על פי שיטת האלגוריתם החמדן, בכל שלב נבחר המטבע שערכו הוא הגבוה ביותר, אך עדיין נמוך (או שווה), לשארית הסכום שעדיין לא חושבה, עד להשלמת הסכום.
בדוגמה זו, ניתן להראות כי עבור סדרת הערכים הנתונה וסדרות דומות לה, האלגוריתם החמדן הוא גם האלגוריתם האופטימלי, אך עבור סדרות ערכים אחרות אין זה כך.
קוד הופמן: בקידוד לשפה בינארית, יש לבחור בכל פעם את התו בעל השכיחות הגבוהה ביותר ולהגדיר לו את הייצוג המתאים כך שייצוג של תו לא יכיל בטעות תת-תווים בתוכו.
אלגוריתם ID3: אלגוריתם חמדן שמייצר עץ החלטה מקבוצת דוגמאות נתונה.
ראו גם
עריכהקישורים חיצוניים
עריכה
- מצגת הסבר - אלגוריתם חמדן
- אלגוריתם חמדן, באתר MathWorld (באנגלית)