ОСНОВИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

ОСНОВИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

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

Як і лінійне програмування, динамічне програмування визначає особливий тип задач і методику їх розв'язування.

Для пояснення відмінності між методиками розв'язування задач лінійного та динамічного програмування введемо поняття етапу їх виконання.

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

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

Ідею розв'язування задач динамічного програмування можна представити так. Спершу розглянемо деяку умовну задачу, процес розв'язку якої можна розбити на етапи і яка на кожному з цих етапів має три варіанти відповідей v1, v2, v3. Щоб не загубити жодного кінцевого розв'язку задачі, потрібно було б на кожному  наступному, другому, етапі розв'язати задачу для кожної з цих варіантів відповідей. Якщо цей процес продовжувати далі, то на останньому, n-му, етапі ми будемо мати справу з 3^(n-1) варіантами відповідей. Оскільки розглядається задача оптимізації, яка вимагає визначення максимального чи мінімального значення серед усіх 3^(n-1) отриманих відповідей, то для скорочення цієї кількості на кожному етапі варто відкидати ті проміжні вааріанти відповідей, які не є оптимальними, а значить, і не приведуть до оптимального кінцевого результату. Отже, задачі динамічного програмування розбиваються на окремі залежні одна від одної підзадачі, а звідси випливає, що неоптимальний розв'язок однієї з підзадач у жодному разі не дасть оптимального кінцевого розв'язку.

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

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

Етапи	1	2	3	...	n
Варіанти
1	v1(1)	v1(2)=опт(v1(1), v2(1), v3(1))	v1(3)=опт(v1(2), v2(2), v3(2))		v1(n)=опт(v1(n-1), v2(n-1), v3(n-1))
2	v2(1)	V2(2)=опт(v1(1), v2(1), v3(1))	V2(3)=опт(v1(2), v2(2), v3(2))		V2(n)=опт(v1(n-1), v2(n-1), v3(n-1))
3	v3(1)	V3(2)=опт(v1(1), v2(1), v3(1))	V3(3)=опт(v1(2), v2(2), v3(2))		V3(n)=опт(v1(n-1), v2(n-1), v3(n-1))

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

Далі розглянемо кілька найтиповіших задач динамічного програмування.