Dinamik dasturlash uchun optimallashtirish usullari

Bino vazifasi algoritm
Dinamik dasturlash algoritm, shuning uchun uning hal ikki yoki undan ko'p Alt bo'linadi vazifasi barcha Alt topshiriqlardan uchun optimal yechim topgan bunday vazifalarni qurilishini o'z ichiga oladi, u o'z ichiga oladi. Bundan tashqari, u qaytish aloqasi, yozish va bir butun sifatida vazifa uchun optimal parametr qadriyatlarini hisoblash uchun zarur.
ad
Ba'zan, 3 qadam, har bir ishning borishi haqida ba'zi qo'shimcha fon ma'lumot yod iborat. Bu Qaytish urish deyiladi.
Application usuli
ikki xarakterli xususiyatlari bor qachon Dinamik dasturlash qo'llaniladi:

• 
  Alt topshiriqlardan uchun optimal;
  
• 
  subproblems nizomiga muvofiq muammosi mavjudligi.
  

dinamik dasturlash tomonidan optimallashtirish muammoni hal qilish, avval hal tuzilishini tasvirlab kerak. vazifa hal o'z Alt topshiriqlardan eng yaxshi qarorlardan iborat bo'lsa optimal bo'lishi kerak. Bu holda, u dinamik dasturiy foydalanish tavsiya etiladi.
Bu usul muhim muammoning ikkinchi xususiyat, - sub-vazifalarni kichik raqam. Shu ketma-ket kelgan sub-muammolarni yordamida muammoni Tekrarlamalı eritmasi, soni, dastlabki ma'lumotlar hajmiga bog'liq. javob maxsus jadvalda saqlanadi, dastur bu ma'lumotlarni yordamida vaqtni tejash imkonini beradi.
Ayniqsa, samarali vazifa aslida bosqichda qaror qabul qilish uchun zarur bo'lgan dinamik dasturlash foydalanish hisoblanadi. Misol uchun, almashtirish va uskunalar ta'mirlash muammoning oddiy misolni ko'rib. ikki turli shakllarda shina qilish bir vaqtning o'zida shinalari ishlab chiqarish bo'yicha to'qimalarining mashinasi zavodi haqida aytaylik. shakllaridan biri bajarilmasa, u holda, bu Demontaj uchun zarur. Bu ba'zan ko'proq daromadli o'rniga va holatda Demontaj uchun ikkinchi shakli va bu shakl keyingi bosqichda bajarilish bo'ladi, deb tushunsa bo'ladi. Ayniqsa, ular muvaffaqiyatsizlikka boshlash oldin ikkala ish shaklini o'zgartirish uchun oson, chunki. davom ekspluatatsiya shakllari, mashina uzilishlar, tashlanadi shinalari va ko'proq mablag 'yo'qotish foydalari: Dinamik dasturlash usuli hisobga barcha omillar olib, bu shakllarini almashtirish masalada eng yaxshi strategiya belgilab beradi.
Xulosa qilib aytganda, dinamik dasturlash muammoni kichik masalalarga ajratish va ularning yechimlarini birlashtirish orqali hal qilish usulidir.
Odatda, dinamik dasturlash optimallashtirish masalalarida, masalan, A shahridan B shahriga o'tish uchun eng qisqa marshrutni topish kerak bo'lganda qo'llaniladi. Yoki bu o'tishlarning barcha mumkin bo'lgan kombinatsiyalarini yoki elementlarning joylashishini hisoblash kerak bo'lgan muammolar bo'lishi mumkin. Ushbu usuldan foydalanadigan klassik misol Fibonachchi ketma-ketligidir.
F (n) = F (n-1) + F (n-2);
F (0) = 0;
F (1) = F (2) = 1;
Ko'rib turganingizdek, ketma-ketliklarga oid masalalarni yechish uchun quyidagi shartlarni belgilash kerak: ketma-ketlik elementlarining bir-biridan takroriy bog'liqligi, boshlang'ich holati. Ularni har doim ham to'g'ridan-to'g'ri holatda ko'rsatib bo'lmaydi, chunki bu yuqoridagi muammoda bo'lgani kabi. Masalan, " Dinamik dasturlash: Chigirtkaning traektoriyalari " videosida ular vazifani A nuqtadan B nuqtaga o'tishlar soni bilan tahlil qiladilar.
Yuqorida ko'rib chiqilgan holatlarda davlat parametri bitta raqam edi, ammo bundan ham murakkab, ko'p o'lchovli muammolar sinflari mavjud. Ko'p o'lchovli dinamika uchun holat parametrlari quyidagilar bo'lishi mumkin:

• 
  massivlar,
  
• 
  vektorlar,
  
• 
  massivlar ichidagi segmentlar,
  
• 
  daraxtlar,
  
• 
  kichik to'plamlar,
  
• 
  profil bo'yicha dinamika
  
• 
  va hokazo.
  

