مسئله فروشنده دوره‌گرد: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Azita araghi (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Azita araghi (بحث | مشارکت‌ها) برچسب: افزودن فضای خالی زیاد(AF) |
||
خط ۵۳:
* بهبود تصادفی
==شبه کد مسئله فروشنده دوره گرد==
{{چپچین}}▼
مسئله:یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید.وزن ها اعدادی غیر منفی هستند
Index i, j, k;▼
ورودی:یک گراف وزن دار و جهت دار و n تعداد گره های گراف . گراف با یک ارایه دو بعدی w مشخص می شود که سطر ها و ستونهایش از 1 تا n شاخص دهی شده اند و در ان [w[i][j معرف وزن لبه از گره iام به گره jام است.4
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}];▼
خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارایه دو بعدی p که یک تور بهینه را از روی ان می توان ساخت . سطر های p از 1 تا n و ستونهای ان با تمامی زیر مجموعه های {v-{v1 شاخص دهی شده اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره های A دقیقا یکبار میگذرد.
▲{{چپچین}}
<pre>
* 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}]);
* }
▲* D[1][v-{vi}]= minimum (W[1][j]+ D[vj][V-{v1}];
▲* Minlength = D[1][V-{v1}];
* }
</pre>
الگوریتم جستجوی ممنوعه یا Tabu Search و یا به اختصار TS، یکی از قوی ترین الگوریتم ها در زمینه حل مسائل بهینه سازی، به خصوص مسائل بهینه سازی مبتنی بر گراف و مسائل بهینه سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالبا یکی از مسائلی که برای حل آنها از الگوریتم TS استفاده می شود، مسأله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسأله TSP ارائه می کند!
| |||