Динамічне програмування – давайте розберемося

Американський математик Річард Беллман (1920–1984) придумав метод розв’язку широкого класу складних багатокрокових задач. Ідея методу полягає в тому, що на багатокрокову задачу треба подивитися «з кінця» і при знаходженні оптимальної стратегії поведінки на будь-якому кроці використовувати вже знайдені оптимальні стратегії на наступних кроках.

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

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

Спробуємо розібратися в цьому на перший погляд заплутаному принципі на простому прикладі. Нехай є квадратна дошка, наприклад 4x4, в клітинках якої записані числа. Нехай в лівому нижньому кутку дошки знаходиться фішка, яку на кожному кроці можна рухати на одну клітинку вгору або вправо. Позначимо ліву нижню клітинку Ст (старт), а праву верхню – Фн (фініш).

Потрібно провести фішку з клітинки Ст в клітинку Фн так, щоб сума всіх чисел в проміжних клітинках була найменшою.

Таблиця 1. Вихідні дані задачі

Для позначення клітинок в подальших міркуваннях введемо нотацію, аналогічну шаховій – рядки позначимо цифрами, а стовпці – літерами. Нехай тепер фішка знаходиться не в початковій клітинці А1, а в деякій іншій (наприклад, С3).

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

Позначимо функцію, яка ставить у відповідність клітинці число, що стоїть у ній, через f (наприклад, у даному випадку f (B2) = 5), а функцію, яка ставить у відповідність клітинці мінімальну суму на шляху з неї в D4 через g () (поки що ми не знаємо значення цієї функції, але хочемо дізнатися, і будемо поступово дізнаватися про це значення для різних клітинок, рухаючись справа-наліво та згори-вниз).

Розглянемо клітинки 4-го рядка. Очевидно, що з кожної з них існує єдиний шлях в D4, а саме – рухатися увесь час вправо. При цьому сума чисел у цій клітинці і в клітинках, які зустрінуться на подальшому шляху, дорівнює: для С4 – 1, для В4 – 2 + 1 = 3, для А4 – 7 + 2 + 1 = 10.

Оскільки з кожної з цих клітинок існує єдиний шлях в А4, то він і є оптимальним (з усіх можливих). Звідси g (C4) = 1, g (B4) = 3, g (А4) = 10. Аналогічно, з клітинок стовпця D існує єдиний шлях в D4, а саме – рухатися увесь час вгору. Обчислимо суми чисел для цих клітинок. Для D3 – 3, для D2 – 8 + 3 = 11, для D1 – 5 + 8 + 3 = 16. Звідси g (D3) = 3, g (D2) = 11, для g (D1) = 16.    

Внесемо в клітинки обчислені суми, а також стрілками покажемо напрямки руху в сусідні клітинки (для клітинок 4-го рядка це будуть стрілки вправо, а для стовпця D – стрілки вгору). Тепер звернемо увагу на клітинку С3.

Ми вже знаємо, яку суму ми додамо, якщо підемо вгору до С4 (g(С4) = 1) або якщо підемо вправо (g(D3) = 3). Оскільки ми хочемо отримати якомога меншу добавку, вибираємо рух вгору і вважаємо, що

g(C4) = f(C4) + min(g(C4), g(D3)) = 4 + 1 = 5.

Таблиця 2. Значення функції g і оптимальні траєкторії. Проміжні розрахунки

Нехай для деякої клітинки значення g ще невідоме, але воно відоме для «сусідок» даної клітинки зверху і справа. Тоді мінімальне значення суми по всіх траєкторіях, що починаються в даній клітинці дорівнює сумі числа, що стоїть у цій клітині, і мінімального з двох значень функції g – від сусідки зверху і сусідки праворуч.

g(клітинка) = f(клітинка) + min(g(сусідка зверху), g(сусідка праворуч)).

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

У таблиці 2 клітинками, до яких можна застосувати цю формулу, є В3 і С2:

g(B3) = 0 + min(3,5) = 0 + 3 = 3, вгору; g(C2) = 6 + min(5,11) = 6 + 5 = 11, вгору.

Після цього доступними для обчислення g стають клітинки А3, В2 і С1: g(A3) = 9 + min(10,3) = 9 + 3 = 12, вправо; g(В2) = 5 + min(3,11) = 5 + 3 = 8, вгору;
g(C1) = 7 + min(11,16) = 7 + 11 = 18, вгору.

Після цього доступними для обчислення g стають клітинки А2, В1 і, нарешті, А1: g(A2) = 4 + min(12,8) = 4 + 8 = 12, вправо; g(В1) = 3 + min(8,18) = 3 + 8 = 11, вгору; g (A1) = 0 + min (12,11) = 11, вправо.

Таблиця 3. Значення функції g і оптимальні траєкторії. Фінальні розрахунки

По таблиці 3, рухаючись по стрілках з А1 в D4, знаходимо оптимальну траєкторію: A1-B1-B2-B3-B4-C4-D4 і шукане мінімальне значення суми дорівнює 11.

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

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

Ханойські вежі

Головоломка з такою назвою була придумана у 1883 році французьким математиком Едуардом Люка (1842–1891). Назва була придумана самим Люка, щоб надати головоломці східно-містичний зміст і тим самим забезпечити їй кращі продажі. Зовні нанизані одне на одного кільця дійсно нагадують східну пагоду.

Сенс головоломки полягає в наступному.

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

Виникає два запитання – за яку мінімальну кількість ходів можна перемістити n кілець з одного стрижня на інший, і як власне це зробити?

Позначимо мінімальне число ходів для головоломки з n вежами через f(n). Нехай n = 1. Тоді очевидно, потрібно просто за один хід перемістити одне кільце з одного стрижня на інший. Таким чином, f(1) = 1.

