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

ВИКОРИСТАННЯ МЕТОДУ ДИНАМІЧНОГО ПРОГРАМУВАННЯ ДЛЯ РОЗВ’ЯЗАННЯ ОЛІМПІАДНИХ ЗАДАЧ

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

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

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

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

 

 

 Ідея методу динамічного програмування.

 

Динамічне програмування – один  із видів задач математичного програмування. Термін «динамічне» програмування не стільки визначає особливий клас задач, як метод їх розв’язання. При такому підході  задача розбивається на окремі підзадачі, розв’язки яких знаходяться послідовно один за одним,  використовуючи один і той же алгоритм. Після чого їх розв’язки збираються в один остаточний розв’язок, який і є розв’язком початкової задачі.

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

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

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

 

Задача «Мінімальний шлях у таблиці»

 

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

Потрібно знайти мінімальну суму, заплативши яку гравець може потрапити в правий нижній кут.

Вхідні дані

У першому рядку задано два числа N й M – розміри таблиці (1<=N<=100, 1<=M<=100). Потім іде N рядків по M чисел у кожній – розміри штрафів. за проходження через відповідні клітинки (числа від 0 до 100).

Вихідні дані

Виведіть мінімальну суму, витративши яку можна потрапити в правий нижній кут.

Приклад

Вхідні дані	Вихідні дані
5 5 1 1 1 1 1 3 100 100 100 100 1 1 1 1 1 2 2 2 1 2 1 1 1 1 1	11

 

Аналіз задачі та опис методу розв’язання.

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

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

Скористаємося методом динамічного програмування. Розіб’ємо задачу на простіші підзадачі та будемо розв’язувати їх в порядку зростання складності. Розглянемо на прикладі вхідних даних. Початкова таблиця має вигляд.

1	1	1	1	1
3	100	100	100	100
1	1	1	1	1
2	2	2	1	2
1	1	1	1	1

 

Виконаємо перезаповнення таблиці, зберігши до кожної комірки мінімальний штраф, який необхідно заплатити, щоб потрапити до даної комірки

1. Розглянемо випадок коли m=1:

1

1

1

1

1

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

1

2

3

4

5

2. Розглянемо випадок коли m=2. В перший рядок заповнено, як у попередньому випадку. 

1	2	3	4	5
3	100	100	100	100

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

1	2	3	4	5
4	102	103	104	105

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

1	1	1	1	1
4	102	103	104	105
5	6	7	8	9
7	8	9	9	11
8	9	10	10	11

Отже, для розв’язування даної задачі необхідно перезаповнити таблицю за наступним принципом:

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

for (int j=2; j<=n; j++)

       a[1][j]=a[1][j]+a[1][j-1];

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

for (int i=2; i<=m; i++)

       a[i][1]=a[i][1]+a[i-1][1];

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

for (int i=2; i<=m; i++)

for (int j=2; j<=n; j++)

         if (a[i][j-1]>a[i-1][j]) a[i][j]=a[i][j]+a[i][j-1];

   else a[i][j]=a[i][j]+a[i-1][j];

4. Вивести результат, який зберігається в нижній правій клітинці a[n][m].

 

Розглянемо ще одну задачу

 

Задача «Мінімальна кількість монет»

Грошова система деякої країни має монети номіналом c₁=1, c₂, c₃, ... c_n. Як видати суму S за допомогою найменшої кількості монет.

Вхідні дані. В першому рядку – сума S та кількість номіналів N, в другому значення номіналів в порядку зростання.

Вихідні дані. В першій стрічці – мінімальна кількість монет, в другій N чисел, кількість монет кожного номіналу.

Приклад вхідних та вихідних даних

Вхідні дані	Вихідні дані
22 3 1 5 15	4 2 1 1

 

Аналіз задачі та опис методу розв’язання.

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

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

Розглянемо інші вхідні дані:

1 10 15 – номінали монет

22 – сума

І при реалізації вищеописаного алгоритму ми отримаємо:

15+1+1+1+1+1+1+1

Всього 8 монет.

Хоча існує інший варіант 10+10+1+1, який складається з 4 монет.

Скористаємося методом динамічного програмування. Розглянемо серію підзадач. Якою найменшою кількістю монет можна подати суму R, використовуючи монети лише номіналом не більшим с_i. Відповіді підзадач будемо зберігати до прямокутної таблиці, рядки якої відповідають номіналам монет, стовпці – сумам.

1. Занесемо до таблиці кількість монет, які необхідні для подання суми, якщо в обігу  є монети лише номіналом c₁

S	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
C1=1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22

 

2. Розглянемо наступну підзадачу коли в обігу є монети номіналом c₁, c_2. Для заповнення клітинок скористаємося формулою:

