Знаходження най коротшої відстані між двома вузлами на мережі доріг

Це одна з перших транспортних задач, що були вирішені методи ДП[12].

Нехай відома мережа автомобільних доріг, яка з'єднує пункти А і Б. Ця мережа складається із сукупності вузлів і з'єднуючих їх доріг. Поставимо задачу пошуку найкоротшого шляху між пунктами А і Б (див. рис.7.1).

Рис.7.1 До визначення найкоротшого шляху

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

VІ-й крок. На цьому кроці є одна умовна крапка. Припустимо, що ми вже потрапили в цю крапку (незалежно як) і будемо намагатися потрапити в кінцеву крапку Б. Є тільки один шлях, тому це і буде найкоротша відстань =12 (оцінку цієї вузлової крапки змінимо 12).

V - крок. На цьому кроці маємо 3 крапки. Якщо ми потрапимо (незалежно як) у верхню крапку, то найкоротша відстань до Б буде дорівнює 13,для другої крапки 10, для третьої - 9, покажемо стрілками напрямок руху в крапку В.

IV - крок. На цьому кроці маємо дві крапки. З верхньої країн виходить три напрямки. Необхідно вибрати оптимальний напрямок. Якщо рухатися в напрямку крапки 13, то відстань до крапки Б, буде 6+(13)=19.

Якщо рухатися в напрямку крапки з оцінкою (10), то відстань до неї буде дорівнює 5 + (10) = 15; а якщо в напрямку крапки з оцінкою (9), 8+(9)=17 нас цікавить напрямок, який дасть мінімальну оцінку, тому змінимо оцінку цієї крапки, рівної мінімальній з перелічених (15). Аналогічно знаходимо оцінку для другої крапки кроку IV 6+(10)=16; 2+(9)=11; 7+(12)=13.

Мінімальне значення в напрямку крапки (9) далі буде дорівнює (11).

Оптимальні значення позначимо стрілками.

III-крок. На цьому кроці одна вузлова крапка з якої виходить три напрямки

3+(13)=16; 4+(10)=14; 11+(9)=20.

Мінімальну оцінку (14) одержимо рухаючи у вузлову крапку з оцінкою (10).

II – крок. На цьому кроці 3 вузлові крапки:
Для верхньої: 7+(14)=21;

Для другої: 5+(14)=19; 9+(15)=24; 10+(П)=21. мінімальна оцінка (19) у напрямку крапки з оцінкою (14;

Для третьої: 4+(15)=19; 5+(11)=16.

Умовно - оптимальної є оцінка (13) і умовно - оптимальним управлінням

- рух у кутову крапку з оцінкою (11).

І – крок містить 4 можливі напрямки:

3+(21)=24; 6+(14)=20; 4+(19)=23; 8+(16)=24.

Мінімальна сума (20) у напрямку крапки з оцінкою (14).

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

А→(14) →(10) →В.

Варто мати на увазі, що потрапивши в будь-яку крапку, ми завжди знайдемо найкоротший маршрут у Б. Наприклад, із крапки (16) таким маршрутом буде: (16) → (11) → (9) → Б, з відстанню, яка дорівнює 11 + 15=26.

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

Дата добавления: 2014-12-29