Нехай ми вже навчилися переміщати n-1 кілець і шукана мінімальна кількість кроків становить f(n-1). Тоді нижнє (і найбільше) кільце не можна перемістити з А в С до тих пір, поки верхні кільця не будуть перекладені з А в В.

Таким чином, потрібно перемістити n-1 кільце з А в В (за припущенням, ми вміємо це робити, і для цього знадобиться f(n-1) кроків), перемістити нижнє кільце з А в С і перемістити n-1 кільце з В в С, використовуючи стрижень А, що звільнився, як проміжний (для цього знову ж знадобиться f(n-1) кроків). Таким чином, для f(n) справедливе рекурентне співвідношення: f(n) = 2f(n-1) +1.

Функція, що задовольняє цьому співвідношенню і початковій умові f(1) = 1 має вигляд: f(n)=2ⁿ–1.

Бажаючі подивитися розв’язок головоломки в динаміці можуть переглянути на youtube ролик під назвою «Задача про ханойську вежу».

Задача вибору найдовшої зростаючої підпослідовності

Нехай задано послідовність дійсних чисел   . Підпослідовністю даної послідовності назвемо будь-яку послідовність, яку можна отримати з даної викреслюванням елементів. З вихідної послідовності потрібно вибрати зростаючу підпослідовність максимальної довжини.

Розв’язок

Розглянемо послідовність s_k=a₁,a₂,…,a_k. Зростаючу підпослідовність даної послідовності назвемо безперспективною, якщо існує інша підпослідовність неменшої довжини і з небільшим останнім елементом, ніж дана, причому, принаймні, одна з  цих двох умов сувора.

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

Якщо на певному етапі серед підпослідовностей виявиться кілька з однаковою довжиною і однаковими останніми елементами, то слід залишити одну (будь-яку) з них, решту відкинути.

Приклад.

1,3,2,5,4,8,3,6,7

1-й крок. Єдина перспективна підпослідовність – 1

2-й крок. Маємо дві підпослідовності – 1 і 1,3

3-й крок.  Залишаємо 1, додаємо 1,2 і відкидаємо 1,3

4-й крок.  1;   1,2;   1,2,5

5-й крок.  1;  1,2;  1,2,4 (1,2,5 відкидаємо)

6-й крок.   1;   1,2;  1,2,4; 1,2,4,8

7-й крок.    1;  1,2;  1,2,3; 1,2,4,8

8-й крок.    1;   1,2;  1,2,3  1,2,3,6 (1,2,4,8 відкидаємо)

9-й крок.   1,2,3,6,7 – найдовша зростаюча підпослідовність.

Задача про рюкзак

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

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

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

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

Розглянемо приклад розв’язку задачі методом динамічного програмування.

Нехай є чотири предмети, їхні характеристики задано в таблиці:

Нехай місткість рюкзака дорівнює 10. Кожному способу заповнення рюкзака будемо ставити у відповідність пару чисел, де перше число означає сумарну вагу, а друге – сумарну цінність. Наприклад, якщо в рюкзаку лежить перший і другий предмети, то їхня сумарна вага дорівнює 2 + 4 = 6, а сумарна цінність – 4 + 5 = 9. Такому заповненню відповідає запис (6,9).

Будемо розв’язувати задачу покроково. На нульовому кроці є тільки один спосіб заповнення рюкзака – в ньому немає предметів, позначаємо це (0,0). На кожному кроці будемо додавати по одному предмету і будемо до вже знайдених способів заповнення рюкзака додавати нові, що виникають у результаті додавання нового предмета. Зробити це дуже просто.

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

Наприклад, нехай уже знайдений спосіб заповнення (4,5). Намагаємося додати третій предмет (з вагою 5 і цінністю 9). Тоді сумарна вага предметів дорівнюватиме 4 + 5 = 9, що не перевищує місткості рюкзака, яка становить 10.

Таким чином, виникає додатковий спосіб заповнення (9,14). Якщо ж спробуємо додати до способу (4,5) четвертий предмет (з вагою 8 і цінністю 11), то сумарна вага предметів складе 4 + 8 = 12, що перевищує місткість рюкзака. В цьому випадку не пишемо нічого. Після того, як на черговому кроці до наявних способів були додані нові, впорядкуємо всі способи в порядку зростання ваги і відкинемо безперспективні.

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

0-й крок - (0,0)

1-й крок - (0,0), (2,4)

2-й крок - залишаються два старих способи (0,0), (2,4), і ще в результаті додавання 2-го предмета виникає два нових – (4,5) і (6,9).

Записуємо список способів: (0,0), (2,4), (4,5), (6,9).

3-й крок – до множини способів 2-го кроку (0,0), (2,4), (4,5), (6,9) в результаті додавання 3-го предмета додається ще три способи, а саме: (5,9), (7,13), (9,14). Зауважимо, що варіант заповнення рюкзака (6,9) є безперспективним, оскільки існує спосіб (5,9). Відкидаємо цей безперспективний спосіб і впорядковуємо інші в порядку зростання ваги:

(0,0), (2,4), (4,5), (5,9), (7,13), (9,14).

4-й крок. У результаті додавання 4-го предмета виникає ще два способи – а саме (8,11) і (10,15). З усіх способів максимальна цінність дорівнює 15, і вона досягається, коли в рюкзаку лежать 1-й і 4-й предмети.

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

С.І. Доценко, кандидат фізико-математичних наук, доцент факультету комп’ютерних наук та кібернетики КНУ імені Тараса Шевченка

За темою: Кібернетіка

№9, 2024

Віктор Михайлович Глушков – вчений світової слави

№9, 2024

Віталій Павлович Деркач: Від «розумних машин» до молекулярних комп’ютерів

№8, 2024

Основоположник вітчизняного комп'ютеробудування