مسئله فروشنده دورهگرد: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
جزبدون خلاصۀ ویرایش |
جز ربات ردهٔ همسنگ (۲۴) +املا+مرتب+تمیز (۴،۷): + رده:مسئلههای محاسباتی در نظریه گراف |
||
خط ۴:
شرح مسئله بدین شکل است:
:تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را میدانیم. مطلوب است کمهزینهترین مسیری که از یک شهر شروع شود و از تمامی شهرها
تعداد کل راهحلها برابر است با <math>\frac{1}{2}(n-1)!</math> برای 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 شاخص دهی
خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارایه دو بعدی p
سطر ۱۰۶ ⟵ ۱۰۵:
</pre>
{{پایان چپچین}}
الگوریتم جستجوی ممنوعه یا Tabu Search و یا به اختصار TS، یکی از قوی ترین الگوریتم ها در زمینه حل مسائل بهینه سازی، به خصوص مسائل بهینه سازی مبتنی بر گراف و مسائل بهینه سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید.
== جستارهای وابسته ==
سطر ۱۲۰ ⟵ ۱۱۹:
}}
{{چپچین}}
* Schrijver, Alexander. "On the history of combinatorial optimization (till ۱۹۶۰)," Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam,
* 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/
* [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]
سطر ۱۴۳ ⟵ ۱۴۲:
[[رده:الگوریتمهای گراف]]
[[رده:تحقیق در عملیات]]
[[رده:مسئلههای محاسباتی در نظریه گراف]]
[[رده:مشکلات انپی کامل]]
[[رده:نظریه گراف]]
|