Загальна задача динамічного програмування

Загальна задача динамічного програмування

Після розгляду найтиповіших задач динамічного програмування, простіше  сформулювати його основні ідеї. Почнемо із формулювання загальної задачі динамічного програмування в алгоритмічних термінах.

Нехай розв'язується деяка задача S. Для її розв'язання зада­ні вхідні дані S_o, що надалі оброблятимуться. У результаті за­стосування до цих вхідних даних розробленого оптимізаційного алгоритму U її буде перетворено у вигляд S_n. Процес виконання алгоритму можна представити як деяку функцію W(U), що дає кілька варіантів розв'язків. Оскільки задача динамічного програмування є задачею оптимізаційною, то серед усіх отриманих варіантів відповідей треба вибрати найкращий W*(U).

Методика розв'язування задач динамічного програмування бу­ла запропонована Р.Беллманом у 1955 р. і полягає в наступному.

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

Кожний з етапів є окремою підзадачею поставленої загаль­ної задачі і розв'язується одним і тим самим розробленим оптимізаційним алгоритмом. Однак вибір розв'язків кожної на­ступної підзадачі залежить від розв'язків попередньої, і тому їх можна назвати залежними. Будемо вважати, що на першому етапі вхідна інформація S_o перетворюється алгоритмом U у вигляд S1. Тепер при виконанні наступного етапу вхідними даними для нього буде вже S1. При цьому застосування алго­ритму на даному етапі може дати багато варіантів розв'язків w₁(u), серед яких ми вибираємо ті, які надалі приведуть до найкращого кінцевого результату, тобто є перспективними. Позначимо їх w*₁(u). Аналогічно будуть перетворюватися вхідні дані на наступних етапах S₂, ..., S_n-1. Отже, оптимізація всієї задачі зводиться до визначення оптимальних результатів застосування розробленого алгоритму w*_i(u) на кожному окре­мому етапі.

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

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

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

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

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

Щоб знайти оптимальну стратегію, тобто визначити шуканий розв'язок задачі, необхідно пройти всю послідовність етапів у зворотному порядку. Теоретично ця послідовність виглядає так: на першому етапі в якості оптимальної стратегії необхідно взяти знайдену умовну оптимальну стратегію. На другому етапі визначити стан інформації S1*, яка отримується для задачі в результаті вибору умовної оптимальної стратегії и*_1. Цей стан визначає знайдена умовна оптимальна стратегія и(0)_2, яку тепер вважатимемо оптимальною і т. д. У результаті цього знаходимо розв'язок задач, тобто максимально можливий виграш та оптимальну стратегію U*, що включає в себе умовну оптимальну стратегію на окремих етапах: U* = (и*₁, и*₂, ... , и*_n).

Зробимо ще одне зауваження: у будь-якій задачі динамічно­го програмування «початок» і «кінець» можна поміняти місця­ми. Це повністю рівнозначне описаній вище методиці щодо ви­конуваних розрахунків, однак при такому підході виникають незручності щодо пояснення ідеї методу: простіше аргументу­вати, посилаючись на умови, що «вже склалися» до початку да­ного кроку, ніж на ті, які ще «попереду» цього кроку. По суті, обидва підходи абсолютно рівносильні і досить умовні. При­кладом цього може служити перша розглянута задача про прокладання найвигіднішого шляху між двома пунктами. Ми її розв'язували від пункту А до пункту В, а можна було навпа­ки. При цьому результуюча відповідь була б однаковою.

У кожній розглянутій задачі визначалася оцінка ефектив­ності роботи розробленого для її розв'язання алгоритму. І справді, оцінку менше ніж О(пт) для задач динамічного про­грамування отримати неможливо, оскільки у кращому разі нам доводиться хоч один раз обробляти кожний елемент таб­лиці розмірністю п*т. Але трапляються й об'ємніші щодо часу виконання задачі. З цим ми ознайомилися в задачі про роз­поділ ресурсів. Ученими доведено, що максимальною оцінкою ефективності роботи алгоритмів, які базуються на методі ди­намічного програмування, можна вважати О(пт log(nm)).

Критерії застосування задач динамічного програмування

Як розпізнати задачу динамічного програмування?

Насамперед варто зазначити, що найкращим критерієм «впізнавання» задач динамічного програмування є власний значний досвід у розв'язуванні таких задач. Разом з тим, можна дати й деякі поради.

Спочатку треба розглянути питання про можливість роз­биття задачі на етапи, що найчастіше міститься вже у форму­люванні самої задачі, як, наприклад, дослідження (аналіз) фінансування одного підприємства по роках або кількох окремих підприємств в економічних задачах. Але іноді таке розбиття необхідно робити штучно, як, наприклад, у задачі про прокладання найвигіднішого шляху. Кількість етапів у задачі найчастіше визначається так само в умові задачі. Якщо ж їх до­водиться визначати самостійно, то необхідно орієнтуватися на тип змінних, обумовлених у задачі, на критерії визначення кінцевого результату. Не можна забувати, що в разі збіль­шення кількості етапів значно зростає об'єм розрахунків, що у свою чергу впливає на загальний час виконання алгоритму.