S	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
C1=1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
C2=10	0	1	2	3	4	5	6	7	8	9	1	2	3	4	5	6	7	8	9	10	2	3	4

 

3. Розглянемо наступну підзадачу коли в обігу є монети номіналом c₁, c₂, c_3.

Для заповнення третьої стрічки скористаємося методом аналогічним до попереднього.

S	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
C1=1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
C2=10	0	1	2	3	4	5	6	7	8	9	1	2	3	4	5	6	7	8	9	10	2	3	4
C3=15	0	1	2	3	4	5	6	7	8	9	1	2	3	4	5	1	2	3	4	5	2	3	4

4. Залишилося лише вивести відповідь, яка зберігається в останньому заповненому елементі таблиці.

 

Задача «Монотонна підпослідовність»

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

Вхідні дані. Перший рядок містить довжину послідовності N (N<=5000), другий рядок N цілих чисел, кожне з яких не перевищую 50000.

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

Приклад вхідних та вихідних даних

Вхідні дані	Вихідні дані
9 5 3 1 6 8 7 2 4 9	5 6 8 9 28
10 5 3 4 6 7 2 4 9 8 7	3 5 6 7 9 30

Аналіз задачі та опис методу розв’язання.

Перебір всіх підпослідовностей практично неможливий. Значну кількість яких можна відкинути як не монотонні, але можливість такої оптимізації залежить від  виду послідовності. Приклад 1 із умови може привести до гіпотези: розпочати з першого елементу і включати всі елементи по порядку не порушуючи монотонність. Але цей алгоритм далеко не завжди дає правильну відповідь. Наприклад, якщо у вхідних даних третій елемент замінити на 4, то розв’язком буде інша підпослідовність: 3 4 6 8 9. Як бачимо включати чи не включати перший елемент залежить від наступних елементів.

Розіб’ємо задачу на підзадачі. Один із варіантів формулювання підзадачі: Яку найкращу (відповідно до умови) підпослідовність можна виділити із послідовностей a₁..a_m. Але в цьому випадку незрозуміло яким чином із розв’язку попередніх підзадач отримати розв’язок наступної. Сформулюємо підзадачі іншим чином. Яку найкращу підпослідовність можна виділити із послідовності a_m..a_n. Початкова задача не є однією із поставлених під задач, але розв’язавши всі підзадачі для m від n до 1 отримаємо розв’язок початкової задачі.

Для розв’язання необхідними є таблиці для збереження довжини підпослідовності – L, суми елементів – S та номера наступного елемента – next. Заповнення таблиць слід проводити починаючи з останнього елемента рухаючись до першого. Для останнього елемента довжина – 1, сума – останній елемент, наступний – 0 (закінчення підпослідовності). Для кожного елемента з номером m  виконувати пошук першого елемента таблиці А[j], який розміщений після  поточного і не менший за нього.

Якщо елемент знайдений, то:

L[m] =L[j]+1;

S[m]= S[j]+A[m];

next[m]= j;

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

Розглянемо на прикладі вхідних даних 2 з умови задачі. Після заповнення таблиці матимуть вигляд:

I	1	2	3	4	5	6	7	8	9	10
A	6	3	5	4	6	7	2	4	9	8
L-довжина	4	5	4	4	3	2	3	2	1	1
s-сума	28	30	27	26	22	16	15	13	9	8
next-наступний	5	3	5	5	6	9	8	9	0	0

Залишається вибрати найдовшу послідовність і вивести результат.

Принцип використання методу динамічного програмування.

 

Після того як розглянуто розв’язання задач методом динамічного програмування, сформулюємо принципи його використання

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

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

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

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

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

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

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

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

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

Метод, що описаний вище буде ефективним якщо задача задовольняє наступні вимоги:

1. В задачі можна виділити підзадачі аналогічної структури меншого розміру. Іноді вихідна задача не є однією із задач серії під задач, але її можна легко розв’язати маючи розв’язки однієї або кількох задач виділеної серії.
2. Серед виділених задач є задачі, які мають невеликий розмір і мають очевидний розв’язок.
3. Оптимальний розв’язок підзадачі більшого розміру можна побудувати на основі розв’язку підзадач меншого розміру.
4. При розв’язані задач великого розміру приходиться багаторазово розв’язувати задачі меншого розміру. Лише при такій умові варто запам’ятовувати проміжні результати.
5. Таблиці для запам’ятовування відповідей підзадач мають не дуже великий розмір.

Умови 1-3 виражають принципову можливість застосування даного методу до задачі, 4-5 – його доцільність.  Якщо ж виконуються умови 1-4, а 5 –ні, то або потрібно виділити іншу серію підзадач, або скористатись іншим підходом, або взагалі задача не має ефективного розв’язку.

 

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

Задача 1.

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

Вхідні дані

