Задача про найширший шлях

У цьому графі найширший шлях із пункту Maldon у пункт Feering має ширину 29 та проходить через Clacton, Tiptree, Harwich та Blaxhall

Задача про найширший шлях — задача знаходження шляху між двома вибраними вершинами у зваженому графі, що максимізує вагу мінімального за вагою ребра графа (якщо розглядати вагу ребра як ширину дороги, то задача полягає у виборі найширшої дороги, що зв'язує дві вершини). Задача про найширший шлях відома також як задача про вузьке місце або задача про шлях із найбільшою пропускною здатністю. Для обчислення пропускної спроможності можна пристосувати алгоритми найкоротшого шляху, використавши замість довжини шляху деяке особливе значенняШаблон:Sfn. Однак у багатьох випадках можливі швидші алгоритми.

Наприклад, у графі, який представляє з'єднання між маршрутизаторами в інтернеті, в якому вага ребра представляє смугу пропускання з'єднання між двома маршрутизаторами, задача про найширший шлях відповідає задачі пошуку наскрізного шляху між двома вузлами інтернету, який має найширшу смугуШаблон:Sfn Шаблон:Sfn. Найменша вага ребра в цьому шляху відома як місткість чи ширина шляху. Також задача про найширший шлях є важливою складовою методу Шульце визначення переможця в багатоходових виборахШаблон:Sfn, вона використовується в Шаблон:Нп Шаблон:Sfn, Шаблон:Не перекладено Шаблон:Sfn і для обчислення максимальних потоків Шаблон:Sfn.

Тісно пов'язана задача про мінімаксний шлях запитує про шлях, який мінімізує максимальну вагу будь-якого з ребер (можна інтерпретувати як пошук найрівнішої дороги, що має мінімальні кути підйому та спуску). Цю задачу застосовують у плануванні дорожнього рухуШаблон:Sfn. Будь-який алгоритм для задачі про найширший шлях можна перетворити на алгоритм про мінімаксний шлях і, навпаки, шляхом обернення сенсу всіх порівнянь ваг, що вживаються в алгоритмі, або, еквівалентно, замінивши ваги від'ємними значеннями.

Неорієнтовані графи

У неорієнтованому графі найширший шлях можна знайти як шлях між двома вершинами в максимальному кістяковому дереві графа, а мінімаксний шлях можна знайти як шлях між двома вершинами в мінімальному кістяковому деревіШаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

У будь-якому графі, орієнтованому чи ні, є простий алгоритм знаходження найширшого шляху, якщо відома вага ребра з найменшим значенням — просто видаляємо всі ребра з меншим значенням і шукаємо шлях серед решти ребер за допомогою пошуку в ширину або пошуку в глибину. Існує заснований на цій перевірці алгоритм лінійного часу для знаходження найширшого Шаблон:Math шляху в неорієнтованому графі, який не використовує максимального кістякового дерева. Основна ідея алгоритму полягає в тому, щоб застосувати алгоритм лінійного часу для знаходження шляху до медіани ваг ребер графа, потім або видалити всі менші ребра, або стягнути всі більші ребра відповідно до того, чи існує шлях, чи його немає, а потім рекурсивно опрацювати менший графШаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

Фернандес, Гарфінкель і АрбіольШаблон:Sfn використовували задачу на «вузькі місця» в неорієнтованих графах для отримання Шаблон:Не перекладено аерофотозйомки, що комбінує кілька зображень ділянок, що перекриваються. У підзадачі, до якої застосовується задача про найширший шлях, два зображення вже зведено до єдиної системи координат. Залишається лише вибрати шов, криву, яка проходить через ділянку перекриття та відокремлює одне зображення від іншого. Пікселі з одного боку шва копіюються з одного зображення, а пікселі з іншого боку шва копіюються з іншого зображення. На відміну від інших методів суміщення зображень, у яких пікселі з обох зображень усереднюються, цей метод дає дійсне фотографічне зображення кожної частини сфотографованої ділянки. У методі ваги ребрам решітки призначають значеннями, які оцінюють, наскільки візуально виявлятиметься шов на ребрі, і знаходять найширший шлях для цих ваг. Використання цього шляху як шва, а не традиційнішого найкоротшого шляху, приводить до того, що їх система знаходить шов, який важко розрізнити, замість підвищення якості однієї частини зображення за рахунок зниження якості іншоїШаблон:Sfn.

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

Якщо всі ваги ребер неорієнтованого графа додатні, то мінімаксні відстані між парами точок (максимальні ваги ребер мінімаксних шляхів) утворюють ультраметричний простір. І навпаки, кожен скінченний ультраметричний простір утворюється з мінімаксних відстаней у такий спосібШаблон:Sfn. Структура даних, побудована з найменшого кістякового дерева, дозволяє запитати мінімаксну відстань між будь-якою парою вершин за постійний час за допомогою запитів найменшого спільного предка в декартовому дереві. Корінь декартового дерева представляє найважче ребро найменшого кістякового дерева, а діти кореня є декартовими деревами, рекурсивно побудованими з піддерев найменших кістякових дерев, утворених видаленням найважчого ребра. Листки декартового дерева є вершинами вхідного графа, а мінімаксна відстань між двома вершинами дорівнює вазі вузла декартового дерева, який є їхнім найменшим спільним предком. Як тільки ребра найменшого кістякового дерева відсортовано, це декартове дерево можна побудувати за лінійний часШаблон:Sfn.

Орієнтовані графи

В орієнтованих графах розв'язок із найбільшим кістяковим деревом використовувати не можна. Натомість відомі деякі інші алгоритми. Питання, який алгоритм вибрати, залежить від того, чи зафіксовано початкову та кінцеву вершини шляху, чи потрібно знайти шляхи від кількох початкових та кінцевих вершин одночасно.

Всі пари

Задачу про найширший шлях для всіх пар застосовують у методі Шульце для визначення переможця в багатоходових виборах, у яких виборці оцінюють кандидатів у Шаблон:Нп. Метод Шульце будує повний орієнтований граф, у якому вершини представляють кандидатів, а будь-які дві вершини з'єднані ребром. Кожне ребро спрямоване від переможця до переможеного в поєдинках між двома кандидатами, і позначено перевагою переможця у змаганні. Потім метод обчислює найширший шлях між усіма парами вершин та переможцем стає кандидат, який має ширші шляхи з кожним із опонентівШаблон:Sfn. Результати виборів, отримані за допомогою цього методу, узгоджуються з Шаблон:Не перекладено, — кандидат, який виграв усі поєдинки, автоматично стає переможцем виборів, проте метод дозволяє вибрати переможця, коли метод Кондорсе не спрацьовує^[1]. Метод Шульце використовували в деяких організаціях, наприклад, у Фонді Вікімедіа^[2].

Для обчислення найширшого шляху для всіх пар вузлів у щільних орієнтованих графах, таких, які виникають у застосуванні до голосування, Шаблон:Не перекладено найшвидший підхід працює за час $O (n^{(3 + ω) / 2})$ , де $ω$ — показник для алгоритмів швидкого множення матриць. За використання найкращих відомих алгоритмів матричного множення ці часові межі перетворюються на $O (n^{2, 688})$ Шаблон:Sfn. У ранніх алгоритмах,Шаблон:Sfn Шаблон:Sfn для прискорення знаходження найширших шляхів для всіх пар, використовували швидке матричне множення, див. статті Шаблон:Нп, Вільямса і ЮстераШаблон:Sfn і розділ 5 книги ВасилевськоїШаблон:Sfn. Посилальна реалізація методу Шульце використовує модифіковану версію простішого алгоритму Флойда — Воршелла, який працює за час $O (n^{3})$ Шаблон:Sfn. Для розріджених графів можна ефективніше використовувати багаторазове застосування алгоритму пошуку найширшого шляху для одного джерела.

Одне джерело

Якщо ребра відсортовано за їхніми вагами, то модифікована версія алгоритму Дейкстри може обчислити вузькі місця між призначеною стартовою вершиною та іншими вершинами графа за лінійний час. Ключова ідея прискорення за допомогою звичайного варіанта алгоритму Дейкстри полягає в тому, що послідовність «вузьких місць» до кожної вершини в порядку появи цих вершин у алгоритмі є монотонною підпослідовністю послідовності ребер, сортованої за вагами. Тому чергу з пріоритетом алгоритму Дейкстри можна реалізувати як контейнерну чергу, масив, пронумерований числами від 1 до Шаблон:Mvar (число ребер у графі), де комірка масиву Шаблон:Mvar містить вершини, «вузькі місця» яких дорівнюють вазі ребра з позицією Шаблон:Mvar у відсортованому порядку. Цей метод дозволяє розв'язати задачу про найширший шлях із такою ж швидкістю, як і сортування. Наприклад, якщо ваги ребер задано цілими числами, то граничний час для цілочисельного сортування списку Шаблон:Mvar цілих чисел буде також оцінкою для цієї задачіШаблон:Sfn.

Одне джерело та одна цільова вершина

Берман і ГандлерШаблон:Sfn припустили, що аварійні машини і машини швидкої допомоги, повертаючися з точки виклику на базу, повинні використовувати мінімаксний шлях. У цих випадках час повернення менш важливий, ніж час відповіді, якщо інший виклик трапиться, поки машина повертається. За використання мінімаксного шляху, в якому вагами служить найбільший час шляху від ребра до найвіддаленішої точки можливого виклику, можна спланувати маршрут так, що найбільший час можливої затримки між отриманням виклику і прибуттям машини буде найменшимШаблон:Sfn. Улла, Лі та ГассунШаблон:Sfn використали максимальні шляхи для моделювання ланцюжка домінівних реакцій у метаболічних мережах. У їхній моделі вагою ребра служить вільна енергія метаболічної реакції, яку представляє реброШаблон:Sfn.

Інше застосування найширших шляхів виникає в алгоритмі Форда — Фалкерсона для задачі про максимальний потік. Поступово збільшуючи потік уздовж шляху з максимальною ємністю в залишковій мережі потоку, що приводить до невеликої межі $O (m \log U)$ числа прирощень, необхідних для пошуку максимального потоку. Тут ємності ребер є цілими числами, що не перевищують Шаблон:Mvar. Проте, цей аналіз залежить від знаходження точного максимуму ємності. Підходить будь-який шлях із ємністю, що відрізняється від максимальної на постійний коефіцієнт. Комбінування цих ідей наближення з методом збільшення найкоротшого шляху алгоритму Едмондса — Карпа приводить до алгоритму максимального потоку з часом роботи $O (m n \log U)$ Шаблон:Sfn.

Шляхи максимальної місткості і мінімаксні шляхи з одним джерелом і однією цільовою вершиною можна знайти дуже ефективно навіть у моделях обчислень, які дозволяють лише порівняння ваг ребер вхідного графа, а не арифметику з нимиШаблон:Sfn Шаблон:Sfn. Алгоритм працює зі множиною Шаблон:Mvar ребер, про яку відомо, що вона містить ребро вузького місця оптимального шляху. Спочатку Шаблон:Mvar складається з усіх Шаблон:Mvar ребер графа. На кожній ітерації алгоритму Шаблон:Mvar розбивають на впорядковану послідовність підмножин $S_{1}, S_{2}, \dots$ приблизно однакового розміру. Число підмножин у розбитті вибирають так, що всі точки розбиття між підмножинами можна знайти шляхом кратного знаходження медіан за час Шаблон:Math. Алгоритм потім перераховує ваги всіх ребер графа за індексом підмножини, що містить ребро, і використовує модифікований алгоритм Дейкстри на графі з оновленими вагами. Ґрунтуючись на результатах цих обчислень, можна обчислити за лінійний час, яка з підмножин містить вагу ребра вузького місця. Потім алгоритм замінює Шаблон:Mvar підмножиною Шаблон:Math, що містить вагу вузького місця, і починає нову ітерацію з цією множиною Шаблон:Mvar. Число підмножин, на яке можна розбити Шаблон:Mvar, може зростати експоненційно з кожним кроком, так що кількість ітерацій пропорційна ітерованому логарифму $O (\log^{⋆} n)$ , а повний час виконання буде $O (m \log^{⋆} n)$ Шаблон:Sfn. У моделі обчислення, де вага кожного ребра є машинним цілим числом, використання ітерованих логарифмів у цьому алгоритмі можна замінити на техніку розбиття списку Гана та ТорупаШаблон:Sfn, що дозволяє розбити Шаблон:Mvar на $O (\sqrt{m})$ менших частин Шаблон:Math за один крок, що приводить до лінійної спільної межі за часомШаблон:Sfn.

Множини евклідових точок

Варіант задачі мінімаксного шляху розглянуто для множини точок на евклідовій площині. Як у задачі з неорієнтованим графом, цю задачу евклідового мінімаксного шляху можна розв'язати ефективно шляхом знаходження евклідового мінімального кістякового дерева — будь-який шлях у дереві є мінімаксним шляхом. Однак задача стає складнішою, якщо потрібно, щоб шлях не тільки мінімізував верхню довжину, але й серед шляхів із однаковою верхньою довжиною мінімізував або приблизно мінімізував повну довжину шляху. Розв'язок можна наблизити за допомогою геометричного кістяка Шаблон:Sfn.

У теорії чисел нерозв'язана задача про Шаблон:Не перекладено запитує, чи обмежена мінімаксна довжина мінімаксних шляхів у гауссових простих чисел. Тобто чи існує стала Шаблон:Mvar, така, що для будь-якої пари Шаблон:Mvar і Шаблон:Mvar в нескінченній множині евклідових точок, визначених гауссовими простими, мінімаксний шлях у гауссових простих між Шаблон:Mvar і Шаблон:Mvar має довжину ребер, що не перевищує Шаблон:Mvar?Шаблон:Sfn Шаблон:Clear

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

↑ Точніше, єдина можливість, коли метод Шульце не працює, це коли два кандидати мають шляхи однакової ширини.
↑ См. Jesse Plamondon-Willard, Board election to use preference voting, May 2008; Mark Ryan, 2008 Wikimedia Board Election results, June 2008; 2008 Board Elections, June 2008; and 2009 Board Elections, August 2009.

[1] Точніше, єдина можливість, коли метод Шульце не працює, це коли два кандидати мають шляхи однакової ширини.

[Wikimedia-2] См. Jesse Plamondon-Willard, Board election to use preference voting, May 2008; Mark Ryan, 2008 Wikimedia Board Election results, June 2008; 2008 Board Elections, June 2008; and 2009 Board Elections, August 2009.

[1]

[2]

Задача про найширший шлях

Зміст

Неорієнтовані графи

Орієнтовані графи

Всі пари

Одне джерело

Одне джерело та одна цільова вершина

Множини евклідових точок

Примітки

Література

Навігаційне меню

Задача про найширший шлях

Неорієнтовані графи

Орієнтовані графи

Всі пари

Одне джерело

Одне джерело та одна цільова вершина

Множини евклідових точок

Примітки

Література

Навігаційне меню

Пошук