![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Лекція 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)
|