Задача про прокладання найвигіднішого шляху між двома пунктами

Задача про прокладання найвигіднішого шляху

 між двома пунктами

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

Розглянемо конкретний приклад. Прямокутна область між двома пунктами А і В розбита на зони 5-ма рядками і 4-ма стовпцями, у кожній з яких зазначена вартість прокладання залізничної колії. Будемо рухатися від лівої нижньої зони до правої верхньої лише вгору і направо. Вислов­люючись алгоритмічною мовою, вважатимемо, що задано таб­лицю A[i,j] розмірністю n*m (n=5, т=4).

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

Перша ознака задачі динамічного програмування полягає в тому, що загальне розв'язування задачі можна розбити на окремі етапи, на кожному з яких розглядатиметься елемент таблиці A[i,j].

Стартовим буде елемент A[5,1] : його значення не змінюється. Розглянемо сусідні для нього елементи, у які може виконуватися перехід: A[4,1] і A[5,2]. Зміна значення елемента A[4,1] залежить лише від значення A[5,1] , і вартість такого переходу становитиме 3 + 10 = 13. Зміна значення елемента A[5,2] залежить також лише від значення A[5,1] , і його значення при переході від A[5,1] вправо становитиме 3 + 4 = 7.

Наступним для розгляду елементом може бути A[4,2] . До цього елемента можна перейти двома шляхами: або від лівого елемента A[4,1] , або від нижнього A[5,2] . Вартість першого переходу становитиме 13 + 1 = 14, а другого 7 + 1 = 8. Зрозуміло, що кращим є другий перехід. Запишемо нове перераховане значення A[4,2] у таблицю .

5	2	8	5
1	4	6	1
3	7	5	6
13	8	5	3
3	74	2	6

Продовжуючи за аналогією перерахунок значень елементів таблиці, будемо розглядати ті її елементи, для яких існує перерахований лівий і нижній елементи, а для крайніх елементів - відповідно лівий або нижній. На кожному етапі новим значенням елемента A[i,j] буде менше з двох можливих варіантів. Таким чином дійдемо до останнього елемента A[1,4]. Отримане значення елемента A[1,4] буде найменшою вартістю прокладання залізничної колії від населеного пункту А до населеного пункту B.

Найчастіше в подібних задачах цікавить не лише кінцевий результат, а й шлях його отримання. Чи можна визначити послідовність переходів по таблиці, яка приводить до отримання оптимальної відповіді? А саме як треба прокласти оптимальну за вартістю залізничну колію? Для цього потрібно відновити рух по таблиці у зворотному порядку. Згадаємо, як ми потрапили в клітинку таблиці A[1,4] і отримали її нове значення. Цей перехід було виконано з одного із сусідніх елементів (лівого або нижнього), що мав менше значення. Тому і зворотний шлях треба спрямувати на цей елемент. Для нашого прикладу A[1,3] = 29, A[2,4] = 23, тому переходимо до елемента A[2,4] . Для нього сусідніми, з яких ми могли зробити перехід, є A[2,3]= 24, A[3,4]= 22. Вибираємо перехід до елемента A[3,4].

Чи завжди отримається однозначна відповідь? Стосовно ре­зультуючого оптимального значення для елемента а_пт відпо­відь буде завжди одна. А от стосовно визначення шляху, що приводить до отримання цієї відповіді, не завжди. У наведеному прикладі під час вибору найменшого еле­мента жодного разу не траплялася ситуація, коли ці значення однакові. А якщо трапиться, то отримується розгалуження у визначенні оптимального шляху: їх уже буде два. У разі повторення подібної ситуації - чотири, а далі - вісім і т. д. Для визначення хоча б одного зі шляхів можна застосувати наведені вище міркування, але якщо задача вимагає визначення всіх можливих шляхів, то необхідно орга­нізувати рекурсивний алгоритм.

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

По-перше, задача була розбита на окремі етапи, яким відповідали зміни значень елементів заданої таблиці.

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

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

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

Перш ніж представити програмний код описаного алго­ритму, модифікуємо наші попередні міркування. Вони стосуються крайніх лівих і нижніх еле­ментів таблиці (за винятком найлівішого нижнього елемента). Можна почати перерахунок елементів усієї таблиці саме з них, оскільки значення кожного елемента першого стовпця залежить лише від значення його нижнього сусіда, а значення кожного елемента останнього рядка - від значення його лівого сусіда. Інший вихід із цієї ситуації: доповнимо задану таблицю зна­чень фіктивним стовпцем із номером 0 та фіктивним рядком із номером (п + 1) і встановимо значення цих елементів, як мак­симально можливі для визначеного типу. Таким чином, під час обробки будь-яких елементів таблиці A[i,j] вони будуть виклю­чені з наступного розгляду.

for i := n-1 downto 1 do    {Перерахунок значень крайнього лівого стовпця.}

   іnc(A[i,1], A[і+1,1]);     {або A[i,1] := A[i,1] +A[і+1,1]} for j := 2 to m do       {Перерахунок значень}

   inc(A[n,j], A[n,j- 1])        {крайнього нижнього рядка.}

for і := n - 1 downto 1 do   {Перерахунок решти елементів таблиці}

   for j := 2 to m do             {і збільшення їх значень}

       inc(a[i, j], min(a[i + 1, j], a[i, j - 1]));

Фрагмент програми, що виводить визначений результат, пе­редбачає лише один із можливих варіантів шляхів:

writeln (a[1,m]);                      {Виведення результуючого значення.)

i := 1; j := m;                           {Ініціалізація визначення самого шляху.)

while not((i = n) and not(j = 1)) do {Поки поточний елемент таблиці не є нижнім лівим,)

   begin

       write('i=',i,'    j=',j);                     {Виведення індексів поточного елемента}

       if A[i+1,j] < A[i,j-1]                       {перехід до меншого з двох сусідніх:}

          then inc(i)                                               { нижнього }

          else dec(j)                                               { або лівого }

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

Завдання

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

1. Знайти найменшу вартість прокладання залізничної колії від населеного пункту А до населеного пункту B (змінюючи дані в таблиці). (3 бали)

2. Знайти шлях для отримання найменшої вартості (з пункту В до пункту А, , наприклад: а[4,2], a[3,2], a[3,1] ). (3 бали)

3. Написати програму для визначення елементів матриці (те що в п.1). (3 бали)

4. Додати в програму визначення шляху (те що в п.2). (3 бали)

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

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

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

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

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

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

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

Ідею розв'язування задач динамічного програмування можна представити так. Спершу розглянемо деяку умовну задачу, процес розв'язку якої можна розбити на етапи і яка на кожному з цих етапів має три варіанти відповідей 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))

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

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