Задача о самом широком пути

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
В этом графе самый широкий путь из пункта Maldon в пункт Feering имеет ширину 29 и проходит через Clacton, Tiptree, Harwich и Blaxhall.

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

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

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

Неориентированные графы[править | править код]

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

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

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

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

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

Ориентированные графы[править | править код]

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

Все пары[править | править код]

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

Для вычисления самого широкого пути для всех пар узлов в плотных ориентированных графах, таких как в приложениях голосования, асимптотически[англ.] наиболее быстрый подход работает за время , где является показателем для алгоритмов быстрого перемножения матриц. При использовании лучших известных алгоритмов матричного умножения эти временны́е границы превращаются в [20]. Для ранних алгоритмов, которые также использовали быстрое матричное умножение для ускорения нахождения самых широких путей для всех пар, см. статьи Вассилевска, Вильямса и Юстера[21] и главу 5 книги Вассилевска[22]. Ссылочная реализация метода Шульце использует модифицированную версию более простого алгоритма Флойда — Уоршелла, который работает за время [4]. Для разреженных графов можно более эффективно использовать многократное применение алгоритма поиска самого широкого пути для одного источника.

Один источник[править | править код]

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

Единственный источник и единственная вершина назначения[править | править код]

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

Другое приложение самых широких путей возникает в алгоритме Форда — Фалкерсона для задачи о максимальном потоке. Постепенно увеличивая поток вдоль пути с максимальной ёмкостью в остаточной сети потока, приводит к небольшому пределу числа приращений, необходимых для поиска максимального потока. Здесь ёмкости рёбер предполагаются целыми числами, не превосходящими U. Однако этот анализ не зависит от нахождения точного максимума ёмкости. Подходит любой путь с ёмкостью, отличающуюся от максимальной на постоянный коэффициент. Комбинируя эти идеи приближения с методом приращения кратчайшего пути Алгоритма Эдмондса — Карпа, приводит к алгоритму максимального потока со временем работы [7].

Можно найти пути максимальной ёмкости и минимаксные пути с одиночным источником и одной вершиной назначения очень эффективно даже в моделях вычислений, которые позволяют лишь сравнение весов рёбер входного графа, а не арифметику с ними[13][25]. Алгоритм работает с множеством S рёбер, о которых известно, что оно содержит ребро узкого места оптимального пути. Первоначально S состоит из всех m рёбер графа. На каждой итерации алгоритма S разбивается на упорядоченную последовательность подмножеств примерно равного размера. Число подмножеств в этом разбиении выбирается так, что все точки разбиения между подмножествами могут быть найдены путём кратного нахождения медиан за время O(m). Алгоритм затем пересчитывает веса всех рёбер графа по индексу подмножества, содержащего ребро, и использует модифицированный алгоритм Дейкстра на графе с обновлёнными весами. Основываясь на результатах этих вычислений, можно вычислить за линейное время, какое из подмножеств содержит вес ребра узкого места. Алгоритм затем заменяет S подмножеством Si, которое содержит вес узкого места, и начинает новую итерацию с этим множеством S. Число подмножеств, на которое может быть разбито S, может увеличиваться экспоненциально с каждым шагом, так что число итераций пропорционально итерированному логарифму , а полное время выполнения будет [25]. В модели вычисления, где вес каждого ребра является машинным целым числом, использование итеративных логарифмирований в этом алгоритме может быть заменено на технику разбиения списка Хана и Торупа[26], позволяющую разбить S на более мелких частей s Si за один шаг, что приводит к линейной общей границе по времени[27].

Множества евклидовых точек[править | править код]

Тёмно-синие ленты отделяют пары гауссовых целых чисел, для которых минимаксная длина пути 2 или более.

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

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

Примечания[править | править код]

  1. ↑ Pollack, 1960, с. 733–736.
  2. ↑ Shacham, 1992, с. 1217–1221.
  3. ↑ Wang, Crowcroft, 1995, с. 2129–2133.
  4. ↑ 1 2 3 Schulze, 2011, с. 267–303.
  5. ↑ 1 2 Fernandez, Garfinkel, Arbiol, 1998, с. 293–304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009, с. 144–150.
  7. ↑ 1 2 Ahuja, Magnanti, Orlin, 1993, с. 210–212.
  8. ↑ 1 2 Berman, Handler, 1987, с. 115–122.
  9. ↑ Hu, 1961, с. 898–900.
  10. ↑ 1 2 Punnen, 1991, с. 402–404.
  11. ↑ Malpani, Chen, 2002, с. 175–180.
  12. ↑ Camerini, 1978, с. 10–14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006.
  14. ↑ Fernandez, Garfinkel, Arbiol, 1998.
  15. ↑ Alt, Godau, 1995, с. 75–91.
  16. ↑ Leclerc, 1981, с. 5–37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009, с. 341–353.
  18. ↑ Более точно, единственная возможность, когда метод Шульце не работает, это когда два кандидата имеют пути одинаковой ширины друг с другом.
  19. ↑ См. 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.
  20. ↑ Duan, Pettie, 2009, с. 384–391.
  21. ↑ Vassilevska, Williams, Yuster, 2007, с. 585–589.
  22. ↑ Vassilevska, 2008.
  23. ↑ Berman, Handler, 1987.
  24. ↑ Ullah, Lee, Hassoun, 2009.
  25. ↑ 1 2 Gabow, Tarjan, 1988, с. 411–417.
  26. ↑ Han, Thorup, 2002.
  27. ↑ Han, Thorup, 2002, с. 135–144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004, с. 233–249.
  29. ↑ Gethner, Wagon, Wick, 1998, с. 327–337.

