(به : ) مسئله‌ای مشهور است که ابتدا در مسائل مربوط به آن توسط و مطرح شد و سپس در شکل عمومی آن به وسیله ریاضیدانانی مثل از و از مورد مطالعه قرار گرفت.
 شرح مسئله بدین شکل است که:
 تعداد جواب‌های شدنی مسئله، برابر است با برای n>۲ که n تعداد شهرها می‌باشد. در واقع این عدد برابر است با تعداد در یک با n رأس.
 مسئله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP)، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و است.
 سه روش کلی برای کد کردن راه حل‌های مسئله TSP ارائه شده‌است که در الگوریتم‌های مختلفی قابل استفاده هستند. راه حل‌های سه‌گانه عبارتند از:
 الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم‌های زیر قابل استفاده است:
 یا Genetic Algorithms (به اختصار GA)
شبیه‌سازی تبرید یا Simulated Annealing (به اختصار SA)
 یا Tabu Search (به اختصار TS)
جستجوی همسایگی متغیر یا Variable Neighborhood Search (به اختصار VNS)
بهینه‌سازی کلونی مورچگان یا Ant Colony Optimization (به اختصار ACO)
جستجوی یا Harmony Search (به اختصار HS)
و سایر الگوریتم‌های بهینه‌سازی گسسته
 ب) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم‌های زیر قابل استفاده است:
 یا Genetic Algorithms (به اختصار GA)
 یا Particle Swarm Optimization (به اختصار PSO)
 یا Imperialist Competitive Algorithm (به اختصار ICA)
تکامل تفاضلی یا Differential Evolution (به اختصار DE)
بهینه‌سازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization (به اختصار BBO)
استراتژی‌های تکاملی یا Evolution Strategies (به اختصار ES)
برنامه‌ریزی تکاملی یا Evolutionary Programming (به اختصار EP)
و سایر الگوریتم‌های بهینه‌سازی پیوسته
 پ) نمایش جواب به شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم‌های اشاره شده در مورد (ب) قابل استفاده می‌باشد.
 
 
 مسئله فروشنده دوره‌گرد جزء مسائل است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
 
 
 سرراست‌ترین راه حل امتحان کردن تمامی ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از مسئله می‌تواند با حل شود. راه‌های دیگر استفاده از برای ۴۰ تا ۶۰ شهر، استفاده از برای کوچکتر از ۲۰۰ شهر و استفاده از برای اندازه‌های بزرگ است.
 متنوعی وجود دارند که خیلی سریع جواب‌های درست را به‌دست می‌دهند که می‌توان آن‌ها را به صورت زیر دسته‌بندی کرد:
 
 
 این الگوریتم به‌طور مستقیم در مرتبه زمانی(!O(n حل می‌شود اما اگر به روش برنامه‌نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبه‌های نمایی است. باید توجه داشت علی‌رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه می‌باشد.
 الگوریتم فوق به صورت زیر است که در آن تعداد زیر مجموعه‌های یک مجموعه n عضوی ۲ به توان n می‌باشد و for اول یک ضریب n را نیز حاصل می‌شود که به ازای تمام شهرهای غیر مبدأ می‌باشد و حاصل
(n*(2^n را پدیدمی‌آورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب می‌شود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل می‌کند.
 
 
 مسئله:یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزن‌ها اعدادی غیر منفی هستند
 ورودی:یک گراف وزن دار و جهت دار و n تعداد گره‌های گراف. گراف با یک ارائه دو بعدی w مشخص می‌شود که سطرها و ستون‌هایش از ۱ تا n شاخص دهی شده‌اند و در ان [w[i][j معرف وزن لبه از گره iام به گره jام است.۴
 خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارائه دو بعدی p که یک تور بهینه را از روی ان می‌توان ساخت . سطرهای p از ۱ تا n و ستون‌های ان با تمامی زیر مجموعه‌های {v-{v1 شاخص دهی شده‌اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره‌های A دقیقاً یکبار می‌گذرد.
 
 
 الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قوی‌ترین الگوریتم‌ها در زمینه حل مسائل بهینه‌سازی، به خصوص مسائل بهینه‌سازی مبتنی بر گراف و مسائل بهینه‌سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند!
{"title": "مسئله فروشنده دوره‌گرد", "link": "https://fa.wikipedia.org//w/index.php?title=%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D9%81%D8%B1%D9%88%D8%B4%D9%86%D8%AF%D9%87_%D8%AF%D9%88%D8%B1%D9%87%E2%80%8C%DA%AF%D8%B1%D8%AF&oldid=34215278", "language": "fa"}