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

В програмирането динамичен е модел алгоритъм, който решава сложен проблем чрез разделяне го в подпроблеми, събиране на резултатите от тях да не се налага да се преизчисли резултатите.

Този график се използва, когато имате проблеми, които могат да бъдат разделени на подобни подпроблеми, така че техните резултати да бъдат използвани повторно. В по-голямата си част този график се използва за оптимизация.

Динамично програмиране. Подпроблеми, наслагвани в последователността на Фибоначи. Източник: Wikimedia commons, bg: Потребител: Dcoatzee, проследен от Потребител: Stannered / Public domain

Преди да разреши наличната подпроблема, динамичният алгоритъм ще се опита да проучи резултатите от предварително решените подпроблеми. Решенията на подпроблемите се комбинират, за да се постигне най-доброто решение.

Вместо да изчислявате една и съща подпроблема отново и отново, можете да съхранявате решението си в някаква памет, когато за първи път срещнете тази подпроблема. Когато се появи отново по време на решението на друга подпроблема, решението, което вече е запаметено в паметта, ще бъде взето.

Това е чудесна идея за определяне на времето на паметта, където използването на допълнително пространство може да подобри времето, необходимо за намиране на решение.

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

Следните съществени характеристики са това, с което трябва да имате проблем, преди да можете да приложите динамично програмиране:

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

Тази характеристика изразява, че проблемът с оптимизацията може да бъде решен чрез комбиниране на оптималните решения на вторичните проблеми, които го съставят. Тези оптимални подструктури се описват чрез рекурсия.

Например, в графика оптимална подструктура ще бъде представена в най-краткия път r, който преминава от върха s до върх t:

Тоест, по този най-кратък път r може да се вземе всяка междинна върха i. Ако r наистина е най-краткият маршрут, тогава той може да бъде разделен на под-маршрути r1 (от s до i) и r2 (от i до t), така че те от своя страна са най-късите маршрути между съответните върхове.

Следователно, за да се намерят най-кратките пътища, решението може лесно да се формулира рекурсивно, което прави алгоритъмът на Floyd-Warshall.

Припокриващи се подпроблеми

Пространството на подпроблемата трябва да е малко. Тоест всеки рекурсивен алгоритъм, който решава даден проблем, ще трябва да решава същите подпроблеми отново и отново, вместо да генерира нови подпроблеми.

Например, за да се генерира серията на Фибоначи, тази рекурсивна формулировка може да се счита: Fn = F (n - 1) + F (n - 2), като за основен случай се приема, че F1 = F2 = 1. Тогава ще имаме: F33 = F32 + F31 и F32 = F31 + F30.

Както можете да видите, F31 се разтваря в рекурсивните подредове както на F33, така и на F32. Въпреки че общият брой на подпроблемите е наистина малък, ако приемете рекурсивно решение като това, в крайна сметка ще решавате едни и същи проблеми отново и отново.

Това се взема предвид чрез динамичното програмиране, така че той решава всяка подпроблема само веднъж. Това може да се осъществи по два начина:

Подход отгоре надолу

Ако решението на всеки проблем може да бъде формулирано рекурсивно, като се използва решението на неговите подпроблеми и ако тези подпроблеми се припокриват, тогава решенията на подпроблемите могат лесно да бъдат запомнени или съхранявани в таблица.

Всеки път, когато се търси ново подпроблемно решение, таблицата ще бъде проверявана, за да се види дали е била решена преди това. В случай, че решение е запазено, то ще бъде използвано, вместо да се изчислява отново. В противен случай подпроблемата ще бъде решена, съхранявайки разтвора в таблицата.

Подход отдолу нагоре

След решаването на даден проблем рекурсивно се формулира по отношение на неговите подпроблеми, може да се направи опит за преформулиране на проблема по възходящ начин: първо, ще се опитаме да разрешим подпроблемите и да използваме техните решения, за да стигнем до решения за по-големите подпроблеми.

Това обикновено се прави и в таблична форма, като итеративно се генерират решения за по-големи и по-големи подпроблеми, като се използват решения за по-малките подпроблеми. Например, ако стойностите на F31 и F30 вече са известни, стойността на F32 може да бъде изчислена директно.

Сравнение с други техники

Една съществена особеност на проблем, който може да бъде решен чрез динамично програмиране, е, че трябва да има подпроблеми, които се припокриват. Това е, което отличава динамичното програмиране от техниката разделяне и завладяване, където не е необходимо да се съхраняват най-простите стойности.

Той е подобен на рекурсията, тъй като при изчисляване на базовите случаи крайната стойност може да се определи индуктивно. Този подход отдолу нагоре работи добре, когато нова стойност зависи само от предварително изчислени стойности.

пример

Минимални стъпки за достигане до 1

За всяко положително цяло число "e" може да се извърши която и да е от следните три стъпки.

- Извадете 1 от числото. (e = e-1).

- Ако е делимо на 2, то се дели на 2 (ако e% 2 == 0, тогава e = e / 2).

- Ако е делимо на 3, то се дели на 3 (ако e% 3 == 0, тогава e = e / 3).

