مسئله فروشنده دورهگرد
از ویکیپدیا، دانشنامه آزاد
از ویکیپدیا، دانشنامه آزاد
مسئله فروشنده دورهگرد (به انگلیسی: Travelling salesman problem، بهاختصار: TSP) مسئلهای مشهور در بهینهسازی ترکیبیاتی است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و چوریو مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است که:
تعداد جوابهای شدنی مسئله، برابر است با برای n>۲ که n تعداد شهرها میباشد. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.
مسئله فروشنده دورهگرد، یکی از مسائل بسیار مهم و پرکاربرد در علوم رایانه و تحقیق در عملیات است.
سه روش کلی برای مدلسازی راه حلهای مسئلهٔ فروشنده دورهگرد ارائه شده است که در الگوریتمها و هیوریستیکهای مختلفی قابل استفاده هستند. راه حلهای سهگانه عبارتند از:
مسئله فروشنده دورهگرد جزء مسائل انپی سخت است. راههای معمول مقابله با چنین مسائلی عبارتند از:
سرراستترین راه حل امتحان کردن تمامی جایگشتهای ممکن برای پیدا کردن ارزانترین مسیر است که چون تعداد جایگشتها است، این راه حل با بالا رفتن فضای جستجو غیرعملی میشود. با استفاده از برنامهنویسی پویا مسئله میتواند با مرتبه زمانی حل شود. راههای دیگر استفاده از الگوریتمهای انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامهنویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازههای بزرگ است.
الگوریتمهای تقریبی متنوعی وجود دارند که خیلی سریع جوابهای درست را با احتمال بالا بهدست میدهند که میتوان آنها را به صورت زیر دستهبندی کرد:
این الگوریتم بهطور مستقیم در مرتبه زمانی حل میشود اما اگر به روش برنامهنویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن خواهد شد که از مرتبه نمایی است. باید توجه داشت علیرغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل میباشد. شبه کد الگوریتم فوق به صورت زیر است که در آن تعداد زیر مجموعههای یک مجموعه عضوی میباشد وحلقه for اول یک ضریب را نیز حاصل میشود که به ازای تمام شهرهای غیر مبدأ میباشد و حاصل را پدیدمیآورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه داریم که در زمان فوق نیز ضرب میشود و در نهایت زمان را برای این الگوریتم حاصل میکند.
C({1},1) = 0 for (S=2 to n) for All Subsets S subset of {1,2,3,...} of size S and containing1 C(S,1) = & for All J member of S , J<>1 C (S , J) = min { C (S - { J } , i) + D i,J: i member of S , i <> J } return min j C ({1 . . . n}, J) + D J,1
مسئله: یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزنها اعدادی غیر منفی هستند
ورودی: یک گراف وزن دار و جهت دار و تعداد گرههای گراف. گراف با یک ارائه دو بعدی مشخص میشود که سطرها و ستونهایش از تا شاخص دهی شدهاند و در آن معرف وزن لبه از گره iام به گره jام است.
خروجی: یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارائه دو بعدی p که یک تور بهینه را از روی ان میتوان ساخت. سطرهای p از ۱ تا n و ستونهای ان با تمامی زیر مجموعههای {v-{v1 شاخص دهی شدهاند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گرههای A دقیقاً یکبار میگذرد.
* Void travel ( int n , * const number W[][], * index p[][], * number&minlength * ) * { * Index i, j, k; * number D[1..n][subset of V-{vi}]; * for (i= 2 ; i<=n;i++) * D[i][∅} = w[i][1]; * for(k=1; k<=n-2 ; k++) * for (all subsets A v-{v1} containing k vertices * for (i such that j≠1 and vi is not in A){ * D[i][A] = minimum (W[i][j]+ D[vj][A-{vj}]); * P[i][A]= value of j that gave the minimum * } * D[1][v-{vi}]= minimum (W[1][j]+ D[vj][V-{v1}]; * P[1][V-{v1}]= value of j that gave the minimum ; * Minlength = D[1][V-{v1}]; * }
الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قویترین الگوریتمها در زمینه حل مسائل بهینهسازی، به خصوص مسائل بهینهسازی مبتنی بر گراف و مسائل بهینهسازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آنها از الگوریتم TS استفاده میشود، مسئله فروشنده دورهگرد یا TSP است. این الگوریتم پاسخهای بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه میکند!
Seamless Wikipedia browsing. On steroids.