Ajrat va hukmronlik qil

Nazariy qism
Boshqarish nazariyasi va kompyuter tizimlari nazariyasida dinamik dasturlash - eng ko'p uchraydigan muammolarni buzib, murakkab muammolarni hal qilish qobiliyati. Optimal substruktsiya bilan bog'liq muammolarga kelsak, bu murakkab siljishlar qatoriga o'xshaydi, murakkabligi aslidan biroz kamroq. Bunday holda, "sodda" usullar bilan solishtirganda hisoblash vaqti sezilarli darajada kamayishi mumkin.

Dinamik dasturlashda asosiy g'oya juda oddiy. Qoida tariqasida, vazifani hal qilish uchun hal qiluvchi alohida vazifalar (pastki chiziqlar) talab qilinadi, shundan so'ng pastki qismlarning echimlari bitta umumiy echimga birlashtiriladi. Ko'pincha etiklardan, subkastrlardan ko'p narsa bir xil. Dinamik davlat dasturiga yondashuv kaizu subtaskasini faqat bir marta echish, shu bilan izolyatsiya sonini kamaytirishdir. Bu, ayniqsa, takroriy taglavhalar soni eksponent bo'yicha katta bo'lgan holatlarda foydalidir.

Sverxu dinamik dasturlash usuli shunchaki keyinchalik takrorlanishi mumkin bo'lgan sub-vazifalarni hal qilish natijalarini saqlashdir. Dinamik dasturlash murakkab vazifani sodda taglavhalarning rekursiv ketma-ketligi shaklida qayta o'zgartirishni ham o'z ichiga oladi.

"Dinamik dasturlash" iborasi birinchi marta 1940 yillarda Richard Bellman tomonidan muammoning echimini topish jarayonini tasvirlash uchun ishlatilgan bo'lib, unda bitta muammoga javob faqat "oldingi" muammoni hal qilganidan keyingina olish mumkin. 1953 yilda u ushbu ta'rifni zamonaviyga aniqlab berdi. Dastlab, ushbu soha IEEE tomonidan tan olingan tizimlarni tahlil qilish va muhandislik sifatida tashkil etilgan. Bellmanning dinamik dasturlashdagi hissasi dinamik dasturlash nazariyasining markaziy natijasi bo'lgan Bellman tenglamasi nomi bilan abadiylashtirildi, bu esa optimizatsiyalash muammosini rekursiv shaklda isloh qiladi.

"Dinamk dasturlash" jumlasidagi "dasturlash" so'zi aslida "an'anaviy" dasturlash (yozuv kodi) bilan hech qanday aloqasi yo'q va "optimallashtirish" so'ziga sinonim bo'lgan "matematik dasturlash" iborasidagi kabi ma'noga ega. Shuning uchun ushbu dasturda "dastur" so'zi muammoni hal qilish uchun maqbul harakatlar ketma-ketligini anglatadi. Masalan, ko'rgazmadagi tadbirlar jadvaliga ba'zan dastur deyiladi. Bu holda dastur deganda voqealar ketma-ketligi tushuniladi.

Dinamik dasturlashda maqbul pastki tuzilma asl muammoni hal qilish uchun kichik kichik vazifalarni maqbul echimini qo'llash mumkinligini anglatadi. Masalan, bitta verteksdan ikkinchisiga (s bilan belgilanadigan) grafikdagi eng qisqa yo'lni quyidagicha topish mumkin: birinchi navbatda s-dan t -gacha ulashgan barcha vertikallardan eng qisqa yo'lni ko'rib chiqing, so'ngra ularni bog'laydigan qirralarning og'irligini hisobga oling. qo'shni uchlari bilan t ga eng yaxshi yo'lni tanlang (qaysi tepadan o'tish yaxshidir). Umumiy holda, maqbul pastki tuzilma mavjud bo'lgan muammoni quyidagi uchta amalni bajarish orqali hal qilishimiz mumkin.

Vazifani kichikroq pastki qismlarga bo'lish.

Subtastrlarning eng maqbul echimini topish uch bosqichli algoritmni bajarish bilan rekursivdir.

