10-Ma’ruza. Dinamik dasturlash algoritmlarini loyihalash va tahlil qilish Reja

1. Massivdan foydalanish:
F[0] = 1;
F[1] = 1;
for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2];


2. O'zgaruvchini ishlatish
int a=0;
int b=1;
for (i = 2; i < n; i++)
{ int c=a+b; a=b; b=c;}

Algoritmning murakkablik darajasi- ;

Bunday yechimni "boshidan" deb nomlash mumkin - biz avval ma'lum qiymatlarni to'ldiramiz, so'ngra birinchi kerakli noma'lum qiymatni (F₃), so'ngra keyingisini va hokazolarni topamiz, biz to'g'ri natijaga erishgunga qadar.

Dinamik dasturlash uchun klassik bo'lgan bunday yechim: biz avval barcha subtitrlarni yechdik, keyin subtitrlarning yechimini bilib, javob topdik.

3. 
   Dinamik dasturlashning umumiy g’oyasi
   

Ko'pincha vazifani belgilashda barcha mumkin bo'lgan variantlarni saralash maqbul tuyuladi. Biroq, bunday variantlarning juda ko'pligi va natijada kompyuterning xotirasini haddan tashqari yuklaganligi sababli, bu usul har doim ham ma’qul emas.
Bundan tashqari, quyidagi savol tug'ilishi mumkin: masalan, minimal yoki maksimal qiymatni topish uchun, nega lotin topilmadi? yoki matematik tahlil apparatlarining boshqa usullaridan foydalanmayapsizmi? Agar katta miqdordagi arsenal mavjud bo'lsa, nega menga DP kerak?
Gap shundaki:
Dinamik dasturlash muammoni alohida qismlarga bo'lish (subtasklar, qadamlar) ga ajratish, ushbu quyi qismlarni yechish va keyin ushbu yechimlarni bitta umumiy yechimga birlashtirish g'oyasiga asoslanadi. Ko'pincha, quyi qismlarning aksariyati aynan bir xil bo’ladi.
Keyinchalik murakkab muammoni hal qilayotganda, biz kichik dasturlarni ishlamaymiz, balki ushbu kichik dasturning allaqachon yechilgan javobidan foydalanamiz.
Grafikda u quyidagicha ko'rinishi mumkin:

1-rasm Quyi qismlarning optimallik xususiyatini umumiy tushuntirish
Muhim: Shu sababli, vazifani kichik vazifalarga ajratish va ushbu kichik vazifalarni faqat bir marta (!) Hal qilish, shu bilan umumiy hisoblar sonini kamaytirish dinamik dasturlash uchun xos bo'lgan eng maqbul usuldir.
Muammoni derivativlar, La Grange to'plamlari va boshqalar bilan hal qilsak, biz doimiy funksiyalar bilan ishlaymiz. Dinamik dasturlash muammolarini hal qilishda biz asosan diskret funksiyalar bilan ishlaymiz, shuning uchun bu yerda doimiy funksiyalardan foydalanish haqida gapirish noo'rin. Shu sababli, ko'pgina muammolarda, ammo barchasida emas, matematik tahlil apparati qo'llanilishi mumkin emas.

Optimallashtirish vazifalari.

Optimal uzunlikdagi marshrut.
Masalan: grafik shaklida ba'zi bir yo'l xaritasi mavjud. Bizning maqsadimiz: A nuqtadan B nuqtasiga o'tish. Bu masofani yoki sarf qilingan yoqilg'ini minimallashtirish uchun bajarilishi kerak.
Bu yerda ob'ektiv funktsiya A dan B gacha bo'lgan masofa. bizning maqsadimiz masofani minimallashtirishdir. Va tanlov o'zgaruvchisi nima? Qisqa yo'lni topish uchun har safar qaror qabul qilish kerak. I.e. har bir nuqtada yoki har bir chorrahada qarorlar qabul qilinishi kerak: qayerga burilish yoki to'g'ri borish.
Muhim: Ushbu vazifadan siz allaqachon dinamik dasturlash orqali hal qilingan vazifalarning umumiy tuzilishini ko'rishingiz mumkin: har bir vazifada ob'ektiv funktsiya va tanlov o'zgaruvchisi mavjud.
Masalan: Mashinani almashtirish (xarajatlarni minimallashtirish)
Har yili biz eski avtoulovni boshqa yilga haydash to'g'risida qaror qabul qilamiz va shu bilan birga eski avtoulovni saqlash va saqlash xarajatlarini o'z zimmamizga olamizmi yoki shu mashinani sotamiz va yangisini sotib olamizmi (va shu bilan birga sotib olish xarajatlarini o'z zimmamizga olamiz).
Maqsad vazifasi: xarajatlarni minimallashtirish (yoki eski mashinani saqlash xarajatlari bo'yicha yoki yangisini sotib olish uchun).
Tanlovning o'zgarishi: har yili avtomobilni sotish yoki ketish to'g'risida qaror qabul qiling.

Masalan: birja portfeli

Birjada o'ynash, har qanday kompaniyada aktsiyalar sotib olish
Maqsad vazifasi: o'rtacha daromadni maksimal darajada oshirish, chunki birjada daromad ehtimoliy yo'l bilan olinadi, ya'ni. bu statistik jarayon, ehtimol.
Tanlov o'zgaruvchisi: qanday investitsiya portfeli bo'ladi: qancha aktsiya va qaysi kompaniyani sotib olishimiz kerak.

Masalan: Optimal ishlab chiqarishni rejalashtirish (logistika)

Mebel ishlab chiqaradigan fabrika mavjud. Zavodda tegishli mebellarni (stullar, stollar, shkaflar va boshqalarni) ishlab chiqaradigan ma'lum miqdordagi ishchilar ishlaydi.
Maqsad vazifasi: foydani ko'paytirish.
Tanlovning o'zgarishi: etarli ishchi kuchi olish uchun qancha stul yoki stolni tanlash kerak.

Masalan: O'yinlar (ehtimoliy yoki ehtimol bo'lmagan)

Turli o'yinlarda ishtirok etish
Maqsad funktsiyasi: g'alaba qozonish ehtimolini oshirish yoki o'rtacha daromadni maksimal darajada oshirish va boshqalar. Bu erda tanlov o'zgaruvchisi o'yinga xosdir.