ДИНАМИЧКО ПРОГРАМИРАЊЕ: КАРАКТЕРИСТИКЕ, ПРИМЕР, ПРЕДНОСТИ, НЕДОСТАЦИ - ТЕХНОЛОГИЈА - 2025

Програмирање динамичко је алгоритам модел који решава сложена проблем би дељењем га у субпроблемс, чување њихове резултате да се избегне прерачунати резултате.

Овај распоред се користи када имате проблема који се могу поделити у сличне подпроблеме, тако да се њихови резултати могу поново користити. Овај распоред се углавном користи за оптимизацију.

Динамичко програмирање. Подпроблеми постављени у Фибонаццијевом низу. Извор: Викимедиа цоммонс, хр: Корисник: Дцоатзее, пронашао Корисник: Станнеред / Публиц домаин

Пре решавања доступног потпроблема, динамички алгоритам ће покушати да испита резултате претходно решених потпроблема. Решења потпроблема су комбинована да би се постигло најбоље решење.

Уместо да поново и поново израчунавате исти подпроблем, своје решење можете да похраните у неку меморију када први пут наиђете на овај подпроблем. Када се поново појави током решења другог подпроблема, узет ће се већ похрањено у меморији.

Ово је дивна идеја за подешавање времена у меморији, где коришћење додатног простора може да побољша време потребно за проналажење решења.

Карактеристике динамичког програмирања

Следеће суштинске карактеристике су оне са којима морате имати проблема пре него што се динамичко програмирање може применити:

Оптимална подструктура

Ова карактеристика изражава да се проблем оптимизације може решити комбиновањем оптималних решења секундарних проблема који га чине. Ове оптималне подструктуре су описане рекурзијом.

На пример, на графикону ће бити представљена оптимална подструктура у најкраћем путу р који иде од вертика с до вертике т:

То јест, на овом најкраћем путу може се узети било који интермедијарни врх. Ако је р заиста најкраћи пут, тада га можемо поделити на поттрасе р1 (од с до и) и р2 (од и до т), тако да су то заузврат најкраће руте између одговарајућих врхова.

Стога, да би се пронашли најкраћи путеви, решење се лако може формулисати рекурзивно, што и алгоритам Флоид-Варсхалл.

Преклапање подпроблема

Простор подпроблема мора бити мали. То јест, сваки рекурзивни алгоритам који решава проблем мораће решавати исте подпроблеме изнова и изнова, уместо да генерише нове подпроблеме.

На пример, за генерисање Фибонаццијевог низа можемо размотрити ову рекурзивну формулацију: Фн = Ф (н - 1) + Ф (н - 2), узимајући за основни случај да је Ф1 = Ф2 = 1. Тада ћемо имати: Ф33 = Ф32 + Ф31, и Ф32 = Ф31 + Ф30.

Као што можете видети, Ф31 је разрешен у рекурзивне подтребе и Ф33 и Ф32. Иако је укупан број потпроблема заиста мали, ако усвојите рекурзивно решење попут овог, на крају ћете решавати исте проблеме изнова и изнова.

То се узима у обзир динамичким програмирањем, тако да сваки подпроблем решава само једном. То се може постићи на два начина:

Одозго на доле приступ

Ако се решење било ког проблема може формулисати рекурзивно користећи решење његових подпроблема, а ако се ови подпроблеми преклапају, онда се решења потпроблема могу лако меморисати или сачувати у табели.

Сваки пут када се тражи ново решење потпроблема, табела ће се проверавати да ли је претходно решено. У случају да се решење сачува, користиће се уместо да га поново израчунава. У супротном, потпроблем ће бити решен, чувајући решење у табели.

Приступ одоздо према горе

Након што се проблем проблема формулише рекурзивно у смислу његових подпроблема, могуће је покушати проблем преформулисати нагоре: прво ћемо покушати да решимо потпроблеме и користећи њихова решења да бисмо дошли до решења за веће подпроблеме.

То се такође обично ради у облику табеле, итеративно стварајући решења за веће и веће подпроблеме коришћењем решења за мање подпроблеме. На пример, ако су вредности Ф31 и Ф30 већ познате, вредност Ф32 се може директно израчунати.

Поређење са другим техникама

Једна значајна карактеристика проблема који се може решити динамичким програмирањем је та што би он требао имати подпроблеме који се преклапају. Ово разликује динамичко програмирање од технике дељења и освајања, где није неопходно складиштење најједноставнијих вредности.

Слично је и са рекурзијом, јер се при израчунавању основних случајева коначна вредност може одредити индуктивно. Овај приступ одоздо према горе добро функционише када нова вриједност зависи само од претходно израчунатих вриједности.

Пример

Минимални кораци за постизање 1

За било који позитивни цели број "е" може се извести било који од следећа три корака.

- одузмите 1 од броја. (е = е-1).

- Ако је дељиво са 2, дели се са 2 (ако је% 2 == 0, онда је е = е / 2).

- Ако је дељив са 3, дели се са 3 (ако је е% 3 == 0, онда је е = е / 3).

На основу горњих корака, требало би утврдити минимални број ових корака који ће е довести до 1. На пример:

- Ако је е = 1, резултат: 0.

- Ако је е = 4, резултат: 2 (4/2 = 2/2 = 1).

- Када је е = 7, резултат: 3 (7-1 = 6/3 = 2/2 = 1).

Фокус

