Tatu samarqand filiali

Dinamik dasturlash

#include

using namespace std;
#define INT_MAX 999999
int n = 4;

int dist[10][10] = {

{0,20,42,25},

{20,0,30,34},

{42,30,0,10},

{25,34,10,0}

};

int VISITED_ALL = (1 << n) - 1;

int dp[16][4];

int tsp(int mask, int pos) {

if (mask == VISITED_ALL) {

return dist[pos][0];

}

if (dp[mask][pos] != -1) {

return dp[mask][pos];

}
// Endi joriy tugundan biz har bir boshqa tugunga o'tishga harakat qilamiz va minimalni olamiz

int ans = INT_MAX;
// Barcha o'rganilmagan shaharlarga tashrif buyuring va eng yaxshi marshrutni tanlang

for (int city = 0; city < n; city++) {

if ((mask & (1 << city)) == 0) {
int newAns = dist[pos][city] + tsp(mask | (1 << city), city);

ans = min(ans, newAns);

}
}
return dp[mask][pos] = ans;

}
int main() {

setlocale(LC_ALL, "ru");

/* massivni ishga tushirish dp*/

for (int i = 0; i < (1 << n); i++) {

for (int j = 0; j < n; j++) {

dp[i][j] = -1;

}

}

cout << " Sayohatchi minimal yo'li " << tsp(1, 0);
return 0;

}

Kommivoyajer masalasi Dinamik dasturlash orqali

Tarmoqli va chegaralangan usul deganda optimal yechimni topish uchun daraxtsimon tuzilishga ega bo‘lgan va baholash masalalarini yechish natijalaridan foydalanadigan masalani yechish algoritmi tushuniladi. Daraxt tuzilishi odatda shoxli daraxt deb ataladi.

CPni yechishning asosiy algoritmlaridan biri dinamik dasturlash tamoyiliga asoslanadi. Ushbu algoritmni taqdim etishda biz masalaning berilgan tipik talqiniga mos keladigan terminologiyaga amal qilamiz.

i ixtiyoriy shahar bo'lsin (i N) va V shahar 1 va shahar i bo'lmagan shaharlarning har qanday kichik to'plami bo'lsin. Har biri i shahardan boshlanib, 1-shaharda tugaydigan va faqat V to‘plam shaharlari orqali oraliq bo‘lib o‘tib, ularning har biriga bir martadan to‘liq kiruvchi yo‘llar to‘plamini M(i, V ) bilan belgilang. M(i, V ) to‘plamning eng qisqa yo‘li uzunligini B(i, V ) bilan belgilang. Yechilayotgan masala uchun B(i, V) Bellman funksiyasi hisoblanadi. Ko'rinib turibdiki, B(1, {2, 3, …, n}) - barcha shaharlardan o'tuvchi oddiy (o'z-o'zidan kesishmasdan) yopiq yo'lning istalgan minimal uzunligi.

Agar V bir elementli to'plam bo'lsa, V ={j}, bu erda j? 1 va j? i, u holda M (i, V) to'plam bitta m = (i, j, 1) yo'ldan iborat. Shunday qilib

i N, j {2, 3,…, n}, j ? i.(1.1)

