Dinamik dasturlashtirish usuli, Bellman tenglamasi

Dinamik dasturlash odatda muammolarni yechishda ikkita yondashuvga amal qiladi:

• Dinamik dasturlash odatda muammolarni yechishda ikkita yondashuvga amal qiladi:
• Yuqoridan pastga: vazifa kichikroq qismlarga bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Tez-tez uchraydigan kichik qismlarni yechimlari xotirada saqlanadi.
• Quyidan yuqoriga: Dastlabki muammoni hal qilish uchun kerak bo'ladigan barcha pastki jadvallar oldindan hisoblab chiqiladi va keyinchalik asl muammoni hal qilishda foydalaniladi. Ushbu usul kerakli stek hajmining kattaligi va funktsiyalarni chaqirish soni nuqtai nazaridan yuqoridan pastga bo'lgan dinamik dasturlashga qaraganda yaxshiroqdir, ammo ba'zida kelajakda biz uchun qaysi kichik masala natijasi kerak bo'lishini oldindan aniqlash oson emas.

Odatda dinamik dasturning ishlash vaqti quyidagi funktsiyalardan iborat:

• Odatda dinamik dasturning ishlash vaqti quyidagi funktsiyalardan iborat:
• Oldindan ishlov berish
• Loop for loopi necha marta ishlaydi
• Qayta ishlashni takrorlash uchun birida ishlash uchun qancha vaqt ketishi kerak
• Post-qayta ishlash
• Umuman olganda, ish vaqti quyidagi shaklda bo'ladi:
• Dastlabki ishlov berish + Loop * Takrorlash + Post-ishlash

Yo'naltirilgan tarmoq N qaror bosqichlariga ega bo'lsin. 10.1-rasmdan ko’rinib turibdiki N = 5 ga teng. Quyidagi belgilashni kiritamiz:

• 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.