Меню Закрити

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

Припустимо, ви виконуєте обчислення, використовуючи певний набір вхідних даних (Input). Ви не знаєте, що отримали певний вихід (Output), коли певний вхід. Тож ви робите перерахунок кожного разу.

Але в чому тут проблема? Річ у тому, що ваш дорогоцінний час втрачено. Це можна легко вирішити, зберігаючи записи, які створюють карту раніше обчислених результатів. Зокрема, використовуючи відповідну структуру даних. Наприклад, можна зберігати вхід як ключ, а вихід — як значення.

Той, хто не пам’ятає минулого, приречений його повторювати. ~ Динамічне програмування

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

Занурення в динамічне програмування

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

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

Наприклад, числа Фібоначчі 0,1,1,2,3,5,8,13,… мають простий опис, де кожен член пов’язаний із двома членами перед ним. Якщо F(n) n-й член цієї послідовності, то F(n) = F(n-1) + F(n-2). Це називається рекурсивною формулою або рекурентним відношенням. Для обчислення наступного члена потрібно обчислювати попередні члени.

*Оскільки ми двічі звертаємося до обчислення функції fib(1), ми могли б зберегти перший отриманий результат і використати його знову в наступному обчисленні.

Більшість задач динамічного програмування можна поділити на два типи:

  • задачі оптимізації;
  • комбінаторні задачі.

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

Підхід до розв’язання: згори вниз або знизу вгору

Існують два основних способи вирішення задачі:

Згори вниз: ви починаєте з верхівки, вирішуючи задачу, розбиваючи її. Якщо бачите, що задачу вже розв’язано, то просто повертаєтеся до збереженої відповіді. Це називається мемоїзація (Memoization — запам’ятовування результатів).

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

Що стосується ітерації та рекурсії, то знизу вгору використовують ітерацію, а згори вниз використовується рекурсія.

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

Спрощений підхід:

  • робить запити О(2^n );
  • не використовує додаткову пам’ять для зберігання результатів

Підхід динамічного програмування:

– робить запити О(n);

– використовує додатковий простір / пам’ять для зберігання результатів

Тут проводиться порівняння між спрощеним підходом та підходом ДП. Можете бачити різницю щодо складності обох.

Мемоїзація: не забувайте

Jeff Erickson у своїх нотатках так висловлюється щодо чисел Фібоначчі:

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

Джерело

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

Мемоїзація спирається на техніку кешування та повторного використання раніше обчислених результатів.

Якщо ви використовуєте мемоїзацію для вирішення задачі, ви зберігаєте схему вже розв’язаних підзадач (як згадувалося вище про відображення ключа й значення). Ви робите це “згори вниз” у тому сенсі, що ви вирішуєте “верхню” задачу спочатку (яка зазвичай виконує рекурсію донизу, щоб розв’язати підзадачі).

Псевдокод для мемоїзації:

* Якщо тут немає шуканого значення для n, тоді розраховуємо його

Тож, використовуючи рекурсію, ми виконуємо це з додатковими витратами пам’яті (тобто lookup — пошук) для зберігання результатів. Якщо є значення, збережене в lookup, ми повертаємо його напряму або додаємо його до пошуку для цього конкретного індексу.

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

Якщо бажаєте отримати додаткові візуалізації для мемоїзації, можете переглянути це відеo.

* угорі трохи правіше центру: перший раз треба розрахувати та мемоїзувати

У верхньому правому кутку: мапінг мемоїзації

Лівий нижній кут: другий раз ми можемо використовувати його попередньо розраховане значення, що зберігається в пам’яті

По центру під стрілкою: те саме для Fn-3

Правий нижній кут: нехай y буде певною величиною після обчислення

У порядку згори вниз.

Табуляція: заповнення в табличній формі

Тільки-но ми побачимо, що масив (мемоїзоване рішення) заповнено, можемо замінити рекурсію простим циклом, який спрямовано заповнює масив по черзі, а не покладатися на складну рекурсію, яка робитиме це для нас “випадково”.

Джерело

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

Псевдокод для табуляції:

*У лівому верхньому кутку: знизу вгору

По центру в квадратних дужках: не треба знову розраховувати fib(1)

Нижче по центру біля fib(0), fib(1), fib(2) тричі: розраховується

Псевдокод із деревом Фібоначчі

Як ви можете побачити, псевдокод (справа на схемі) робить ітерацію (тобто циклічно закінчується до кінця масиву). Він просто починається із fib(0), fib(1), fib(2),… Отже, із використанням табуляції можна усунути необхідність рекурсії та просто повернути результат за допомогою циклічного перебору елементів.

Зазираючи в історію

Річард Беллмен був людиною, що стояла за цим поняттям. Він придумав це, коли працював у корпорації RAND у середині 1950-х років. Причина того, що він вибрав цю назву “динамічне програмування”, полягала в тому, щоб приховати математичну роботу, яку він зробив для цього дослідження. Він боявся, що його боси будуть проти або поставляться негативно до будь-яких математичних досліджень.

Отже, слово “програмування” — це лише позначення, аби пояснити, що це був старомодний спосіб планування або розробки графіків, як правило, шляхом заповнення таблиці (переважно динамічним, а не лінійним способом) протягом певного часу, а не за раз.

Якщо ви знайшли помилку, будь ласка, виділіть фрагмент тексту та натисніть Ctrl+Enter.

0

Повідомити про помилку

Текст, який буде надіслано нашим редакторам: