Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе , максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью . Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём использования некоего специального значения вместо длины пути . Однако во многих случаях возможны более быстрые алгоритмы.

Например, в графе, который представляет соединения между маршрутизаторами в интернете , в котором вес ребра представляет полосу пропускания соединения между двумя маршрутизаторами, задача о самом широком пути соответствует задаче поиска сквозного пути между двумя узлами интернета, который имеет максимально широкую полосу . Наименьший вес ребра на этом пути известен как ёмкость или ширина пути. Наравне с приложениями в маршрутизации в сети задача о самом широком пути является также важной компонентой метода Шульце определения победителя в многоходовых выборах , она была использована в цифровом совмещении изображений , и для вычисления максимальных потоков .

Тесно связанная задача о минимаксном пути спрашивает о пути, который минимизирует максимальный вес любого из рёбер (можно интерпретировать как поиск самой ровной дороги, имеющей минимальные углы подъёма и спуска). Эта задача находит приложение в планировании дорожного движения . Любой алгоритм для задачи о самом широком пути может быть преобразован в алгоритм о минимаксном пути и, наоборот, путём обращения смысла всех сравнений весов, предпринимаемых в алгоритме, или, эквивалентно, путём замены весов на отрицательные значения.

Неориентированные графы

В неориентированном графе самый широкий путь может быть найден как путь между двумя вершинами в максимальном остовном дереве графа, а минимаксный путь может быть найден как путь между двумя вершинами в минимальном остовном дереве .

В любом графе, ориентированном или нет, имеется простой алгоритм нахождения самого широкого пути, если вес ребра с минимальным значением известен — просто удаляем все рёбра с меньшим значением и ищем путь среди оставшихся рёбер с помощью поиска в ширину или поиска в глубину . Существует основанный на этой проверке алгоритм линейного времени для нахождения самого широкого s - t пути в неориентированном графе, который не использует максимальное остовное дерево. Основная идея алгоритма состоит в том, чтобы применить алгоритм линейного времени для нахождения пути к медиане весов рёбер графа, а затем либо удалить все меньшие рёбра, либо стянуть все бо́льшие рёбра согласно тому, существует ли путь или его нет, а затем рекурсивно отработать получившийся меньший граф .

Фернандес, Гарфинкель и Арбиоль использовали задачу на «узкие места» в неориентированных графах для получения цифрового совмещения изображений аэрофотосъёмки , комбинирующего несколько изображений перекрывающихся областей. В подзадаче, к которой задача о самом широком пути применяется, два изображения уже . Остаётся лишь выбрать шов , кривую, которая проходит через область перекрытия и отделяет одно изображение от другого. Пикселы с одной стороны от шва копируются из одного изображения, а пикселы с другой стороны шва копируются из другого изображения. В отличие от других методов совмещения изображений, в которых пикселы с обоих изображений усредняются, этот метод действительное фотографическое изображение каждой части сфотографированной области. В методе веса рёбрам решётки назначают значениями, оценивающими, насколько будет визуально проявляться шов на ребре, и находят самый широкий путь для этих весов. Использование этого пути в качестве шва, а не более традиционного кратчайшего пути, приводит к тому, что их система находит шов, который трудно различить, вместо увеличения качества одной части изображения за счёт ухудшения другой .

Решение минимаксной задачи между двумя углами решётки решётки может быть использовано для поиска слабого расстояния Фреше между двумя ломаными . Здесь каждая вершина решётки представляет пару отрезков, по одному из каждой цепи, а вес ребра представляет расстояние Фреше, необходимое, чтобы пройти от одной пары отрезков до другой .

