אלגוריתם חמדן – הבדלי גרסאות

דוגמה לשימוש באלגוריתם חמדן לצורך פתרון [[בעיית הסוכן הנוסע]]:

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

 

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