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

Динамічного програмування є моделлю алгоритм , який вирішує складну проблему шляхом ділення її на підзадачі, зберігання результатів їх , щоб уникнути необхідності перерахувати результати.

Цей графік використовується, коли у вас є проблеми, які можна розділити на подібні підпрограми, щоб їх результати можна було повторно використовувати. Здебільшого цей графік використовується для оптимізації.

Динамічне програмування. Підпрограми, накладені в послідовності Фібоначчі. Джерело: Wikimedia commons, en: Користувач: Dcoatzee, відстежується користувачем: Stannered / Public domain

Перш ніж вирішити наявну підпроблему, динамічний алгоритм спробує вивчити результати раніше розв’язаних підпроблем. Рішення підпроблем поєднуються для досягнення найкращого рішення.

Замість того, щоб обчислювати одну і ту ж підпроблему знову і знову, ви можете зберігати своє рішення в деякій пам'яті, коли ви вперше зіткнетеся з цією підпроблемою. Коли він знову з’явиться під час вирішення іншої підпрограми, буде прийнято рішення, яке вже зберігається в пам'яті.

Це чудова ідея для фіксації часу пам’яті, коли використання додаткового простору може покращити час, необхідний для пошуку рішення.

Особливості динамічного програмування

Наступні суттєві характеристики - це те, з чим ви повинні мати проблеми, перш ніж буде застосовано динамічне програмування:

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

Ця характеристика виражає те, що оптимізаційну задачу можна вирішити, комбінуючи оптимальні рішення вторинних задач, які її складають. Ці оптимальні підструктури описуються рекурсією.

Наприклад, на графіку буде представлена ​​оптимальна підструктура в найкоротшому шляху r, який йде від вершини s до вершини t:

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

Тому, щоб знайти найкоротші шляхи, рішення можна легко сформулювати рекурсивно, що і робить алгоритм Флойда-Варшала.

Підпрограми, що перекриваються

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

Наприклад, для створення ряду Фібоначчі ми можемо розглянути цю рекурсивну формулювання: 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).

Виходячи з наведених вище кроків, слід знайти мінімальну кількість цих кроків, щоб довести e до 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 + хв {F (e-1), F (e / 2), F (e / 3)}, якщо e> 1, приймаючи за основний випадок: F (1) = 0. Маючи рівняння повторення, ви можете почати кодувати рекурсію.

Однак видно, що в ньому є підпрограми, що перекриваються. Крім того, оптимальне рішення для заданого входу залежить від оптимального рішення його підпроблем.

Як і при запам'ятовуванні, де розв'язані підпрограми зберігаються для подальшого використання. Або як у динамічному програмуванні, ви починаєте внизу, працюючи в напрямку до заданого e. Тоді обидва коди:

Запам'ятовування

Динамічне програмування знизу вгору

Перевага

Однією з головних переваг використання динамічного програмування є те, що воно прискорює обробку, оскільки використовуються попередньо розраховані посилання. Оскільки це метод рекурсивного програмування, він зменшує рядки коду в програмі.

Ненасичені алгоритми проти динамічного програмування

Жадібні алгоритми схожі на динамічне програмування тим, що вони є обома інструментами для оптимізації. Однак жадібний алгоритм шукає оптимальне рішення на кожному локальному кроці. Тобто вона прагне жадібного вибору в надії знайти глобальний оптимум.

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

З іншого боку, динамічне програмування знаходить оптимальне рішення для підпроблем, а потім робить усвідомлений вибір, комбінуючи результати цих підпроблем, щоб фактично знайти найбільш оптимальне рішення.

Недоліки

- Для збереження обчисленого результату кожної підпрограми потрібно багато пам'яті, не маючи змоги гарантувати, що збережене значення буде використано чи ні.

- Багато разів вихідне значення зберігається, не використовуючи ніколи в наступних підпрограмах під час виконання. Це призводить до зайвого використання пам'яті.

- У динамічному програмуванні функції викликаються рекурсивно. Завдяки цьому пам'ять стеку постійно збільшується.

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

Якщо у вас обмежена пам'ять для запуску коду, швидкість обробки не викликає занепокоєння, ви можете використовувати рекурсію. Наприклад, якщо ви розробляєте мобільний додаток, для запуску програми пам'ять дуже обмежена.

Якщо ви хочете, щоб програма запускалася швидше і не мала обмежень на пам'ять, бажано використовувати динамічне програмування.

Програми

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

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

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

Динамічне програмування є досить ефективним і дуже добре працює для широкого кола проблем. Багато алгоритмів можна розглядати як жадібні програми алгоритмів, такі як:

- ряд чисел Фібоначчі.

- Вежі Ханої.

- Всі пари коротших маршрутів через Флойд-Варшалл.

- Проблема з рюкзаком.

- Планування проекту.

- Найкоротший шлях через Дейкстру.

- Управління польотом і робототехніка.

- Задачі математичної оптимізації.

- Часовий обмін: заплануйте завдання, щоб максимально використовувати CPU.

Ряд чисел Фібоначчі

Числа Фібоначчі - це числа, знайдені в такій послідовності: 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. Програміз (2020). Динамічне програмування. Взято з: programiz.com.