Динамичко програмирање је концепт који је развио Ричард Белман, математичар и економиста.
У то време, Беллман је тражио начин да реши сложене проблеме оптимизације. Проблеми оптимизације захтевају да изаберете најбоље решење из скупа опција.
Пример проблема оптимизације је проблем трговачког путника. Циљ је пронаћи најкраћи пут који ће омогућити продавцу да посети сваки град тачно једном и врати се у почетни град.
Белманов приступ овим проблемима је био да их разбије на мање подпроблеме и реши подпроблеме од најмањег до највећег. Затим је сачувао резултате подпроблема и поново их користио за решавање већих подпроблема. Ово је главна идеја која стоји иза динамичког програмирања.
Преглед садржаја
Шта је динамичко програмирање?
Динамичко програмирање решава проблеме оптимизације тако што их разлаже на мање подпроблеме, решавајући сваки подпроблем једном и чувајући њихова решења тако да се могу поново користити и комбиновати за решавање већег проблема. Проблеми се решавају од најмањег до највећег, омогућавајући поновну употребу решења.
Како функционише динамичко програмирање?
Решавање проблема помоћу динамичког програмирања укључује следеће кораке:
Да бисмо видели ово на делу, израчунавамо 6. Фибоначијев број, Ф(6), користећи овај процес.
Прво дефинишите подпроблеме које треба решити.
Ф(н) = Ф(н-1) + Ф(н-2) за н > 1
Дакле: Ф(6) = Ф(5) + Ф(4)
Ф(5) = Ф(4) + Ф(3)
Ф(4) = Ф(3) + Ф(2)
Ф(3) = Ф(2) + Ф(1)
Ф(2) = Ф(1) + Ф(0)
Ф(1) = 1
Ф(0) = 0
Други корак укључује решавање сваког подпроблема коришћењем рекурзивне функције или итеративног процеса. Решавамо подпроблеме од најмањег до највећег, поново користећи резултате мањих подпроблема. Ово нам даје следеће:
Ф(0) = 0
Ф(1) = 1
Ф(2) = Ф(1) + Ф(0) = 1 + 0 = 1
Ф(3) = Ф(2) + Ф(1) = 1 + 1 = 2
Ф(4) = Ф(3) + Ф(2) = 2 + 1 = 3
Ф(5) = Ф(4) + Ф(3) = 3 + 2 = 5
Ф(6) = Ф(5) + Ф(4) = 5 + 3 = 8
Како решавамо сваки од подпроблема, ми складиштимо решења у низ или табелу тако да се могу поново користити у решавању већих подпроблема као што су:
Када су сви подпроблеми решени, користимо решења да конструишемо решење првобитног проблема.
У овом случају, решење првобитног проблема је 6. Фибоначијев број, који се налази сумирањем резултата Ф(5) и Ф(4), подпроблема идентификованих из највећег проблема. Резултат нам даје 8.
Где и зашто се користи динамичко програмирање?
Динамичко програмирање се користи у областима где имамо проблеме који се могу поделити на мање подпроблеме, а њихова решења се користе за решавање већих проблема.
Ове области укључују рачунарство, економију, математику и инжењерство. У рачунарској науци, користи се за решавање проблема који укључују низове, графове и целобројне вредности иу такмичарском програмирању.
У економији се користи за решавање проблема оптимизације у финансијама, производњи и алокацији ресурса. У математици се динамичко програмирање користи у теорији игара, статистици и вероватноћи, где се користи за решавање проблема оптимизације.
У инжењерству се користи за решавање проблема у алокацији ресурса, планирању, производњи, комуникацији и системима управљања.
Постоји неколико предности коришћења динамичког програмирања за решавање проблема оптимизације:
Када је у питању решавање проблема оптимизације, динамичко програмирање је веома користан алат за осигурање ефикасности у решењима.
Приступи који се користе у динамичком програмирању
У динамичком програмирању, два приступа се користе за решавање проблема оптимизације. То су приступ одозго надоле и приступ одоздо према горе.
Одозго на доле приступ
Овај приступ је познат и као мемоизација. Мемоизација је техника оптимизације која се првенствено користи за убрзавање рачунарских програма тако што се резултати позива функција чувају у кеш меморији и враћају кеширани резултати следећи пут када буду потребни уместо да се поново рачунају.
Приступ одозго надоле укључује рекурзију и кеширање. Рекурзија укључује функцију која сама себе позива са једноставнијим верзијама проблема као аргументом. Рекурзија се користи за разбијање проблема на мање подпроблеме и решавање подпроблема.
Када се подпроблем реши, његов резултат се кешује и поново користи кад год се појави сличан проблем. Одозго надоле је лако разумети и применити и само једном решава подпроблем. Недостатак тога је, међутим, што заузима много меморије због рекурзије. Ово може довести до грешке прекорачења стека.
Приступ одоздо према горе
Приступ одоздо према горе, такође познат као табела, уклања рекурзију, замењујући је итерацијом, чиме се избегавају грешке преливања стека.
У овом приступу, велики проблем се дели на мање подпроблеме, а решења за подпроблеме се користе за решавање већег проблема.
Мањи подпроблеми се прво решавају од највећег до најмањег, а њихови резултати се чувају у матрици, низу или табели, отуда и назив табела.
Сачувани резултати решавају веће проблеме који зависе од подпроблема. Резултат првобитног проблема се затим проналази решавањем највећег подпроблема коришћењем претходно израчунатих вредности.
Овај приступ има предност у томе што је ефикасан у меморији и времену јер укида рекурзију.
Примери проблема који се могу решити динамичким програмирањем
Следе неки проблеми програмирања који се могу решити коришћењем динамичког програмирања:
#1. Проблем са ранцем
Извор: Википедија
Ранац је торба направљена од платна, најлона или коже која се обично веже на леђима и коју војници и планинари користе за ношење залиха.
У проблему ранца, представљен вам је ранац, а с обзиром на његову носивост, од вас се тражи да изаберете предмете, од којих свака има своју вредност. Ваш избор треба да буде такав да добијете максималну укупну вредност изабраних артикала и да тежина предмета буде мања или једнака капацитету ранца.
Пример проблема са ранцем је дат у наставку:
Замислите да идете на планинарење и имате ранац капацитета 15 килограма. Имате листу ставки које можете понети са собом, заједно са њиховим вредностима и тежинама, као што је приказано у табели испод:
СтавкаВриједностТежина Шатор2003 Врећа за спавање1502Шпорет501Храна1002Флаша за воду100,5Комплет прве помоћи251
Изаберите подскуп ствари које желите да донесете тако да укупна вредност предмета буде максимизирана док је укупна тежина мања или једнака капацитету ранца, који износи 15 килограма.
Примене проблема ранца у стварном свету укључују одабир хартија од вредности које ће се додати у портфолио како би се минимизирао ризик и максимизирао профит и проналажење најмање расипничких начина за сечење сировина.
#2. Проблем са планирањем
Проблем планирања је проблем оптимизације у којем је циљ оптимално додељивање задатака скупу ресурса. Ресурси могу бити машине, особље или други ресурси који се користе за извршавање задатака.
Пример проблема са заказивањем је дат у наставку:
Замислите да сте менаџер пројекта одговоран за заказивање скупа задатака које треба да обави тим запослених. Сваки задатак има време почетка, време завршетка и листу запослених који су квалификовани да га заврше.
Ево табеле која описује задатке и њихове карактеристике:
Задатак Време почетка Крајње време Квалификовани запослениТ1911А, Б, ЦТ21012А, ЦТ31113Б, ЦТ41214А, Б
Доделите сваки задатак запосленом да бисте свели на минимум укупно време завршетка.
Проблем планирања може се наићи у производној индустрији када покушавате да оптимизујете алокацију ресурса као што су машине, материјали, алати и радна снага.
Такође се може срести у здравству када се оптимизује употреба кревета, особља и медицинског материјала. Друге индустрије у којима се овај проблем може појавити су управљање пројектима, управљање ланцем снабдевања и образовање.
#3. Проблем трговачког путника
Извор: Википедија
Ово је један од највише проучаваних проблема оптимизације који се може решити коришћењем динамичког програмирања.
Проблем трговачког путника даје листу градова и удаљености између сваког пара градова. Од вас се тражи да пронађете најкраћу могућу руту која посети сваки град тачно једном и врати се у изворни град.
Пример проблема са путујућим продавцем је дат у наставку:
Замислите да сте продавац који треба да посети скуп градова у најкраћем могућем року. Имате листу градова које треба да посетите и удаљености између сваког пара градова, као што је приказано у табели испод:
ЦитиАБЦДЕА010152030Б100352515Ц153503020Д202530010Е301520100
Проблем трговачког путника може се наићи у индустрији слободног времена када покушава да планира руте за туристе, логистици при планирању отпреме робе, транспорту при планирању аутобуских рута и у индустрији продаје, између осталог.
Јасно је да динамичко програмирање има много апликација у стварном свету, што помаже да се сазна више о томе.
Размотрите следеће ресурсе да бисте објаснили своје знање о динамичком програмирању.
Ресурси
Динамичко програмирање Рицхарда Беллмана
Динамичко програмирање је књига Ричарда Белмана, који је осмислио динамичко програмирање и развио га у његовим раним фазама.
Књига је написана на лако разумљив начин који захтева само основно знање математике и рачуна да би се текст разумео. У књизи, Белман уводи математичку теорију вишестепеног процеса одлучивања који је кључан у динамичком програмирању.
Књига затим испитује проблеме уских грла у вишестепеним производним процесима, теореме постојања и јединствености и оптималну једначину залиха.
Најбоља ствар у књизи је то што Белман нуди примере многих сложених проблема у областима као што су логистика, теорија распореда, теорија комуникације, математичка економија и контролни процеси и показује како динамичко програмирање може да реши проблеме.
Књига је доступна у Киндле верзији, тврдом повезу и меком повезу.
Мастер курс алгоритама динамичког програмирања
Овај мастер курс алгоритама за динамичко програмирање од стране Удеми-а нуде Апаар Камал, софтверски инжењер у Гуглу, и Пратик Наранг, који је такође радио са Гоогле-ом.
Курс је оптимизован да помогне ученицима да се истичу у такмичењу у програмирању које садржи много проблема који захтевају динамичко програмирање.
Осим за такмичаре у програмирању, курс је идеалан за програмере који желе да побољшају своје разумевање алгоритама и људе који се припремају за интервјуе за програмирање и рунде кодирања на мрежи.
Курс, који траје преко 40 сати, детаљно покрива динамичко програмирање. Курс прво нуди освежење о концептима као што су рекурзија и враћање уназад.
Затим покрива динамичко програмирање у теорији игара, низове, стабла и графове, експоненцијацију матрице, битмаске, комбинаторику и подсеквенце, проблеме партиција и вишедимензионално динамичко програмирање, међу многим другим концептима.
Основе конкурентног програмирања, мастер алгоритми
Удеми нуди Основе конкурентног програмирања Пратеек Наранг и Амал Камаар који покрива динамичко програмирање, математику, теорију бројева и напредне структуре података и алгоритме на начин који је користан и релевантан за конкурентне програмере.
Курс нуди освежење о структурама података и алгоритмима пре него што уђе у сложеније алгоритме и технике које су корисне у конкурентном програмирању.
Курс покрива динамичко програмирање, математику, теорију игара, подударање шаблона, Битмаскинг и безброј напредних алгоритама који се користе и тестирају на такмичењима у програмирању.
Удеми курс је подељен на 10 модула и 42 секције и нуди много практичних питања након сваког одељка. Овај бестселер курс је обавезан за све заинтересоване за конкурентно програмирање.
Завршне речи
Динамичко програмирање је корисна вештина за сваког програмера да научи да побољша своје решавање проблема у стварном свету. Због тога би програмери требало да размотре да прођу кроз предложене ресурсе како би додали овај кључни алат у своју кутију са алаткама.
Затим можете погледати програмске језике за употребу у науци о подацима.