אלגוריתם חמדן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
שימוש באלגוריתם חמדן עבור קביעת מספר המטבעות הנמוך ביותר הנדרש כדי להגיע לסכום של 36 אגורות, כאשר ערכי המטבעות הם: 20, 10, 5 ו-1.
שימוש באלגוריתם חמדן לפתרון בעיית הסוכן הנוסע.

במדעי המחשב, אלגוריתם חמדןאנגלית: Greedy Algorithm) הוא אלגוריתם המתבסס על היוריסטיקה לפיה בוחרים את האפשרות הטובה ביותר הנראית לעין בשלב הנוכחי, מבלי לקחת בחשבון את ההשפעה של צעד זה על המשך הפתרון. אלגוריתמים חמדנים נפוצים בפתרון בעיות מיטוב, בהן מנסים למצוא את הפתרון הטוב ביותר.

יעילות[עריכת קוד מקור | עריכה]

לעתים כאשר לא ניתן למצוא את הפתרון האופטימלי בזמן סביר, שימוש באלגוריתם חמדן עשוי לתת קירוב טוב לפתרון המיטבי בזמן קצר. בהתחשב בעובדה שבעיות אופטימיזציה רבות הן NP-קשות, שימוש באלגוריתמים חמדניים יכול להיות יעיל במיוחד.

במקרים מסוימים האלגוריתם החמדן הוא גם האלגוריתם האופטימלי. כלומר, סדרת בחירות חמדניות נותנת לפעמים את הפתרון האופטימלי הכללי לבעיה. למשל, האלגוריתם של פרים למציאת עץ פורש מינימלי בגרף.

בכדי להוכיח שאלגוריתם חמדן יוביל לפתרון אופטימלי משתמשים בתורת המטרואידים. ביתר פירוט, גישה חמדנית תוביל לפתרון אופטימלי אם ניתן להציג מופע של הבעיה כמטרואיד שבו קבוצת הבסיס הוא אוסף כל האיברים שמתוכם ניתן לבחור (למשל, אוסף כל הצלעות בגרף) ואוסף הקבוצות הבלתי תלויות הוא בדיוק אוסף תתי קבוצות "חוקיות" לפי הגדרת הבעיה (למשל, צלעות שאינן מכילות מעגל, בבעיית עץ פורש מינימלי). ניתן להשתמש גם בהוכחה בדרך השלילה, אם כי הוכחה כזו עשויה להיות פחות אלגנטית.

דוגמאות[עריכת קוד מקור | עריכה]

בעיית הסוכן הנוסע: סוכן מכירות רוצה לעבור במספר יישובים כדי למכור את הסחורה שלו. המטרה היא למצוא את המסלול הקצר ביותר שיעבור דרך כל היישובים. על פי שיטת האלגוריתם החמדן, הסוכן הנוסע צריך להסתכל בכל פעם במפה ולנסוע ליישוב הקרוב ביותר בו לא ביקר עדיין.

במקרה זה שיטת האלגוריתם החמדן לא תיתן בהכרח את הפתרון הטוב ביותר. כפי שניתן לראות באיור, יכול להיות מצב בו הסוכן ידלג על יישוב מסוים משום שישנו יישוב אחר קרוב יותר, כך שיאלץ לחזור ליישוב עליו דילג בסוף המסלול ולעשות דרך ארוכה יותר.

דוגמה נוספת היא קביעת מספר המטבעות הנמוך ביותר הנדרש כדי להגיע לסכום של 36 אגורות, כאשר ערכי המטבעות הם: 20, 10, 5 ו-1. על פי שיטת האלגוריתם החמדן, בכל שלב נבחר המטבע שערכו הוא הגבוה ביותר, אך עדיין נמוך משארית הסכום שעדיין לא חושבה, עד להשלמת הסכום.

בדוגמה זו, ניתן להראות כי עבור סדרת הערכים הנתונה וסדרות דומות לה, האלגוריתם החמדן הוא גם האלגוריתם האופטימלי, אך עבור סדרות ערכים אחרות אין זה כך.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]