Если все веса рёбер неориентированного графа положительны , то минимаксные расстояния между парами точек (максимальные веса рёбер минимаксных путей) образуют ультраметрическое пространство . Обратно, каждое конечное ультраметрическое пространство образуется из минимаксных расстояний таким образом . Структура данных , построенная из наименьшего остовного дерева, позволяет запросить минимаксное расстояние между любой парой вершин за постоянное время с помощью запросов наименьшего общего предка в декартовом дереве . Корень декартова дерева представляет самое тяжёлое ребро наименьшего остовного дерева, а дети корня являются декартовыми деревьями, рекурсивно построенными из поддеревьев наименьших остовных деревьев, образованных путём удаления наиболее тяжёлого ребра. Листья декартова дерева представляют собой вершины входного графа, а минимаксное расстояние между двумя вершинами равно весу узла декартова дерева, который является их наименьшим общим предком. Как только рёбра наименьшего остовного дерева отсортированы, это декартово дерево может быть построено за линейное время .

Ориентированные графы

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

Все пары

Задача о самом широком пути для всех пар имеет приложение в методе Шульце для определения победителя в многоходовых выборах , в которых голосующие оценивают кандидатов в преференциальном голосовании . Метод Шульце строит полный ориентированный граф , в котором вершины представляют кандидатов, а любые две вершины соединены ребром. Каждое ребро направлено от победителя к проигравшему в поединках между двумя кандидатами и помечено перевесом победителя в соревновании. Затем метод вычисляет самый широкий путь между всеми парами вершин и победителем становится кандидат, который имеет более широкие пути с каждым из оппонентов . Результаты выборов с помощью этого метода согласуются с — кандидат, выигравший все поединки, автоматически становится победителем выборов, однако метод позволяет выбрать победителя, когда метод Кондорсе не срабатывает . Метод Шульце использовался в некоторых организациях, включая Фонд Викимедиа .

Для вычисления самого широкого пути для всех пар узлов в плотных ориентированных графах, таких как в приложениях голосования, наиболее быстрый подход работает за время ${\displaystyle O(n^{(3+\omega )/2})}$ , где ${\displaystyle \omega }$ является показателем для алгоритмов быстрого перемножения матриц . При использовании лучших известных алгоритмов матричного умножения эти временны́е границы превращаются в ${\displaystyle O(n^{2{,}688})}$ . Для ранних алгоритмов, которые также использовали быстрое матричное умножение для ускорения нахождения самых широких путей для всех пар, см. статьи Вассилевска, Вильямса и Юстера и главу 5 книги Вассилевска . Ссылочная реализация метода Шульце использует модифицированную версию более простого алгоритма Флойда — Уоршелла , который работает за время ${\displaystyle O(n^{3})}$ . Для разреженных графов можно более эффективно использовать многократное применение алгоритма поиска самого широкого пути для одного источника.

Один источник

Если рёбра отсортированы по их весам, то модифицированная версия алгоритма Дейкстры может вычислить узкие места между назначенной стартовой вершиной и всеми остальными вершинами графа за линейное время. Ключевая идея ускорения с помощью обычного варианта алгоритма Дейкстры заключается в том, что последовательность «узких мест» до каждой вершины в порядке появления этих вершин в алгоритме является монотонной подпоследовательностью, сортированной последовательности рёбер по весам. Поэтому очередь с приоритетом алгоритма Дейкстры может быть реализована как , массив, пронумерованный числами от 1 до m (число рёбер в графе), где ячейка массива i содержит вершины, «узкие места» которых равны весу ребра с позицией i в отсортированном порядке. Этот метод позволяет решить задачу о самом широком пути с такой же скоростью, как и сортировка . Например, если веса рёбер представлены целыми числами, то граничное время для целочисленной сортировки списка из m целых чисел будет также оценкой для данной проблемы .

Единственный источник и единственная вершина назначения

