Grafada quyidagilar mavjud

1.1-misol (qisqa yo'l muammosi). 2-rasmda ko'rsatilgan tarmoqni ko'rib chiqing. Maqsad - topish

A tugunidan H tugunigacha bo'lgan eng qisqa yo'l, bu erda yo'l uzunligi chekka raqamlar bilan ko'rsatilgan.

Keling, xarajatlarni V (i) deb belgilaymiz. Ya'ni, V (i) i tugundan to eng qisqa yo'l uzunligi

n tuguni H Masalan, V (H) = 0. c (i, j) nuqtadan i tuguniga j tuguniga o'tish xarajatlarini bildiraylik.

Masalan, c (C, E) = 7. Keyin c (i, j) + V (j) tugundan i tugunigacha bo'lgan harakat xarajatlarini anglatadi.

j va keyin j tugunidan H gacha eng qisqa yo'l bo'ylab. Bu bizga printsipni yozishga imkon beradi

optimallik tenglamasi va chegara shartlari:

Bu erda Nd

i

i tugunidan chiqadigan tugunlarni anglatadi. Masalan, Nd

C = {D, E, F}.

Ushbu tenglamalarni H tugunidan boshlab va orqaga harakat qilib, rezursiv ravishda echishimiz mumkin

quyidagicha A tugun:

V (G) = c(G, H) + V (H) = 2 + 0 = 2

V (E) = min {c(E, G) + V (G), c(E, H) + V (H)} = min {3 + 2, 4 + 0} = 4

V (F) = min {c(F, G) + V (G), c(F, H) + V (H), c(F, E) + V (E)}

= min {2 + 2, 5 + 0, 1 + 4} = 4

V (D) = min {c(D, E) + V (E), c(D, H) + V (H)} = min {5 + 4, 11 + 0} = 9

V (C) = min {c(C, F) + V (F), c(C, E) + V (E), c(C, D) + V (D)}

= min {5 + 4, 7 + 4, 1 + 9} = 9

V (B) = c(B, F) + V (F) = 6 + 4 = 10

V (A) = min {c(A, B) + V (B), c(A, C) + V (C), c(A, D) + V (D)}

= min {2 + 10, 4 + 9, 4 + 9} = 12

Shunday qilib, biz eng maqbul yo'lga keldik A → B → F → G → H.

Bellman tenglamasi

Agar siz mustahkamlashni o'rganish bilan bog'liq biron bir narsani o'qigan bo'lsangiz, biron bir joyda qo'ng'iroqchi tenglamasiga duch kelgan bo'lsangiz kerak. Bellman tenglamasi mustahkamlashni o'rganishning asosiy bloki bo'lib, RL-da har doim mavjud. Bu bizga MDP ni hal qilishga yordam beradi. Yechish eng maqbul siyosat va qiymat funktsiyalarini topishni anglatadi.

V * (S) maqbul qiymat funktsiyasi bu maksimal qiymatni beradi.

Berilgan holatning qiymati berilgan holatdagi eng maqbul harakat mukofotining eng katta harakatiga (qiymatni oshiradigan harakat) tengdir va Bellman tenglamasidan keyingi davlat qiymatiga ko'paytirilayotgan chegirma koeffitsientini qo'shadi.

Keling, ushbu tenglamani tushunamiz, V (s) ma'lum bir holatda bo'lish uchun qiymatdir. V (s) - biz a harakatini amalga oshirgandan so'ng yakunlanadigan keyingi holatdagi qiymat. R (s, a) - bu s holatida harakatni amalga oshirgandan so'ng oladigan mukofot. Turli xil harakatlar qilishimiz mumkin, shuning uchun biz maksimal darajada foydalanamiz, chunki bizning agentimiz maqbul holatda bo'lishni xohlaydi. γ yuqorida muhokama qilinganidek, chegirma koeffitsienti. Bu deterministik muhitda qo'ng'iroqning tenglamasi (1-bo'limda muhokama qilingan). Bu aniqlanmaydigan muhit yoki stoxastik muhit uchun biroz farq qiladi.