Faraz qilaylik, barcha i N {1} va barcha mumkin boʻlgan k-elementlar (k < n - 1) V toʻplamlar uchun V(i, V ) funksiyaning qiymatlari allaqachon hisoblangan boʻlsin. Keyin V' N {1, i} to'plamning ixtiyoriy (k + 1) elementli to'plami bo'lgan B(i, V') qiymati formula bo'yicha hisoblanadi.

(1.2)

(1.1)-(1.12) tenglamalar Kommivoyajer masalasini echish uchun dinamik dasturlash rekursiv munosabatlar bo'lib, ular teskari Bellman usulini amalga oshirishni ta'minlaydi. Masalaning hisoblash murakkabligi , bu erda S ixtiyoriy doimiy (S > 0), n - shaharlar soni.

1.1-misol matritsa bilan aniqlangan Kommivoyajer masalasini hal qiling:

Birinchidan, (1.1) formuladan foydalanib, biz V(i, {j}) qiymatlarini aniqlaymiz:

B(2, {3}) = 5 + 6 = 11; B(3, {2}) = 2 + 2 = 4; B(4, {2}) = 5 + 2 = 7;

B(2, {4}) = 2 + 1 = 3; B(3, {4}) = 1 + 1 = 2; B(4, {3}) = 4 + 6 = 10.

Bundan tashqari, (1.2) formulaga muvofiq, biz ketma-ket ravishda olamiz (quyida yozilgan har bir tenglikning chap tomonida j parametrining qiymatlari ajratib ko'rsatilgan, bunda (1.2) ning o'ng tomonida ko'rsatilgan minimal ko'rsatilgan. hisoblash paytida amalga oshiriladi):

B(2, {3, 4}) = min[s23 + B(3,{4}); s24 + B(4,{3})] = min(5 + 2; 2 + 10)=7;

B(3, {2, 4}) = min [s32 + B(2,{ 4}); s34 + B(4,{ 2})] = min(2 + 3; 1 + 7 )=5;

B(4, {2, 3}) = min[s42 + B(2,{ 3}); s43 + B(3,{ 2})] = min(5 + 11; 4 +4)=8;

B(1, {2, 3, 4}) = min [s12 + B(2,{3,4}) s13 + B(3,{ 2,4}) s14 + B(4,{2,3} )] =

= min(4+7; 3+5; 4+8) = 8.

Demak, ushbu misoldagi mezonning optimal qiymati 8 ga teng.

Tanlangan tanlovlar sizga eng yaxshi marshrutni aniqlash imkonini beradi. Keyingisi:

1 ® 3 ® 2 ® 4 ® 1.

To'g'ridan-to'g'ri Bellman usuli amalga oshiriladigan munosabatlarni yozish uchun biz yangi belgini kiritamiz. M'(V, i) har biri 1-shahardan boshlanib, faqat V kichik to'plamdagi shaharlar orqali oraliq sifatida o'tib, ularning har biriga bir martadan to'liq kirib, i shaharda tugaydigan yo'llar to'plami bo'lsin; bu yerda, avvalgidek, i ixtiyoriy shahar (i N ), V esa N ning 1 va i shaharlarini o‘z ichiga olmagan har qanday kichik to‘plamidir. M'(V, i) to'plamning eng qisqa yo'li uzunligini B*(V, i) bilan belgilang. Ko'rinib turibdiki, V*({2, 3, …, n}, 1) barcha shaharlardan o'tuvchi oddiy (o'z-o'zidan kesishmasdan) yopiq yo'lning istalgan minimal uzunligi. Agar V bir elementli to'plam bo'lsa, V = {j}, bu erda j? 1 va j? i , keyin M'(V, i) to'plami bitta µ = (1, j, i) yo'ldan iborat. Shunday qilib

Faraz qilaylik, barcha i N va barcha mumkin bo‘lgan k-elementlar (k < n - 1) V to‘plamlar uchun V*(V, i) funksiyaning qiymatlari allaqachon hisoblangan bo‘lsin. Keyin qiymat V*(V', i), bu erda V' N {1, i} to'plamning ixtiyoriy (k + 1)-elementli to'plami, formula bo'yicha hisoblanadi.

(1.4)

(1.3)-(1.4) tenglamalar klassik Kommivoyajer masalasini hal qilish uchun dinamik dasturlash rekursiv munosabatlar bo'lib, ular to'g'ridan-to'g'ri Bellman usulini amalga oshirishni ta'minlaydi.

1.2-misol To'g'ridan-to'g'ri hisoblash usulidan foydalanib, matritsa bilan aniqlangan Kommivoyajer masalasini hal qiling:

(esda tutingki, ushbu misoldagi S matritsasi avvalgisi bilan bir xil).

Birinchidan, (1.3) formuladan foydalanib, biz V*( {j }, i) qiymatlarini aniqlaymiz:

B*({2}, 3) = 4 + 5 = 9; B*({3}, 2) = 3 + 2 = 5; B*({4}, 2) = 4 + 5 = 9;

B*({2}, 4) = 4 + 2 = 6; B*({3}, 4) = 3 + 1 = 4; B*({4}, 3) = 4 + 4 = 8.

Bundan tashqari, (1.4) formulaga muvofiq, biz ketma-ket ravishda olamiz (quyida yozilgan har bir tenglikning chap tomonida j parametrining qiymatlari ajratib ko'rsatilgan, bunda (1.4) o'ng tomonida ko'rsatilgan minimal ko'rsatilgan. hisoblash paytida amalga oshiriladi):

B*({2, 3}, 4) = min [B*({2}, 3) + s34; B*({3}, 2) + s24] = min(9 + 1; 5 + 2)= 7;

B*({2, 4}, 3) = min [B*({2}, 4) + s43; B*({4}, 2) + s23] = min(6 + 4; 9 + 5 )= 10;

B*({3, 4}, 2}) = min [B*({3}, 4) + s42; B*({4}, 3) + s32] = min(4 + 5; 8 + 2)= 9;

B*({2, 3, 4}, 1) = min [B*({2, 3}, 4) + s41; B*({2, 4}, 3) + s31; B*({3, 4}, 2) + s21;] = min (7 + 1; 10 +6; 9 + 2 ) = 8.

Demak, ushbu misoldagi mezonning optimal qiymati 8 ga teng.

Tanlangan tanlovlar sizga eng yaxshi marshrutni aniqlash imkonini beradi. Keyingisi:

1 ® 3 ® 2 ® 4 ® 1.