Olingan pastki chizmalarning echimini asl muammoning echimini yaratish uchun ishlatish.

Subproblemlar doimiy ravishda echilishi mumkin bo'lgan muammoning arzimas holatiga kelgunga qadar, ularni kichikroq hajmdagi kichik dasturlarga va hokazolarga bo'lish orqali hal qilinadi (javob darhol aytilishi mumkin). Masalan, agar biz n ni topishga muhtoj bo'lsak, unda arzimas vazifa 1 bo'ladi! = 1 (yoki 0! = 1).

Dinamik dasturlashda bir-birini to'ldirib turadigan pastki qavatlar deganda kattaroq o'lchamdagi bir qator muammolarni (bitta emas) hal qilish uchun foydalaniladigan pastki tagliklar tushuniladi (ya'ni biz bir xil ishni bir necha bor qilamiz). Fibonachchi ketma-ketligini hisoblash, {\ displaystyle F_ {3} = F_ {2} + F_ {1}} F_ {3} = F_ {2} + F_ {1} va {\ displaystyle F_ {4} = F_ { 3} + F_ {2}} F_ {4} = F_ {3} + F_ {2} - hatto ikkita Fibonachchi sonini hisoblashning ahamiyatsiz bo'lmagan taqdirda ham, biz {\ displaystyle F_ {2}} F_ {2} ni ikki marta sanadik. Agar biz oldinga borsak va {\ displaystyle F_ {5}} F_ {5} ni hisoblasak, {\ displaystyle F_ {2}} F_ {2} yana ikki marta sanaladi, chunki {\ displaystyle F_ {5}} F_ { 5} yana {{displaystyle F_ {3}} F_ {3} va {\ displaystyle F_ {4}} F_ {4} uchun yana kerak bo'ladi. Bu quyidagicha ko'rinadi: oddiy rekursiv yondashuv, u allaqachon hal qilgan muammolar uchun echimni hisoblash uchun vaqt sarflaydi.

Hodisalarning bunday holatiga yo'l qo'ymaslik uchun biz allaqachon hal qilgan pastki qismlarning echimlarini saqlab qolamiz va yana biz yana hisob-kitob qilishning o'rniga, pastki qism echimini talab qilsak, shunchaki uni xotiradan o'chirib tashlaymiz. Ushbu yondashuv eslab qolish deb nomlanadi. Keyinchalik optimallashtirishni amalga oshirishingiz mumkin - masalan, agar biz pastki qismni echishga endi ehtiyoj qolmasligiga amin bo'lsak, uni xotiradan o'chirib, boshqa ehtiyojlar uchun bo'shatib qo'yamiz yoki protsessor bo'sh bo'lsa va biz hali hisoblanmagan pastki qismlarga echim topilishini bilsak, kelajakda bizga kerak bo'ladi, biz ularni oldindan hal qilishimiz mumkin.

Yuqoridagilardan xulosa qilib aytish mumkinki, dinamik dasturlash muammoning quyidagi xususiyatlaridan foydalanadi.

bir-birini to'ldiruvchi pastki satrlar;

maqbul pastki tuzilma;

tez-tez uchraydigan pastki qismlarga echimlarni yodlash qobiliyati.

Dinamik dasturlash odatda muammolarni echishda ikkita yondashuvga amal qiladi:

pastga qarab dinamik dasturlash: vazifa kichik pastki qismlarga bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Xotiralash allaqachon echilgan pastki qismlarni echish uchun ishlatiladi.

upstream dinamik dasturlash: keyinchalik asl muammoni hal qilish uchun kerak bo'lgan barcha quyi chiziqlar oldindan hisoblab chiqiladi va keyinchalik asl muammoning echimini yaratishda foydalaniladi. Ushbu usul kerakli stack hajmi va funktsiyalar soni bo'yicha nuqtai nazaridan yuqoridan-pastga dasturlashdan afzaldir, lekin ba'zida kelajakda qaysi pastki satrlarni hal qilishimiz kerakligini oldindan aniqlash oson emas.