Берман и Хандлер предположили, что аварийные машины м машины скорой помощи должны использовать минимаксный путь, когда возвращаются из точки вызова на базу. В этих случаях время возвращения менее важно, чем время ответа, если другой вызов случится, пока машина находится в процессе возвращения. При использовании минимаксного пути, в котором весами служит максимальное время пути от ребра до самой отдалённой точки возможного вызова, можно спланировать маршрут так, что максимальное время возможной задержки между получением вызова и прибытием машины будет минимальным . Улла, Ли и Хассун использовали максимальные пути для моделирования цепочки доминирующих реакций в метаболических сетях . В их модели весом ребра служит свободная энергия метаболической реакции, представленной ребром .

Другое приложение самых широких путей возникает в алгоритме Форда — Фалкерсона для задачи о максимальном потоке . Постепенно увеличивая поток вдоль пути с максимальной ёмкостью в остаточной сети потока, приводит к небольшому пределу ${\displaystyle O(m\log U)}$ числа приращений, необходимых для поиска максимального потока. Здесь ёмкости рёбер предполагаются целыми числами, не превосходящими U . Однако этот анализ не зависит от нахождения точного максимума ёмкости. Подходит любой путь с ёмкостью, отличающуюся от максимальной на постоянный коэффициент. Комбинируя эти идеи приближения с методом приращения кратчайшего пути Алгоритма Эдмондса — Карпа , приводит к алгоритму максимального потока со временем работы ${\displaystyle O(mn\log U)}$ .

Можно найти пути максимальной ёмкости и минимаксные пути с одиночным источником и одной вершиной назначения очень эффективно даже в моделях вычислений, которые позволяют лишь сравнение весов рёбер входного графа, а не арифметику с ними . Алгоритм работает с множеством S рёбер, о которых известно, что оно содержит ребро узкого места оптимального пути. Первоначально S состоит из всех m рёбер графа. На каждой итерации алгоритма S разбивается на упорядоченную последовательность подмножеств ${\displaystyle S_{1},S_{2},\dots }$ примерно равного размера. Число подмножеств в этом разбиении выбирается так, что все точки разбиения между подмножествами могут быть найдены путём кратного нахождения медиан за время O ( m ) . Алгоритм затем пересчитывает веса всех рёбер графа по индексу подмножества, содержащего ребро, и использует модифицированный алгоритм Дейкстра на графе с обновлёнными весами. Основываясь на результатах этих вычислений, можно вычислить за линейное время, какое из подмножеств содержит вес ребра узкого места. Алгоритм затем заменяет S подмножеством S _i , которое содержит вес узкого места, и начинает новую итерацию с этим множеством S . Число подмножеств, на которое может быть разбито S , может увеличиваться экспоненциально с каждым шагом, так что число итераций пропорционально итерированному логарифму ${\displaystyle O(\log ^{\star }n)}$ , а полное время выполнения будет ${\displaystyle O(m\log ^{\star }n)}$ . В модели вычисления, где вес каждого ребра является машинным целым числом, использование итеративных логарифмирований в этом алгоритме может быть заменено на технику разбиения списка Хана и Торупа , позволяющую разбить S на ${\displaystyle O({\sqrt {m}})}$ более мелких частей s S _i за один шаг, что приводит к линейной общей границе по времени .

Множества евклидовых точек

Вариант задачи минимаксного пути рассматривался для множества точек на евклидовой плоскости . Как в задаче с неориентированным графом, эта задача евклидова минимаксного пути может быть решена эффективна путём нахождения евклидова минимального остовного дерева — любой путь в дереве является минимаксным путём. Однако задача становится более сложной, если желают, чтобы путь не только минимизировал верхнюю длину, но и также среди путей с одинаковой верхней длиной минимизировал или примерно минимизировал полную длину пути. Решение может быть приближено с помощью геометрического остова .

В теории чисел нерешённая проблема спрашивает, ограничена ли минимаксная длина минимаксных путей в гауссовых простых чисел . То есть существует ли константа B , такая, что для любой пары p и q в бесконечном множестве евклидовых точек, определённых гауссовыми простыми, минимаксный путь в гауссовых простых между p и q имеет длину рёбер, не превосходящую B ? .

Примечания

Литература