فرض کنید نمودار شکل زیر نقشه چهار شهر و فاصله بین آنها برحسب کیلومتر باشد.




فرض کنید یک فروشنده بخواهد از هر شهر تنها یک بار عبور کند که نقطه شروع و پایان شهر باشد. کمترین مسافتی که فروشنده می تواند همه مسیر را بپیماید، کدام است؟

حل مسئله

این مساله را می توان با نوشتن همه دورهای همیلتونی ممکن با نقطه شروع و پایان از راس و محاسبه کل مسافت پیموده شده برای هر دور حل کرد.

مسیر	مسافت (کیلومتر)
ABCDA ABDCA ACBDA ACDBA ADBCA ADCBA	30+30+25+40=125 30+35+25+50=140 50+30+35+40=155 140 155 125

بنابراین مسیر یا حداقل مسافت کل یعنی، 125 کیلومتر را به دست می دهد. حالت کلی مساله فروشنده دوره گرد شامل یافتن یک دور همیلتونی برای یک گراف دلخواه راسی با حداقل مسافت پیموده شده است، که هر یال در آن مسافت بین دو راس را نشان می دهد. یک راه برای حل مساله، حالت کلی استفاده از روش مثال بالا است. برای این منظور،همه دورهای همیلتونی را که از یک راس خاص شروع شده و به همان راس پایان می یابد می نویسیم و مسافت کل هر دور را حساب می کنیم و از میان آنها، آن دوری را انتخاب می کنیم، که مسافت کل آن حداقل است، با این حال حتی برای مقادیر متوسط این روش غیر عملی است. مثلاً برای یک گراف کامل با 30 راس تعداد دور همیلتونی مختلف با شروع و پایان از یک راس خاص وجود دارد، که باید بررسی شود. حتی اگر برای هر دور پیدا شده در محاسبه مسافت کل به یک میکروثانیه زمان احتیاج باشد، برای 30 راس تقریباً سال نیاز داریم درحال حاضر، برای حل حالت کلی مساله فروشنده دوره گرد هیچ الگوریتم شناخته شده ای وجود ندارد، تا از کارایی کافی برخوردار باشد.