Могло би се помислити да увек бирамо корак који чини н што нижим и настављамо овако док не досегне 1. Међутим, може се видети да ова стратегија не делује овде.

На пример, ако је е = 10, кораци би били: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 корака). Међутим, оптимални облик је: 10-1 = 9/3 = 3/3 = 1 (3 корака). Стога се морају покушати сви могући кораци који се могу подузети за сваку вриједност н пронађене, одабирући минимални број ових могућности.

Све започиње рекурзијом: Ф (е) = 1 + мин {Ф (е-1), Ф (е / 2), Ф (е / 3)} ако је> 1, узимајући за основни случај: Ф (1) = 0. Имајући једначину рецидива, можете почети да кодирате рекурзију.

Међутим, може се видети да има подпроблеме који се преклапају. Поред тога, оптимално решење за одређени улаз зависи од оптималног решења његових подпроблема.

Као и код меморисања, где су решења потпроблема која су решена сачувана за каснију употребу. Или као у динамичном програмирању, започнете при дну, радећи свој пут до заданог е. Онда оба кода:

Меморизатион

Динамично програмирање одоздо према горе

Предност

Једна од главних предности употребе динамичког програмирања је та што убрзава обраду, јер се користе претходно израчунате референце. Пошто је то рекурзивна техника програмирања, она смањује линије кода у програму.

Ворациоус алгоритми вс динамично програмирање

Похлепни алгоритми су слични динамичком програмирању по томе што су оба алата за оптимизацију. Међутим, похлепни алгоритам тражи оптимално решење на сваком локалном кораку. Односно, тражи похлепни избор у нади да ће пронаћи глобални оптимум.

Стога похлепни алгоритми могу направити претпоставку која тада изгледа оптимално, али у будућности постаје скупа и не гарантује глобални оптималан.

С друге стране, динамичко програмирање проналази оптимално решење за подпроблеме и затим доноси информирани избор комбинујући резултате тих подпроблема да би се нашао најоптималније решење.

Недостаци

- Потребно је пуно меморије за складиштење израчунатог резултата сваког подпрограма, а да не будете у могућности да гарантујете да ли ће сачувана вредност бити коришћена или не.

- Много пута се излазна вредност похрањује без коришћења у следећим потпрограмима током извођења. То доводи до непотребне употребе меморије.

- У динамичком програмирању функције се називају рекурзивно. Тако се меморија сталка стално повећава.

Рекурзија вс динамичко програмирање

Ако имате ограничену меморију за покретање кода, а брзина обраде није проблем, можете користити рекурзију. На пример, ако развијате мобилну апликацију, меморија је веома ограничена за покретање апликације.

Ако желите да програм ради брже и нема ограничења меморије, пожељно је да користите динамичко програмирање.

Апликације

Динамичко програмирање је ефикасна метода решавања проблема за које се иначе може изгледати изузетно тешко решити у разумном року.

Алгоритми засновани на парадигми динамичког програмирања користе се у многим областима науке, укључујући многе примере вештачке интелигенције, од планирања решавања проблема до препознавања говора.

Алгоритми засновани на динамичком програмирању

Динамичко програмирање је прилично ефикасно и делује веома добро за широк распон проблема. Многи алгоритми се могу видети као похлепни програми алгоритама, као што су:

- Фибонацијеви бројеви.

- Куле из Ханоја.

- Сви парови краћих рута кроз Флоид-Варсхалл.

- Проблем са руксаком.

- Планирање пројеката.

- Најкраћи пут кроз Дијкстра.

- Контрола лета и контрола роботике.

- Проблеми математичке оптимизације.

- Временско дељење: закажите посао како бисте максимално искористили ЦПУ.

Фибонаццијев низ броја

Фибонаццијеви бројеви су бројеви пронађени у следећем низу: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, итд.

У математичкој терминологији, низ Фн Фибонаццијевих бројева је дефинисан формулом понављања: Ф (н) = Ф (н -1) + Ф (н -2), где је Ф (0) = 0 и Ф ( 1) = 1.

Одозго на доле приступ

У овом примјеру, низ претраживања са свим почетним вриједностима иницијализира се са -1. Кад год је потребно решење подпроблема, прво ће се претражити ова матрица претраге.

Ако је израчуната вредност тамо, та вредност ће се вратити. У супротном, резултат ће се израчунати да би се сачувао у претраживачком пољу да би се касније могло поново користити.

Приступ одоздо према горе

У овом случају, за исти Фибонаццијев низ прво се израчунава ф (0), затим ф (1), ф (2), ф (3), и тако даље. Тако се решења потпроблема граде одоздо нагоре.

Референце

1. Винеет Цхоудхари (2020). Увод у динамичко програмирање. Инсајдер за програмере Преузето са: девелоперинсидер.цо.
2. Алек Аллаин (2020). Динамичко програмирање у Ц ++. Ц Програмирање. Преузето са: цпрограмминг.цом.
3. После Академије (2020). Идеја динамичког програмирања. Преузето са: афтерацадеми.цом.
4. Анирудха Цхаудхари (2019). Динамичко програмирање и рекурзија - разлика, предности са примером. ЦСЕ Стацк. Преузето са: цсестацк.орг.
5. Цоде Цхеф (2020). Туториал за динамичко програмирање. Преузето са: цодецхеф.цом.
6. Програмиз (2020). Динамичко програмирање. Преузето са: програмиз.цом.