مسئله فروشنده دورهگرد: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Yamaha5Bot (بحث | مشارکتها) تمیزکاری با ویرایشگر خودکار فارسی |
FreshmanBot (بحث | مشارکتها) جز اصلاح فاصله مجازی + اصلاح نویسه با استفاده از AWB |
||
خط ۱۱:
مسئله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP)، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.
سه روش کلی برای کد کردن راه حلهای مسئله TSP ارائه
الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتمهای زیر قابل استفاده است:
خط ۳۹:
== الگوریتمها ==
مسئله فروشنده دورهگرد جزء مسائل [[انپی سخت]] است. راههای معمول مقابله با چنین مسائلی عبارتند از:
* طراحی الگوریتمهایی برای پیدا کردن جوابهای دقیق که استفاده از
* استفاده از [[الگوریتم مکاشفهای|الگوریتمهای مکاشفهای]] که جوابهایی بهدست میدهد که احتمالاً درست هستند.
* پیدا کردن زیرمسئلههایی از مسئله یا به عبارت دیگر تقسیم مسئله به مسئلههای کوچکتر، تا بتوان الگوریتمهای مکاشفهای بهتر و دقیقتری ارائه داد.
خط ۴۷:
=== الگوریتمهای مکاشفهای ===
[[الگوریتم تقریبی|الگوریتمهای تقریبی]] متنوعی وجود دارند که خیلی سریع جوابهای درست را با احتمال بالا بهدست میدهند که میتوان
* مکاشفهای سازنده
* بهبود تکراری
خط ۵۷:
=== پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد ===
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل میشود اما اگر به روش برنامهنویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبههای نمایی است. باید توجه داشت علیرغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل میباشد.
شبه کد الگوریتم فوق
(n*(2^n را پدیدمیآورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب میشود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل میکند.
خط ۷۵:
مسئله:یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزنها اعدادی غیر منفی هستند
ورودی:یک گراف وزن دار و جهت دار و n تعداد گرههای گراف. گراف با یک
خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک
{{چپچین}}
خط ۱۰۴:
</pre>
{{پایان چپچین}}
الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قویترین الگوریتمها در زمینه حل مسائل بهینهسازی، به خصوص مسائل بهینهسازی مبتنی بر گراف و مسائل بهینهسازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل
== جستارهای وابسته ==
|