3
nuqtasidan 9-nuqtagacha bo’lgan minimal yo’l shu bosqichning qaysi nuqtasida
ekanligimizga bog'liq bo'ladi. N-bosqichga tegishli bo'lgan
n-elementning raqami
tizimning n-bosqich holat o'zgaruvchisi bo'ladi. Optimallashtirish odatda jarayon
oxiridan boshlanadi, chunki n-bosqichning ba'zi nuqtalarida bo'lganligi sababli (n -
1) - bosqichning nuqtalaridan biriga o'tish to'g'risida
qaror qabul qilinadi va
keyingi harakat yo'nalishi oldingi bosqichlardan ma'lum bo’ladi. (N - 1)
bosqichning j raqami n bosqichda boshqarish o'zgaruvchisi bo'ladi.
Birinchi bosqich (n = 1) uchun maqsad funktsiya (Bellman funktsiyasi)
birinchi bosqich (6, 7, 8) nuqtalaridan 9 oxirgi nuqtaga qadar bo'lgan minimal
yo'ldir, ya'ni S1 (i) = si9. Keyingi bosqichlar uchun yo'l uzunligi ikki yig’indidan
iborat –n-bosqichning i nuqtasidan j (n - 1)-bosqichning j nuqtasigacha bo’lgan Sij
yo’li va j nuqtadan oxirgi nuqtagacha bo'lgan yo'lning minimal uzunligi, ya'ni Sn -
1 (j). Shunday qilib, funktsional Bellman tenglamasi quyidagi shaklga ega bo'ladi:
Minimal uzunlik ma'lum bir qiymat j*
da erishiladi, bu i nuqtadan oxirgi
nuqtaga harakatning optimal yo'nalishidir. Beshinchi bosqichda biz boshlang'ich
nuqtaga etib boramiz va tizimning holati i = 1 bo’lib aniqlangan bo’ladi. S5(1)
funktsiyasi 1-chi nuqtadan 9-nuqtagacha bo’lgan minimal yo’lni ifodalaydi.
Optimal yo'nalish barcha bosqichlarni teskari tartibda
tahlil qilish orqali
aniqlanadi.
Dostları ilə paylaş: