אלגוריתם חמדן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
הרחבה, עריכה |
||
שורה 1:
[[קובץ:Greedy algorithm 36 cents.svg|שמאל|ממוזער|250px|
ב[[מדעי המחשב]], '''אלגוריתם חמדן''' (ב[[אנגלית]]: '''Greedy Algorithm''') הוא [[אלגוריתם]] המתבסס על [[היוריסטיקה]] בה בוחרים את האפשרות הטובה ביותר הניראית לעין בשלב הנוכחי, מבלי לקחת בחשבון את
==יעילות==
לעתים כאשר לא ניתן למצוא את הפתרון האופטימאלי בזמן סביר, שימוש באלגוריתם חמדן עשוי לתת קירוב טוב לפתרון המיטבי בזמן קצר. בהתחשב בעובדה שבעיות אופטימיזציה רבות הן [[NP-קשה|NP-קשות]], שימוש באלגוריתמים חמדניים יכול להיות יעיל במיוחד.
==בעיית הסוכן הנוסע==
[[תמונה:Greedy_algorithm.jpg|שמאל|ממוזער|250px|שימוש באלגוריתם חמדן לפתרון [[בעיית הסוכן הנוסע]]]]
דוגמה לשימוש באלגוריתם חמדן לצורך פתרון [[בעיית הסוכן הנוסע]]: סוכן מכירות רוצה לעבור במספר יישובים כדי למכור את הסחורה שלו. המטרה היא למצוא את המסלול הקצר ביותר שיעבור דרך כל היישובים.▼
▲[[קובץ:Greedy algorithm 36 cents.svg|שמאל|ממוזער|250px|שימוש באלגוריתם חמדן לקביעת מספר המטבעות הנמוך ביותר הנדרש עבור 36 אגורות, כאשר ערכי המטבעות הם: 20, 10, 5 ו-1. בכל שלב נבחר המטבע שערכו הוא הגבוה ביותר, אך עדיין נמוך מהסכום שעדיין לא חושב.]]
▲ב[[מדעי המחשב]], '''אלגוריתם חמדן''' (ב[[אנגלית]]: '''Greedy Algorithm''') הוא [[אלגוריתם]] המתבסס על [[היוריסטיקה]] בה בוחרים את האפשרות הטובה ביותר הניראית לעין, מבלי לקחת בחשבון את השלכות הבחירה לטווח רחוק. אלגוריתמים חמדנים נפוצים בפתרון בעיות [[בעיית מיטוב|מיטוב]], בהן מנסים למצוא את הפתרון הטוב ביותר. כאשר לא ניתן למצוא את הפתרון המקסימלי/מינימלי בזמן סביר (בעיות אופטימיזציה רבות הן [[NP-קשה|NP-קשות]]), [[אלגוריתם]] חמדן עשוי לתת קירוב טוב לפתרון המיטבי בזמן קצר.
על פי שיטת האלגוריתם החמדן, הסוכן הנוסע צריך להסתכל בכל פעם במפה ולנסוע ליישוב הקרוב ביותר בו לא ביקר עדיין.
▲סוכן מכירות רוצה לעבור במספר יישובים כדי למכור את הסחורה שלו. המטרה היא למצוא את המסלול הקצר ביותר שיעבור דרך כל היישובים.
==הוכחת אופטמיאליות של אלגוריתם חמדן==
▲על פי שיטת האלגוריתם החמדן, הסוכן הנוסע צריך להסתכל בכל פעם במפה ולנסוע ליישוב הקרוב ביותר בו לא ביקר עדיין. שיטה זו לא תיתן בהכרח את הפתרון הטוב ביותר. כפי שניתן לראות באיור, יכול להיות מצב בו הסוכן ידלג על יישוב מסוים משום שישנו יישוב אחר קרוב יותר, כך שיאלץ לחזור ליישוב עליו דילג בסוף המסלול ולעשות דרך ארוכה יותר.
{{להשלים}}
כדי להוכיח שאלגוריתם חמדן כלשהו יתן את הפתרון האופטימאלי הכללי משתמשים בדרך כלל ב[[הוכחה בדרך השלילה]].
==ראו גם==
▲לפעמים האלגוריתם החמדן הוא גם האלגוריתם האופטימלי. למשל, [[האלגוריתם של פרים]] למציאת [[עץ פורש מינימלי]] בגרף.
* [[קוד הופמן]]
{{קצרמר|מחשבים}}
| |||