10-mavzu. Dinamik dasturlash tamoyillari Dinamik dasturlashning tamoyili

2. Dinamik dasturlash masalalarini yechish sxemasi.

Ko'p bosqichli qarorlarni qabul qilish jarayonlari turli xil vaziyatlarda uchrashi mumkin, masalan, zaxiralarni boshqarish, resurslarni taqsimlash yoki kosmik kemalarni boshqarish vazifalari. Har bir ko'p bosqichli qarorlarni qabul qilish jarayonini yo'naltirilgan tarmoqdagi eng qisqa yo'lni topishning eng tushunarli ko'p bosqichli jarayonini ishlab chiqish deb hisoblsh mumkin (10.1-rasm). Ushbu misoldan foydalanib, R. Bellmanning optimallashtirish tamoyili mohiyatini namoyish etish mumkin.

10.1-rasm. Yo'naltirilgan tarmoq

Yo'naltirilgan tarmoq N qaror bosqichlariga ega bo'lsin. 10.1-rasmdan ko’rinib turibdiki N = 5 ga teng. Quyidagi belgilashni kiritamiz:
n - bosqich raqami (n = 1, 2, 3, 4,5);
i - harakat amalga oshirilgan joy (i = 1, 2, ..., 8);
j - harakat yo'naltirilgan nuqta (j = 2, 3, ..., 9);
Sij - i nuqtadan j nuqtagacha bo'lgan masofa;
Sn (i) - bu masalani yechishning n-bosqichida i nuqtadan oxirgi nuqtagacha bo'lgan minimal masofa.
Nuqta n-bosqichga tegishli deb taxmin qilinadi, agar undan aniq n bosqichda yakuniy nuqtaga o'tish mumkin bo'lsa. Ko’rinib turibdiki, n-bosqichning biror 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.