Mavzu. Dinamik dasturlash tamoyillar Dinamik dasturlashning tamoyili

4. Masalalar

Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat:

1-qadam. n = 1, S₁(i) = S_i9. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6, 7, 8 nuqtalaridan borish mumkin. Shuningdek: S₁(6) = 15; S₁(7) = 3; S₁(8) = 10.
2-qadam. N = 2, bu yerda biz uchinchi bosqichning (4 va 5) nuqtalaridan ikkinchi bosqichga qadar bo'lgan yo'llarni ko'rib chiqamiz. Bu yerda funktsional Bellman tenglamasi quyidagi shaklga ega bo’ladi:

Shuningdek quyidagiga ega bo’lamiz:

Shartli ravishda optimal yo'l (5-7);

Shartli ravishda optimal yo'llar (4-6 va 4-8).

3-qadam. n = 3, bu yerda to'rtinchi bosqichning (2 va 3) nuqtalaridan uchinchi bosqichgacha bo'lgan yo'llarni ko'rib chiqiladi.

Shartli ravishda optimal yo'l (2–5).

Shartli optimal yo'l (3-4).


4-qadam. n = 4, bu erda 1-nuqtadan to'rtinchi bosqichning nuqtalarigacha bo'lgan yo'llarni ko'rib chiqiladi.
S₄(1) = min {S₁₂ + S₃(2), S₁₃ + S₃(3)} = min {(1 + 22); (2 + 20);} = 22.
Shartli ravishda optimal yo'l (1-3).
Endi biz 1-nuqtadan 9-gacha bo'lgan eng qisqa shartsiz yo'lni topamiz. Shartli optimallashtirish bosqichida minimal yo'lning uzunligi S₄(1) = 22 ekanligi aniqlandi, bu natija birinchi nuqtadan uchinchisiga o'tganda erishiladi, keyin to'rtinchisiga o'tish kerak. Ushbu bosqichdan boshlab, 2-bosqichda ko'rsatilgandek, 6 va 7-nuqtalarga ikkita mumkin bo'lgan ekvivalent yo'nalish mavjud. Shunday qilib, optimal yechimga 10.2-rasmda ko'rsatilgan ikkita yo'nalish orqali erishiladi, aniqrog'i (1-3–4–6–9) va (1-3–4–8–9).



10.2-rasm. Optimal yo’l
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:

• 
  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
Dinamik dasturlar uchun katta-O bilan tanishish uchun punchcard muammosining ishlash vaqtini tahlil qilaylik. Bu yerda punchcard muammolari dinamik dasturi:
def punchcardSchedule (n, qiymatlar, keyingi):
# Eslatma qatorini boshlang - 4 bosqich
memo = [0] * (n + 1)
# Asosiy korpusni o'rnatish
memo [n] = qiymatlar [n]
# N dan 1 gacha xotiralar jadvalini tuzing - 2 bosqich
diapazondagi i uchun (n-1, 0, -1):
memo [i] = maks (v_i + memo [next [i]], memo [i + 1])
# OPT (1) muammosiga echim - 3 bosqich
qaytish eslatmasi [1]
Uning ish vaqti buzilsin:

• 
  Dastlabki ishlov berish: Bu yerda yodlash massivini yaratish kerak. O (n).
  
• 
  Loop necha marta ishlaydi: O (n).
  
• 
  Loop iteratsiyasi uchun birida ishlash uchun takroriylik qancha vaqtni oladi: takrorlanish doimiy ishlash vaqtini oladi, chunki har bir iteratsiyada ikkita variant o'rtasida qaror qabul qilinadi. O (1).
  
• 
  Post-qayta ishlash: Bu yerda yo'q! O (1)
  

Muammoli dinamik dasturning umumiy ish vaqti O (n) O (n) * O (1) + O (1) yoki soddalashtirilgan shaklda O (n).