Dinamikaning optimal holatini izlash, o'tish va qayta hisoblash tartibi (oldinga yoki orqaga) va dinamik dasturlash usulini o'z ichiga oladi.
Ushbu usulning qo'llanilishi va uni qanday optimallashtirish haqida algoritmlar bo'yicha deyarli barcha kitoblarda, masalan, "Algoritmlar. Qurilish va tahlil".
Javobning foydaliligi reytingi:
0,7
Dinamik dasturlash - bu "bo'l va zabt et" g'oyasiga asoslangan muammolarni hal qilishda juda keng qo'llaniladigan yondashuv. Ko'pincha, kirish ma'lumotlarini oladigan, ular bilan biror narsa qiladigan va darhol javob beradigan muammoni hal qilishning umumiy algoritmini yaratish imkonsiz yoki juda qiyin.
Ko'pincha muammoni "bir qiling, ikkita qiling, uchta qiling" usuli yordamida hal qilishning imkoni yo'q. Lekin siz har doim katta vazifani juda ko'p kichiklarga bo'lishingiz va soddalashtirilgan vazifalar ibtidoiy sodda bo'lgunga qadar bo'lishingiz mumkin. Bu "bo'l va zabt et" deb nomlanuvchi yondashuv. Buning uchun ko'pincha rekursiya qo'llaniladi - funktsiyaning o'zi chaqiriladi.
Muhim xususiyat shundaki, bu jarayon tsikllarda o'tmaydi, ba'zi bir bosqichda vazifa ibtidoiy holatga tushirilishi kerak, javob darhol ma'lum bo'ladi. Masalan, sonning faktorialini hisoblash. Bunday muammoni oddiy algoritm n!= 1 · 2 · 3 · ... · n yordamida hal qilish mumkin, bu holda siz darhol qiymatni olishingiz mumkin (masalan, 4! = 1 · 2 · 3 2 3 4 5 = 120). Ammo xuddi shu muammoni rekursiv hal qilish mumkin, chunki 5! = 5 4 !, va 4! = 4 3! va boshqalar. Shunday qilib, faktorial n ni hisoblash uchun oddiy funktsiyani yozishingiz mumkin! Va faqat ibtidoiy holatda 1! funktsiya o'zini chaqirmaydi, lekin darhol 1 ni qaytaradi, bu hech qanday aylanish sodir bo'lmasligi uchun muhim nuqta.

Nima uchun dinamik dasturlash tillari katta hajmdagi kodlarni saqlashni qiyinlashtiradi

tproger.ru

Ammo "bo'l va zabt et" hali ham to'liq dinamik dasturlash emas, chunki bu yondashuv oddiy bo'lsa ham, ko'pincha kerakli hisob-kitoblarning ko'chkiga o'xshash o'sishiga olib keladi, garchi usulning o'zi siz xohlagancha sodda bo'lishi mumkin.

Masalan, shahar bo‘ylab A nuqtadan B nuqtagacha bo‘lgan eng qisqa yo‘lni topish masalasini olaylik. Amalda bunday masalalar grafik nazariyasi yordamida hal qilinadi, shaharning har bir ko‘chasi grafikning cheti bilan bog‘langan va har bir mumkin bo'lgan qolish nuqtasi grafikning tugunidir. Har bir chekkaga ma'lum bir shartli "xarajat" belgilanadi, masalan, tranzit vaqti yoki to'g'ridan-to'g'ri tegishli "ko'cha" bo'ylab sayohatning pul qiymati. Aslida, bu xarajat hatto vaqt o'tishi bilan o'zgarishi mumkin, masalan, tirbandlik tufayli. Keyin bizga eng qisqa marshrutni topadigan funksiya kerak - tugunlarning bunday ketma-ketligi, ular orqali biz ularni bog'laydigan barcha qirralarning o'tishining minimal "xarajatini" olamiz.
Va bunday vazifalar uchun dinamik dasturlash usullari amalda yagona ishchi echimga aylanadi. Bu erda rekursiya usullari endi mos emas: siz, albatta, bu muammoni hal qilishingiz mumkin va shu tarzda: har bir mumkin bo'lgan "ko'chalar" bo'ylab A nuqtasini tark etish narxini qaytaradigan funktsiyani yozing, bu funktsiyalarning har biri, o'z navbatida, unga keyingi "chorraha"gacha sayt narxini qo'shib qo'yadi, yana o'zini chaqiradi va "B" nuqtasiga yetguncha buni ko'p marta takrorlaydi. Natijada, barcha javob zanjirlari orasidan tanlash mumkin bo'ladi. eng kam xarajat bilan bir va muammoga javob olish. Ammo amalda bu faqat o'nlab tugunlarga ega bo'lgan juda oddiy grafiklar uchun, masalan, metro xaritasi uchun amalga oshirilishi mumkin. Ammo allaqachon shahar ko'chalari xaritasi miqyosida bunday algoritmlar haqiqiy emas.
Javobning foydaliligi reytingi:
Chiziqli va chiziqli bo'lmagan dasturlash muammolarida optimallashtiriladigan jarayon statik, ya'ni vaqtdan mustaqil deb hisoblanadi. Bunday muammolarning optimal yechimi bitta rejalashtirish bosqichida topiladi. Bu vazifalar bir bosqichli vazifalar deb ataladi.
Dinamik dasturlash masalalarida optimallashtirish jarayoni vaqtga bog'liq (vaqtning bir necha bosqichlaridan). Shuning uchun optimal yechim har bir bosqich uchun ketma-ket topiladi, shu bilan birga butun jarayon uchun optimal echimlar taqdim etiladi. Dinamik dasturlash vazifalari ko'p bosqichli deb ataladi.