مسئله فروشنده دوره‌گرد: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده
جزبدون خلاصۀ ویرایش
Rezabot (بحث | مشارکت‌ها)
خط ۴:
 
شرح مسئله بدین شکل است:
:تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌدقیقاًٌ یکبار عبور کند و به شهر شروع بازگردد.
 
تعداد کل راه‌حل‌ها برابر است با <math>\frac{1}{2}(n-1)!</math> برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد [[دور همیلتونی|دورهای همیلتونی]] در یک [[گراف کامل]] با n رأس.
== مسئله‌های مرتبط ==
 
خط ۱۲:
 
سه روش کلی برای کد کردن راه حل های مسأله TSP ارائه شده است که در الگوریتم های مختلفی قابل استفاده هستند. راه حل های سه گاه عبارتند از:
 
 
الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم های زیر قابل استفاده است:
سطر ۳۶ ⟵ ۳۵:
* مسئله معادل در [[نظریه گراف]] به این صورت است که یک [[گراف وزن‌دار]] کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
* [[مسئله تنگراه فروشنده دوره‌گرد]] {{انگلیسی|Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP}} مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
* تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌدقیقاًٌ از یک شهر عبور کند. این مسئله به « مسئله سیاست‌مدار مسافر» نیز شهرت دارد. ===
 
== الگوریتم‌ها ==
مسئله فروشنده دوره‌گرد جزء مسائل [[ان‌پی سخت]] است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
* طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
* استفاده از [[الگوریتم مکاشفه‌ای|الگوریتم‌های مکاشفه‌ای]] که جواب‌هایی به‌دست می‌دهد که احتمالاٌاحتمالاًٌ درست هستند.
* پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
=== الگوریتم‌های دقیق ===
سطر ۵۵ ⟵ ۵۴:
 
=== پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد ===
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می شود اما اگر به روش برنامه نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبه های نمایی است. باید توجه داشت علی رغمعلی‌رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد .
شبه کد الگوریتم فوق بصورت زیر است که در آن تعداد زیر مجموعه های یک مجموعه n عضوی 2 به توان n می باشد و for اول یک ضریب n را نیز حاصل می شود که به ازای تمام شهرهای غیر مبدا می باشد و حاصل
(n*(2^n را پدید می آورد.
سطر ۷۶ ⟵ ۷۵:
مسئله:یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید.وزن ها اعدادی غیر منفی هستند
 
ورودی:یک گراف وزن دار و جهت دار و n تعداد گره های گراف . گراف با یک ارایه دو بعدی w مشخص می شود که سطر ها و ستون هایش از 1 تا n شاخص دهی شده اندشده‌اند و در ان [w[i][j معرف وزن لبه از گره iام به گره jام است.4
 
خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارایه دو بعدی p که یک تور بهینه را از روی ان می توان ساخت . سطر های p از 1 تا n و ستونهای ان با تمامی زیر مجموعه های {v-{v1 شاخص دهی شده اندشده‌اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره های A دقیقادقیقاً یکبار میگذرد.
 
سطر ۱۰۶ ⟵ ۱۰۵:
</pre>
{{پایان چپ‌چین}}
الگوریتم جستجوی ممنوعه یا Tabu Search و یا به اختصار TS، یکی از قوی ترین الگوریتم ها در زمینه حل مسائل بهینه سازی، به خصوص مسائل بهینه سازی مبتنی بر گراف و مسائل بهینه سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباغالباً یکی از مسائلی که برای حل آنها از الگوریتم TS استفاده می شود، مسأله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسأله TSP ارائه می کند!
 
== جستارهای وابسته ==
سطر ۱۲۰ ⟵ ۱۱۹:
}}
{{چپ‌چین}}
* Schrijver, Alexander. "On the history of combinatorial optimization (till ۱۹۶۰)," Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, ۲۰۰۵,۲۰۰۵، pp. ۱-۶۸. [http://homepages.cwi.nl/~lex/files/histco.ps PS], [http://homepages.cwi.nl/~lex/files/histco.pdf PDF]
* S. Arora (۱۹۹۸). "[http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arora-tsp.pdf Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems]". Journal of ACM, ۴۵ (۱۹۹۸), pp. ۷۵۳-۷۸۲.
{{پایان چپ‌چین}}
سطر ۱۳۴ ⟵ ۱۳۳:
{{ویکی‌انبار-رده|Traveling salesman problem}}
{{چپ‌چین}}
* [http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ Gerhard Reinelt TSPLIB Databases]
* [http://www.tsp.gatech.edu/index.html Traveling Salesman Problem] at Georgia Institute of Technology
* [http://www.vias.org/simulations/simusoft_travsalm.html Solution of the Traveling Salesman Problem using a Kohonen Map]
سطر ۱۴۳ ⟵ ۱۴۲:
[[رده:الگوریتم‌های گراف]]
[[رده:تحقیق در عملیات]]
[[رده:مسئله‌های محاسباتی در نظریه گراف]]
[[رده:مشکلات ان‌پی کامل]]
[[رده:نظریه گراف]]