Литература[править | править код]

  • Maurice Pollack. The maximum capacity through a network // Operations Research. — 1960. — Т. 8, вып. 5. — С. 733–736. — doi:10.1287/opre.8.5.733. — JSTOR 167387.
  • Shacham N. Multicast routing of hierarchical data // IEEE International Conference on Communications (ICC '92). — 1992. — Т. 3. — doi:10.1109/ICC.1992.268047.
  • Zheng Wang, Crowcroft J. Bandwidth-delay based routing algorithms // IEEE Global Telecommunications Conference (GLOBECOM '95). — 1995. — Т. 3. — doi:10.1109/GLOCOM.1995.502780.
  • Markus Schulze. A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method // Social Choice and Welfare. — 2011. — Т. 36, вып. 2. — С. 267–303. — doi:10.1007/s00355-010-0475-4.
  • Ullah E., Lee K., Hassoun S. An algorithm for identifying dominant-edge metabolic pathways // IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009). — 2009. — С. 144–150.
  • Oded Berman, Gabriel Y. Handler. Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations // Transportation Science. — 1987. — Т. 21, вып. 2. — С. 115–122. — doi:10.1287/trsc.21.2.115.
  • Hu T. C. The maximum capacity route problem // Operations Research. — 1961. — Т. 9, вып. 6. — doi:10.1287/opre.9.6.898. — JSTOR 167055.
  • Navneet Malpani, Jianer Chen. A note on practical construction of maximum bandwidth paths // Information Processing Letters. — 2002. — Т. 83, вып. 3. — С. 175–180. — doi:10.1016/S0020-0190(01)00323-4.
  • Abraham P. Punnen. A linear time algorithm for the maximum capacity path problem // European Journal of Operational Research. — 1991. — Т. 53, вып. 3. — doi:10.1016/0377-2217(91)90073-5.
  • Camerini P. M. The min-max spanning tree problem and some extensions // Information Processing Letters. — 1978. — Т. 7, вып. 1. — doi:10.1016/0020-0190(78)90030-3.
  • Volker Kaibel, Matthias A. F. Peinhardt. On the bottleneck shortest path problem. — Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2006. — (ZIB-Report 06-22).
  • Elena Fernandez, Robert Garfinkel, Roman Arbiol. Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths // Operations Research. — 1998. — Т. 46, вып. 3. — С. 293–304. — doi:10.1287/opre.46.3.293. — JSTOR 222823.
  • Helmut Alt, Michael Godau. Computing the Fréchet distance between two polygonal curves // International Journal of Computational Geometry and Applications. — 1995. — Т. 5, вып. 1–2. — С. 75–91. — doi:10.1142/S0218195995000064.
  • Bruno Leclerc. Description combinatoire des ultramétriques (фр.) // Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines. — 1981. — Вып. 73. — С. 5–37, 127.
  • Erik D. Demaine, Gad M. Landau, Oren Weimann. On Cartesian trees and range minimum queries // Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009. — 2009. — Т. 5555. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-02927-1_29.
  • Ran Duan, Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths // Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09). — 2009.
  • Virginia Vassilevska, Ryan Williams, Raphael Yuster. All-pairs bottleneck paths for general graphs in truly sub-cubic time // Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC '07). — New York: ACM, 2007. — doi:10.1145/1250790.1250876.
  • Virginia Vassilevska. Efficient Algorithms for Path Problems in Weighted Graphs. — Carnegie Mellon University School of Computer Science, 2008. — (Ph.D. thesis, Report CMU-CS-08-147).
  • Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. 7.3 Capacity Scaling Algorithm // Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. — ISBN 0-13-617549-X.
  • Harold N. Gabow, Robert E. Tarjan. Algorithms for two bottleneck optimization problems // Journal of Algorithms. — 1988. — Т. 9, вып. 3. — doi:10.1016/0196-6774(88)90031-4.
  • Yijie Han, Thorup M. Integer sorting in O(n√log log n) expected time and linear space // Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002). — 2002. — doi:10.1109/SFCS.2002.1181890.
  • Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh. Approximating geometric bottleneck shortest paths // Computational Geometry. Theory and Applications. — 2004. — Т. 29, вып. 3. — doi:10.1016/j.comgeo.2004.04.003.
  • Ellen Gethner, Stan Wagon, Brian Wick. A stroll through the Gaussian primes // American Mathematical Monthly. — 1998. — Т. 105, вып. 4. — С. 327–337. — doi:10.2307/2589708.
Источник — https://ru.wikipedia.org/w/index.php?title=Задача_о_самом_широком_пути&oldid=136332058