У першому рядку вхідного потоку записане число N - кількість гвіздків (2 <= N <= 100). У наступному рядку записано N чисел - координати всіх гвіздків (невід’ємні цілі числа, що не перевершують 10000).

Вихідні дані

У вихідний потік потрібно вивести одне число - мінімальну сумарну довжину всіх ниточок.

Приклад

№	Вхідні дані	Вихідні дані
1	6 3 4 12 6 14 13	5

 

 

Ідея розв’язання.

Після введення даних. Координати гвіздків відсортувати за ознакою не спадання. Підзадачі сформулювати наступним чином: Знайти оптимальний розв’язок для і гвіздків. Очевидно, що для 2 гвіздків розв’язком буде відстань між ними, для 3 сума відстаней між 1- 2 та 2 - 3. Кожен наступний обов’язково має бути з’єднаний з попереднім, при цьому не завжди попередні два мають бути з’єднані між собою. А тому, на кожному наступному етапі з номером і, розв’язок знаходиться як сума відстані між і та і-1 гвіздком та розв’язком отриманим на і-1 або і-2 етапі (вибрати менший)

Код програми

#include<iostream>

using namespace std;

int main()

{

    int n,k,i,z,a[101],b[101];

    cin>>n;

    for(i=1;i<=n;i++)

        cin>>a[i];

    for(i=1;i<=n;i++)

      for(k=i+1;k<=n;k++)

        if (a[i]>a[k])

            {z=a[k]; a[k]=a[i]; a[i]=z;}

    b[2]=a[2]-a[1];

    if (n>=3)

      {

        b[3]=a[3]-a[2]+b[2];

        for (i=4; i<=n; i++)

            if (b[i-2]<b[i-1])

                b[i]=a[i]-a[i-1]+b[i-2];

            else b[i]=a[i]-a[i-1]+b[i-1];

      }

     cout<<b[n];

}

Задача 2

Ігрове поле N × M заповнюється цілими числами, одне невід’ємне ціле число в кожній клітці. Ціль гри полягає в тому, щоб пройти по будь-якому дозволеному шляху від верхнього лівого кута до правого нижнього. Ціле число в кожній клітці вказує, якої довжини крок повинен бути з поточної клітки. Всі кроки можуть бути або праворуч або вниз. Якщо в результаті якого-небудь кроку гравець залишає межі поля, такий крок забороняється.

На малюнку 1 наведений приклад ігрового поля 3×4, де синім кольором відмічено положення початку, а зеленим - ціль. Малюнок  2 показує три можливих шляхи від початку до мети для розглянутого приклада ігрового поля, з вилученими проміжними числами.

2	1	1	2
3	2	1	44
3	1	1	0

Мал. 1

2
3			0

Мал.. 2

2		1
		1
		1	0

 

2		1	2
			0

 

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

Вхідні дані

Вхідний потік містить у першому рядку розміри поля N (1 ≤ N ≤ 70) і M (1 ≤ M ≤ 70). У наступних N рядках вхідного файлу, кожен з яких описує окремий рядок ігрового поля, записані через пробіл по M цілих чисел - довжини кроків із клітинок даного рядка.

Вихідні дані

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

Приклад

№	Вхідні дані	Вихідні дані
1	3 4 2 1 1 2 3 2 1 44 3 1 1 0	3

Ідея розв’язання

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

Код програми

#include<iostream>

using namespace std;

int main()

{

    int a[71][71], b[71][71];

    int i,j,n,m,k;

    long long L;

    cin>>n>>m;

    for (i=1;i<=n;i++)

    for (j=1;j<=m;j++)

    {

        cin>>a[i][j];

        b[i][j]=0;

    }

    b[1][1]=1;

    for (i=1;i<=n;i++)

    for (j=1;j<=m;j++)

    {

        if ((b[i][j]!=0)&&(a[i][j]!=0))

        {

            if (i+a[i][j]<=n)

                { b[i+a[i][j]][j]=b[i+a[i][j]][j]+b[i][j];}

            if (j+a[i][j]<=m)

                {b[i][j+a[i][j]]=b[i][j+a[i][j]]+b[i][j];}

        }

    }

    cout<<b[n][m];

}

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

 

1.   Караванова Т.П., Інформатика: методи побудови алгоритмів та їх аналіз:обчислювальні алгоритми: навчальний посібник для 9-10 кл. з поглибленим вивченням інформатики. – К. Генеза, 2009. – 336 с.
2.   Кармен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ / пер. с англ. Под ред. А. Шеня. – М.: МЦНМО, 2002. – 960 с.
3.   Порублев И.Н., Ставровский А. Б., Алгоритмы и программы. Решение олимпиадных задач – М.: ООО «И.Д. Вильямс», 2007. – 480с.