مسئله فروشنده دوره‌گرد کیست؟ توضیح بده.
مسئله فروشنده دوره‌گرد مسئله‌ای مشهور در بهینه‌سازی ترکیبیاتی است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و چوریو مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.شرح مسئله بدین شکل است که:تعداد جواب‌های شدنی مسئله، برابر است با formula_1 برای n&gt;۲ که n تعداد شهرها می‌باشد. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.شیوه نمایش راه‌حل.مسئله فروشنده دوره‌گرد، یکی از مسائل بسیار مهم و پرکاربرد در علوم رایانه و تحقیق در عملیات است.سه روش کلی برای مدل‌سازی راه حل‌های مسئلهٔ فروشنده دوره‌گرد ارائه شده است که در الگوریتم‌ها و هیوریستیک‌های مختلفی قابل استفاده هستند. راه حل‌های سه‌گانه عبارتند از:الگوریتم‌ها.مسئله فروشنده دوره‌گرد جزء مسائل ان‌پی سخت است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:الگوریتم‌های دقیق.سرراست‌ترین راه حل امتحان کردن تمامی جایگشتهای ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها formula_2 است، این راه حل با بالا رفتن فضای جستجو غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی formula_3 حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.الگوریتم‌های مکاشفه‌ای.الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آن‌ها را به صورت زیر دسته‌بندی کرد:پیچیدگی محاسباتی الگوریتم فروشنده دوره‌گرد.این الگوریتم به‌طور مستقیم در مرتبه زمانی formula_4 حل می‌شود اما اگر به روش برنامه‌نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن formula_5 خواهد شد که از مرتبه نمایی است. باید توجه داشت علی‌رغم آن‌که مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می‌باشد. شبه کد الگوریتم فوق به صورت زیر است که در آن تعداد زیر مجموعه‌های یک مجموعه formula_6 عضوی formula_7 می‌باشد وحلقه for اول یک ضریب formula_6 را نیز حاصل می‌شود که به ازای تمام شهرهای غیر مبدأ می‌باشد و حاصل formula_9 را پدیدمی‌آورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه formula_6 داریم که در زمان فوق نیز ضرب می‌شود و در نهایت زمان formula_11 را برای این الگوریتم حاصل می‌کند.شبه کد مسئله فروشنده دوره‌گرد.مسئله: یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزن‌ها اعدادی غیر منفی هستندورودی: یک گراف وزن دار و جهت دار و formula_6 تعداد گره‌های گراف. گراف با یک ارائه دو بعدی formula_13 مشخص می‌شود که سطرها و ستون‌هایش از formula_14 تا formula_6 شاخص دهی شده‌اند و در آن formula_16 معرف وزن لبه از گره iام به گره jام است.خروجی: یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارائه دو بعدی p که یک تور بهینه را از روی ان می‌توان ساخت. سطرهای p از ۱ تا n و ستون‌های ان با تمامی زیر مجموعه‌های {v-{v1 شاخص دهی شده‌اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره‌های A دقیقاً یکبار می‌گذرد.الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قوی‌ترین الگوریتم‌ها در زمینه حل مسائل بهینه‌سازی، به خصوص مسائل بهینه‌سازی مبتنی بر گراف و مسائل بهینه‌سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره‌گرد یا TSP است. این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند!