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