Задача про прокладання найвигіднішого шляху
між
двома пунктами
Розглянемо задачу: Залізнична колія, що прокладається між двома
населеними пунктами А і В, має пройти через пересічену місцевість:
ліси, болота, річку, пагорби тощо. Відома вартість прокладання дороги через окремі
зони, на які можна розбити місцевість між цими населеними пунктами. Необхідно так прокласти дорогу,
рухаючись від пункту А до пункту В, щоб сумарні витрати
на її спорудження були мінімальними.
Розглянемо конкретний
приклад. Прямокутна область між двома пунктами А і В розбита на зони
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 бали)
Немає коментарів:
Дописати коментар