موضوع مقاله: مسئله فروشنده دوره‌گرد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله فروشنده دوره‌گرد | مقدمه: مسئله فروشنده دوره‌گرد مسئله‌ای مشهور در بهینه‌سازی ترکیبیاتی است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و چوریو مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت. | ## بخش 1: مسئله فروشنده دوره‌گرد | شرح مسئله بدین شکل است که: تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاً یکبار عبور کند و به شهر شروع بازگردد. شیوه نمایش راه‌حل مسئله فروشنده دوره‌گرد، یکی از مسائل بسیار مهم و پرکاربرد در علوم رایانه و تحقیق در عملیات است. سه روش کلی برای مدل‌سازی راه حل‌های مسئلهٔ فروشنده دوره‌گرد ارائه شده است که در الگوریتم‌ها و هیوریستیک‌های مختلفی قابل استفاده هستند. راه حل‌های سه‌گانه عبارتند از: نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک تبرید شبیه‌سازی شده جستجوی ممنوعه جستجوی همسایگی متغیر بهینه‌سازی کلونی مورچه‌ها جستجوی هارمونی سایر الگوریتم‌های بهینه‌سازی گسسته نمایش جواب به صورت کلیدهای تصادفی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک بهینه‌سازی ازدحام ذرات الگوریتم رقابت استعماری تکامل تفاضلی بهینه‌سازی مبتنی بر جغرافیای زیستی استراتژی‌های تکاملی برنامه‌ریزی تکاملی سایر الگوریتم‌های بهینه‌سازی پیوسته نمایش جواب به شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم‌های اشاره شده در مورد ۱ قابل استفاده می‌باشد. مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم. مسئله تنگراه فروشنده دوره‌گرد مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد. | ## بخش 2: مسئله فروشنده دوره‌گرد | تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاً از یک شهر عبور کند. راه‌های معمول مقابله با چنین مسائلی عبارتند از: طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آن‌ها فقط برای مسائل با اندازه کوچک صورت می‌گیرد. پیدا کردن زیرمسئله‌هایی از مسئله یا به عبارت دیگر تقسیم مسئله به مسئله‌های کوچکتر، تا بتوان الگوریتم‌های جستجوی بهتر و دقیق‌تری ارائه داد. الگوریتم‌های دقیق سرراست‌ترین راه حل امتحان کردن تمامی جایگشتهای ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها است، این راه حل با بالا رفتن فضای جستجو غیرعملی می‌شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است. الگوریتم‌های مکاشفه‌ای الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آن‌ها را به صورت زیر دسته‌بندی کرد: مکاشفه‌ای سازنده بهبود تکراری مبادله دوبه‌دو مکاشفه‌ای k-opt مکاشفه‌ای V-opt بهبود تصادفی پیچیدگی محاسباتی الگوریتم فروشنده دوره‌گرد این الگوریتم به‌طور مستقیم در مرتبه زمانی حل می‌شود اما اگر به روش برنامه‌نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن خواهد شد که از مرتبه نمایی است. باید توجه داشت علی‌رغم آن‌که مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می‌باشد. | ## بخش 3: مسئله فروشنده دوره‌گرد | شبه کد الگوریتم فوق به صورت زیر است که در آن تعداد زیر مجموعه‌های یک مجموعه عضوی می‌باشد وحلقه for اول یک ضریب را نیز حاصل می‌شود که به ازای تمام شهرهای غیر مبدأ می‌باشد و حاصل را پدیدمی‌آورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه داریم که در زمان فوق نیز ضرب می‌شود و در نهایت زمان را برای این الگوریتم حاصل می‌کند. n}, J) + D J,1 شبه کد مسئله فروشنده دوره‌گرد مسئله: یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزن‌ها اعدادی غیر منفی هستند ورودی: یک گراف وزن دار و جهت دار و تعداد گره‌های گراف. گراف با یک ارائه دو بعدی مشخص می‌شود که سطرها و ستون‌هایش از تا شاخص دهی شده‌اند و در آن معرف وزن لبه از گره iام به گره jام است. سطرهای p از ۱ تا n و ستون‌های ان با تمامی زیر مجموعه‌های {v-{v1 شاخص دهی شده‌اند . غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره‌گرد یا TSP است. | ## جمع‌بندی | این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند!