У овом упутству ћете научити шта је динамичко програмирање. Такође ћете наћи поређење између динамичког програмирања и похлепних алгоритама за решавање проблема.
Динамичко програмирање је техника у рачунарском програмирању која помаже у ефикасном решавању класе проблема који имају преклапајуће подпроблеме и оптимална својства подструктуре.
Такви проблеми укључују опетовано израчунавање вредности истих потпроблема како би се пронашло оптимално решење.
Пример динамичког програмирања
Узмимо случај генерисања фибоначијеве секвенце.
Ако је секвенца Ф (1) Ф (2) Ф (3)… Ф (50), следи правило Ф (н) = Ф (н-1) + Ф (н-2)
Ф (50) = Ф (49) + Ф (48) Ф (49) = Ф (48) + Ф (47) Ф (48) = Ф (47) + Ф (46)…
Приметите како постоје подпроблеми који се преклапају, морамо израчунати Ф (48) да бисмо израчунали и Ф (50) и Ф (49). Ово је управо врста алгоритма у којем динамичко програмирање засија.
Како функционише динамичко програмирање
Динамичко програмирање функционише тако што чува резултат потпроблема тако да су им решења потребна када су при руци и не треба да их прерачунавамо.
Ова техника чувања вредности потпроблема назива се меморисање. Спремањем вредности у низу штедимо време за прорачуне под-проблема на које смо већ наишли.
вар м = мап (0 → 0, 1 → 1) функција фиб (н) ако кључ н није у мапи мм (н) = фиб (н - 1) + фиб (н - 2) ретурн м (н)
Динамичко програмирање памћењем је приступ динамичком програмирању одозго према доле. Преокретањем смера у којем алгоритам ради, тј. Полазећи од основног случаја и радећи ка решењу, такође можемо применити динамичко програмирање одоздо према горе.
функција фиб (н) ако је н = 0 повратак 0 иначе вар превФиб = 0, цуррФиб = 1 понављање н - 1 пута вар невФиб = превФиб + цуррФиб превФиб = цуррФиб цуррФиб = невФиб повратак цуррентФиб
Рекурзија вс динамичко програмирање
Динамичко програмирање се углавном примењује на рекурзивне алгоритме. То није случајно, већина проблема са оптимизацијом захтева рекурзију и за оптимизацију се користи динамичко програмирање.
Али не могу сви проблеми који користе рекурзију да користе динамичко програмирање. Уколико не постоје преклапајуће се потпроблеми као у проблему фибоначијеве секвенце, рекурзија може доћи до решења само помоћу поделе и освајања.
То је разлог зашто рекурзивни алгоритам попут Мерге Сорт не може да користи динамичко програмирање, јер се подпроблеми ни на који начин не преклапају.
Похлепни алгоритми вс динамичко програмирање
Похлепни алгоритми слични су динамичком програмирању у смислу да су обојица алати за оптимизацију.
Међутим, похлепни алгоритми траже локално оптимална решења или другим речима, похлепан избор, у нади да ће пронаћи глобални оптимум. Стога похлепни алгоритми могу да претпоставе да у то време изгледају оптимално, али постају скупи и не гарантују глобални оптимум.
С друге стране, динамичко програмирање проналази оптимално решење за потпроблеме, а затим доноси информисани избор да комбинује резултате тих подпроблема како би пронашло најоптималније решење.