Въз основа на стъпките по-горе трябва да се намери минималният брой от тези стъпки, за да се стигне до 1. Например:

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

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

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

фокус

Човек може да мисли, че винаги избира стъпката, която прави n възможно най-ниска и продължава така, докато стигне до 1. Въпреки това, може да се види, че тази стратегия не работи тук.

Например, ако e = 10, стъпките ще бъдат: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 стъпки). Оптималната форма обаче е: 10-1 = 9/3 = 3/3 = 1 (3 стъпки). Следователно, всички възможни стъпки, които могат да бъдат направени за всяка стойност на n намерени, трябва да бъдат изпробвани, като се избере минималният брой от тези възможности.

Всичко започва с рекурсия: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, ако e> 1, като се вземе за основен случай: F (1) = 0. Притежавайки уравнението на повторение, можете да започнете да кодирате рекурсията.

Вижда се обаче, че той има припокриващи се подпроблеми. Освен това оптималното решение за даден вход зависи от оптималното решение на неговите подпроблеми.

Както при запаметяването, където решенията на подпроблемите, които са решени, се съхраняват за по-късна употреба. Или както при динамичното програмиране, вие започвате отдолу, като работите по пътя си към даденото e. Тогава и двата кода:

Запаметяване

Динамично програмиране отдолу нагоре

предимство

Едно от основните предимства на използването на динамично програмиране е, че то ускорява обработката, тъй като се използват препратки, които са били предварително изчислени. Тъй като е рекурсивна техника на програмиране, тя намалява редовете на кода в програмата.

Променливи алгоритми срещу динамично програмиране

Алчните алгоритми са подобни на динамичното програмиране по това, че и двамата са инструменти за оптимизация. Алчният алгоритъм обаче търси оптимално решение на всяка локална стъпка. Тоест, търси алчен избор с надеждата да намери глобален оптимум.

Следователно алчните алгоритми могат да направят предположение, което изглежда оптимално по това време, но в бъдеще става скъпо и не гарантира глобален оптимален.

От друга страна, динамичното програмиране намира оптималното решение за подпроблемите и след това прави информиран избор, като комбинира резултатите от тези подпроблеми, за да намери действително най-оптималното решение.

Недостатъци

- Необходима е много памет за съхраняване на изчисления резултат на всяка подпроблема, без да можете да гарантирате, че запаметената стойност ще бъде използвана или не.

- Много пъти изходната стойност се съхранява, без изобщо да бъде използвана в следните подпрограми по време на изпълнение. Това води до ненужно използване на паметта.

- При динамично програмиране функциите се наричат ​​рекурсивно. Това поддържа паметта на стека постоянно да се увеличава.

Рекурсия срещу динамично програмиране

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

Ако искате програмата да работи по-бързо и да няма ограничения на паметта, за предпочитане е да използвате динамично програмиране.

Приложения

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

Алгоритмите, базирани на парадигмата за динамично програмиране, се използват в много области на науката, включително много примери за изкуствен интелект, от планиране на решаване на проблеми до разпознаване на речта.

Алгоритми, базирани на динамично програмиране

Динамичното програмиране е доста ефективно и работи много добре за широк спектър от проблеми. Много алгоритми могат да се разглеждат като алчни приложения за алгоритми, като например:

- Числови серии на Фибоначи.

- Кулите на Ханой.

- Всички двойки по-къси маршрути през Floyd-Warshall.

- Проблем с раницата.

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

- Най-краткият път през Dijkstra.

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

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

- Време за споделяне: планирайте работата, за да увеличите максимално използването на процесора.

Числови серии на Фибоначи

Числата на Фибоначи са числата, открити в следната последователност: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и т.н.

В математическата терминология последователността Fn на числата на Фибоначи се определя чрез формулата на повторение: F (n) = F (n -1) + F (n -2), където F (0) = 0 и F (1) = 1.

Подход отгоре надолу

В този пример масив за търсене с всички първоначални стойности се инициализира с -1. Винаги, когато е необходимо решението на подпроблема, тази матрица за търсене първо ще се търси.

Ако изчислената стойност е налице, тя ще бъде върната. В противен случай резултатът ще бъде изчислен за запазване в масива за търсене, така че да може да се използва повторно по-късно.

Подход отдолу нагоре

В този случай за същата серия на Фибоначи първо се изчислява f (0), след това f (1), f (2), f (3) и т.н. Така решенията на подпроблемите се изграждат отдолу нагоре.

Препратки

1. Vineet Choudhary (2020). Въведение в динамичното програмиране. Insider за разработчици. Взета от: developerinsider.co.
2. Алекс Алайн (2020). Динамично програмиране в C ++. C програмиране. Взета от: cprogramming.com.
3. След Академията (2020). Идея за динамично програмиране. Взета от: afteracademy.com.
4. Анируда Чаудхари (2019). Динамично програмиране и рекурсия - разлика, предимства с пример. CSE стек. Взета от: csestack.org.
5. Код готвач (2020). Урок за динамично програмиране. Взета от: codechef.com.
6. Programiz (2020). Динамично програмиране. Взета от: programiz.com.