В този урок ще научите какво е динамично програмиране. Също така ще намерите сравнението между динамичното програмиране и алчните алгоритми за решаване на проблеми.
Динамичното програмиране е техника в компютърното програмиране, която помага ефективно да се реши клас проблеми, които имат припокриващи се подпроблеми и оптимално свойство на подструктурата.
Такива проблеми включват многократно изчисляване на стойността на едни и същи подпроблеми, за да се намери оптималното решение.
Пример за динамично програмиране
Вземете случая на генериране на последователността на Фибоначи.
Ако последователността е F (1) F (2) F (3) … F (50), тя следва правилото F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Забележете как има припокриващи се подпроблеми, трябва да изчислим F (48), за да изчислим както F (50), така и F (49). Това е точно такъв алгоритъм, при който динамичното програмиране блести.
Как работи динамичното програмиране
Динамичното програмиране работи, като съхранява резултата от подпроблеми, така че когато се изискват техните решения, те са под ръка и не е необходимо да ги преизчисляваме.
Тази техника за съхраняване на стойността на подпроблемите се нарича запомняне. Като запазваме стойностите в масива, спестяваме време за изчисления на подзадачи, на които вече сме попаднали.
var m = map (0 → 0, 1 → 1) функция fib (n), ако ключът n не е в картата mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Динамичното програмиране чрез мемоизиране е подход отгоре надолу към динамичното програмиране. Чрез обръщане на посоката, в която работи алгоритъмът, т.е. като стартираме от основния случай и работим към решението, ние също можем да реализираме динамично програмиране отдолу нагоре.
функция fib (n), ако n = 0 върне 0 иначе var prevFib = 0, currFib = 1 повторение n - 1 пъти var newFib = prevFib + currFib prevFib = currFib currFib = newFib връщане на текущия Fib
Рекурсия срещу динамично програмиране
Динамичното програмиране се прилага най-вече към рекурсивни алгоритми. Това не е случайно, повечето проблеми с оптимизацията изискват рекурсия и за оптимизация се използва динамично програмиране.
Но не всички проблеми, които използват рекурсия, могат да използват динамично програмиране. Освен ако няма наличие на припокриващи се подпроблеми, като при проблема с последователността на Фибоначи, рекурсията може да достигне до решението само с помощта на разделяй и владей подход.
Това е причината рекурсивният алгоритъм като Merge Sort да не може да използва динамично програмиране, тъй като подпроблемите не се припокриват по никакъв начин.
Алчни алгоритми срещу динамично програмиране
Алчните алгоритми са подобни на динамичното програмиране в смисъл, че и двете са инструменти за оптимизация.
Алчните алгоритми обаче търсят локално оптимални решения или с други думи алчен избор, с надеждата да намерят глобален оптимум. Следователно алчните алгоритми могат да направят предположение, което изглежда оптимално по това време, но става скъпо и не гарантира глобален оптимум.
Динамичното програмиране, от друга страна, намира оптималното решение за подпроблемите и след това прави информиран избор да комбинира резултатите от тези подпроблеми, за да намери най-оптималното решение.
