лькість обчислень. Це особливо корисно у випадках, коли число повторюваних подзадач експоненціально велике.
Метод динамічного програмування зверху - це просте запам'ятовування результатів вирішення тих подзадач, які можуть повторно зустрітися надалі. Динамічне програмування знизу включає в себе переформулювання складної задачі у вигляді рекурсивної послідовності простіших підзадач.
Оптимальна підструктура в динамічному програмуванні означає, що оптимальне рішення підзадач меншого розміру може бути використано для розв'язання вихідної задачі. Наприклад, найкоротший шлях в графі з однієї вершини (позначимо s) в іншу (позначимо t) може бути знайдений так: спочатку вважаємо найкоротший шлях з усіх вершин, суміжних з s, до t, а потім, враховуючи ваги ребер, якими s з'єднана з суміжними вершинами, вибираємо кращий шлях до t (через яку вершину найкраще піти). У загальному випадку ми можемо вирішити завдання, в якій присутній оптимальна підструктура, проробляючи наступні три кроки.
- Розбиття задачі на підзадачі меншого розміру.
- Знаходження оптимального рішення підзадач рекурсивно, проробляючи такий же трехшаговий алгоритм.
- Використання отриманого рішення підзадач для конструювання рішення вихідної задачі.
Підзадачі вирішуються розподілом їх на підзадачі ще меншого розміру і т.д., поки не приходять до тривіального нагоди завдання, розв'язуваної за константне час (відповідь можна сказати відразу). Наприклад, якщо нам потрібно знайти n!, То тривіальним завданням буде 1! =1 (або 0!=1).
Перекриваються підзадачі в динамічному програмуванні означають підзадачі, які використовуються для вирішення деякої кількості завдань (не однієї) більшого розміру.
Динамічне програмування користується наступними властивостями завдання:
- перекриваються підзадачі;
- оптимальна підструктура;
- можливість запам'ятовування рішення часто зустрічаються подзадач.
Динамічне програмування зазвичай дотримується двох підходів до вирішення завдань:
- спадний динамічне програмування: завдання розбивається на підзадачі меншого розміру, вони вирішуються і потім комбінуються для вирішення вихідної задачі. Використовується запам'ятовування для рішень часто зустрічаються подзадач.
- висхідне динамічне програмування: всі підзадачі, які згодом знадобляться для вирішення вихідної задачі прораховуються заздалегідь і потім використовуються для побудови рішення вихідної задачі. Цей спосіб краще спадного програмування в сенсі розміру необхідного стека і кількості виклику функцій, але іноді буває нелегко заздалегідь з'ясувати, рішення яких подзадач нам потрібно надалі.
Мови програмування можуть запам'ятовувати результат виклику функції з певним набором аргументів (мемоізація), щоб прискорити «обчислення по імені». У деяких мовах така можливість вбудована, а в деяких вимагає додаткових розширень.
Відомі серіальне динамічне програмування, включене у всі підручники з дослідження операцій, і не серіальне динамічне програмування (НСДП), яке в даний час слабо відомо, хоча було відкрито в 1960-х роках.
Звичайне динамічне програмування є приватним випад...
