Задача про найкоротший шлях з урахуванням додаткових обмежень

Тема 2 Визначення найкоротших відстаней на транспортній мережі

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

При цьому транспортна мережа представляється у вигляді сукупності окремих елементів: вершин та дуг, що їх поєднують. Для кожної дуги відома її довжина. Дуга може бути як спрямованою (тобто мати певний напрямок руху), так і неспрямованою. В якості вершин транспортної мережі можуть наприклад виступати залізничні станції, а в якості дуг – дільниці, що їх поєднують. У загальному випадку задача пошуку найкоротших відстаней на транспортній мережі полягає у пошуку найкоротшої відстані із однієї заданої вершини в іншу задану вершину.

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

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

Існують різні постановки задачі про найкоротший шлях:

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

• Задача про найкоротший шлях між заданою парою вершин. Потрібно знайти найкоротший шлях із заданої вершини u в задану вершину v.

• Задача про найкоротший шлях між усіма парами вершин. Потрібно знайти найкоротший шлях з кожної вершини u в кожну вершину v. Цю задачу теж можна вирішити за допомогою алгоритму, призначеного для розв'язання задачі про одну вихідну вершину, проте зазвичай вона вирішується швидше.

В різних постановках задачі, роль довжини ребра можуть грати не тільки самі довжини, але і час, вартість, витрати, обсяг витрачених ресурсів (матеріальних, фінансових, паливно-енергетичних і т. д.) Або інші характеристики, пов'язані з проходженням кожного ребра. Таким чином, задача знаходить практичне застосування у великій кількості областей (інформатика, економіка, географія та ін.).

Задача про найкоротший шлях з урахуванням додаткових обмежень

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

1. Найкоротший шлях, що проходить через задану множину вершин. Можна розглядати два обмеження: найкоротший шлях повинен проходити через виділену множину вершин, і найкоротший шлях повинен містити якомога менше невиділених вершин. Перша з них добре відома в теорії дослідження операцій.

2. Мінімальне покриття вершин орієнтованого графа шляхами. Здійснюється пошук мінімального по числу шляхів покриття графа, а саме підмножини всіх s-t шляхів, таких що, кожна вершина орієнтованого графа належить хоча б одному такому шляху.

3. Задача про необхідні шляхи. Потрібно знайти мінімальну за потужністю множину s-t шляхів таку, що для будь-якого знайдеться шлях , що накриває його – множина деяких шляхів в орієнтованому графі G.

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

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

У минулому найкоротші по відстанях напрямку на мережі визначалися вручну з великою витратою праці. Відомий, наприклад, альбом найкоротших напрямків між залізничними вузлами, виданий МШС. У теперішній час найкоротші шляхи визначаються за допомогою ЕОМ.

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

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

Нехай задана наступна транспортна мережа. Вершинами даної мережі є станції, а дугами, що з'єднують їх, - ділянки. Для кожної дуги вказується напрямок і довжина (вартість, тривалість) перевезення.

Алгоритм рішення задачі

1. Привласнюємо вершині, від якої здійснюється пошук потенціал 0 і позначаємо цю вершину знаком "-"

2. . Привласнюємо всім іншим вершинам потенціал ∞.

3. Перевіряємо, чи є хоч одна вершина з міткою "-". Якщо такої вершини ні, то рішення завершене, інакше переходимо до кроку 4.

4. Беремо чергову вершину з міткою "-". Нехай це буде вершина k. Вибираємо дуги, що виходять із вершини kj і перевіряємо:

Uk+Ckj<Uj

де Uk, Uj - відповідно потенціали вершин k й j;

Ckj - довжина дуги kj.

Якщо умова виконується - переходимо до кроку 5, інакше до кроку 6.

5. Біля вершини j вказуємо номер вершини k (k є суміжною для j) Значення Uk+Ckj привласнюємо як потенціал вершині j. Позначаємо її знаком
"-" і переходимо до кроку 6.

6. Перевіряємо, чи всіє дуги, що виходять із вершини k переглянуті. Якщо так знімаємо з неї мітку "-" і переходимо до кроку 3, інакше переходимо до кроку 4.

Приклад

	1. Вершині 1 привласнюємо потенціал 0 і позначаємо її знаком "-". 2. Привласнюємо всім вершинам потенціал ∞. (зазначений у дужках біля вершини). 3. Розраховуємо Uk+Ckj<Uj для ребер 1-2 й 1-3. 1-2: 0+15<¥®крок 5 алгоритму 1-3 0+7 <¥ ®крок 5 алгоритму 4. Малюємо новий нову мережу
	Переглядаємо вершину 2. Зверніть увагу для ребра 2-3 умова Uk+Ckj<Uj не виконується, тому вершина 3 залишається без змін.
	Переглядаємо вершину 3. Зверніть увагу для ребра 3-2 умова Uk+Ckj<Uj виконується, тому вершина 2 знову позначена знайомий "-".
	Вершин, позначених знайомий "-" більше немає - отже пошук закінчений. Перша частина мітки біля вершини значить із якої вершини необхідно в неї переміщатися; друга частина мітки (потенціал) позначає відстань від початкової вершини.

Найкоротші відстані на мережі зображуються у вигляді дерева:

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