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

Приклад 2. Задача прокладення траси.

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

Знайти оптимальну трасу прокладки лінійних споруджень з пункту А в пункт В таким чином, щоб вартість лінійних споруджень була мінімальною.

Рішення. Схему розташування пунктів можна подати у вигляді сіткової моделі прямокутної форми, вузлами якої є пункти, що з'єднуються, а над дугами вказуються вартості прокладки ділянок траси між сусідніми пунктами. Отже на сітковій моделі ділянки траси можуть розташовуватися в двох напрямках (Y і Z).

Рішення задачі розбивається на 5 послідовних етапів.

При рішенні використовується алгоритм «зворотного прогону» від кінцевого пункту В до початкового пункту А. Під рішенням на кожному етапі розуміється вибір напрямку, по якому прокладається чергова ділянка траси. Вартість прокладки називається виграшем. Умовно оптимальний виграш позначається W*. Значення W* будемо записувати у відповідні вершини (вузли), а обрані напрямки – позначати стрілками.

Етап 5. Вершина (2, 2) Х*=Y W*=6

Вершина (3, 1) Х*=Z W*=10

Етап 4. Вершина (1, 2) Х*=Y W*=11

Вершина (2, 1) Х*=Z W*=17

Вершина (3, 0) Х*=Z W*=18

Етап 3. Вершина (1, 1) Х*=Z W*=23 -суміжна

Вершина (0, 2) Х*=Y W*=26

Вершина (2, 0) Х*=Z W*=22

Етап 2. Вершина (0, 1) Х*=Y W*=26

Вершина (1, 0) Х*=Y W*=30

Етап 1. Вершина (0, 0) Х*=Z W*=37 – оптимальний виграш.

Після знаходження величини оптимального виграшу визначається топологія траси:

А (0, 0) à (0, 1) à (1, 1) à (1, 2) à (2, 2) à B (3, 2)