این الگوریتم برای پیدا کردن کوتاه ترین مسیری است که یک فروشنده میتواند به نمامی شهرها سر بزند و این کار را تنها یکبار انجام دهد و بین شهرهایی سفر نماید که مسافتشان در حد نهایی مقدار کمینه باشد.
یا به عنوان دیگر : یافتن یک دور همیلتونی با کمترین وزن گرافی داده شده .
v تعداد شهرها = No. of cities
v تعداد مسیرهای ارتباطی= Number of paths
v وزن مسیرهای ارتباطی Distance of the path.
مثال :
وروودی ها:
1) بینهایت (infinity) :999 در صورتی بینهایت خواهد شد که بیش از 999 بار به جواب نرسد، میتوان این مقدار را را نیز تغغیر داد .
2) تعداد شهرها ( no. of cities: 4 ) : در اینجا به صورت پیشفرض 4 در نظر گرفته میشود.
3) تعداد مسیرها ( no. of paths:6 ) : در اینجا مسیرهای بین شهرها به صورت پیشفرض 6 در نظر گرفته میشود.
4) وروودی ها را در بدو وروود به این شکل وارد میگنیم :
نکته :
گفته بودیم که گراف 4 راس (همانند شکل بالا) و بین رئوس آن 6 مسیر وجود دارد.
S D Dist
path0:0 1 2از راس 0 به 1 با وزن 2
path0:0 2 4از راس 0 به 2 با وزن 4
path0:0 3 3از راس 0 به 3 با وزن 3
path0:1 2 3از راس 1 به 2 با وزن 3
path0:1 3 6از راس 1 به 3 با وزن 6
path0:2 3 1از راس 2 به 3 با وزن 1
نحوه پردازش
|
V(راس) |
V_N |
V_N-path |
ckt_length, ckt |
MIN_CKT_LENGTH, HAM_CKT |
|
0
|
1 |
1-2-3 |
9,0-1-2-3-0* |
9,0-1-2-3-0 |
|
2 |
2-3-1 |
13,0-2-3-1-0 |
9,0-1-2-3-0 |
|
|
3 |
3-2-1 |
9,0-3-2-1-0* |
9,0-3-2-1-0 |
|
|
1
|
0 |
0-3-2 |
9,1-0-3-2-1* |
9,1-0-3-2-1 |
|
2 |
2-3-0 |
9,1-2-3-0-1* |
9,1-2-3-0-1 |
|
|
3 |
3-2-0 |
13,1-3-2-0-1 |
9,1-2-3-0-1 |
|
|
2
|
0 |
0-1-3 |
13,2-0-1-3-2 |
9,1-2-3-0-1 |
|
1 |
1-0-3 |
9,2-1-0-3-2* |
9,2-1-0-3-2 |
|
|
3 |
3-0-1 |
9,2-3-0-1-2* |
9,2-3-0-1-2 |
|
|
3
|
0 |
0-1-2 |
9,3-0-1-2-3* |
9,3-0-1-2-3 |
|
1 |
1-0-2 |
13,3-1-0-2-3 |
9,3-0-1-2-3 |
|
|
2 |
2-1-0 |
9,3-2-1-0-3* |
9,3-2-1-0-3 |
مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem ، به‌اختصار: TSP ) 
اگر فروشنده دوره‌گرد از نقطه A شروع کند و فواصل بین نقاط مشخص باشد، کوتاه‌تربن مسیر که از تمام نقاط یکبار بازدید می‌کند و به A بازمی‌گردد کدام است؟
........
مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های 1- هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .
طرح مسئله
تعدادی شهر داریم و هزینه (مسافت) مسافرت به هر یک از آنها مشخص است به دنبال کم هزینه ترین مسیر هستیم بطوریکه از همه شهرها فقط یکبار عیور کنیم و مجددا به محل شروع بازگردیم
پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می شود اما اگر به روش برنامه نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبه های نمایی است. باید توجه داشت علی رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد .
..............
شبه کد الگوریتم فوق بصورت زیر است که در آن تعداد زیر مجموعه های یک مجموعه n عضوی 2 به توان n می باشد
و for اول یک ضریب n را نیز حاصل می شود که به ازای تمام شهرهای غیر مبدا می باشد و حاصل (n*(2^n را پدید می آورد
بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب می شود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل می کند
این مسئله ، مسئله‌ای مشهور است که ابتدا در سده 18 مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه 1930 شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه‌حل‌ها برابر است با برای n>2 که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
مسئله‌های مرتبط
مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP ) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌ از یک شهر عبور کند. این مسئله به « مسئله سیاست‌مدار مسافر» نیز شهرت دارد.
الگوریتم‌ها
مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
الگوریتم‌های دقیق
سرراست ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی میشود. با استفاده از برنامه‌نویسی پویا مسئله میتواند با مرتبه زمانی n22n حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای 40 تا 60 شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از 200 شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.
الگوریتم‌های مکاشفه‌ای
الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که میتوان آنها را به صورت زیر دسته‌بندی کرد:
مکاشفه‌ای سازنده
بهبود تکراری
مبادله دوبه‌دو
مکاشفه‌ای k-opt
مکاشفه‌ای V-opt
بهبود تصادفی
