Участник:AKA MBG/Задача о максимальной пропускной способности

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

У:Enne.anastasia

In this graph, the widest path from Maldon to Feering has bandwidth 29, and passes through Clacton, Tiptree, Harwich, and Blaxhall.

В алгоритмах на графах зада́ча о максима́льной пропускно́й спосо́бности заключается в поиске пути между двумя заданными вершинами во взвешенном графе, с целью максимизации веса ребра с минимальным весом в этом пути. Задача о максимальной пропускной способности is also known as the bottleneck shortest path problem or the maximum capacity path problem. Большинство алгоритмов поиска кратчайшего пути можно модифицировать для нахождения пути с максимальной пропускной способностью, используя the bottleneck distance вместо длины пути[1]. Тем не менее, во многих случаях even faster algorithms are possible.

Например, в графе, который represents соединения между маршрутизаторами в интернете, где вес ребра — это ширина полосы пропускания соединения между двумя маршрутизаторами, задача о максимальной пропускной способности заключается в нахождении an end-to-end пути между двумя Internet nodes that has максимально возможную ширину.[2] Наименьший вес ребра в таком пути называется пропускной способностью или шириной пути. Наравне со своими приложениями in network routing, задача о максимальной пропускной способности сама по себе является важной component of the метода Шульце для определения победителя в multiway election,[3] and has been applied to digital compositing,[4] metabolic pathway analysis,[5] and the computation of maximum flows.[6]

Тесно связанная the minimax path problem, заключается в поиске пути, который минимизирует максимальный вес любого его ребра. It has приложения that include transportation planning.[7] Любой алгоритм для решения задачи о максимальной пропускной способности может быть преобразован в алгоритм для решения minimax path problem, и обратно, by reversing the sense of all the weight comparisons performed by the algorithm, or equivalently by replacing every edge weight by its negation.

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

У:Plekhanov.evgeniy

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

В любом графе, ориентированном или неориентированном, существует простой алгоритм поиска широчайшего пути после того, как вес минимально весящей грани становится известен: просто удалите все наименьшие грани и поищите по любому пути среди оставшихся ребер, используя поиск в ширину или поиск в глубину. На основании этой проверки также существует алгоритм линейного времени для нахождения широчайшего s-t пути в неориентированном графе, который не использует максимальное остовное дерево. Основная идея алгоритма состоит в том, чтобы применить алгоритм линейного времени для нахождения пути к медиане среднего веса в графе, а затем либо удалить все меньшие ребра, либо сократить все большие ребра в соответствии существует ли путь или его нет, и recurse in the resulting smaller graph.[9][11][12]

Фернандес, Гарфинкель & Арбиоль (1998) использовали неориентированные bottleneck кратчайшие пути для формирования композитных аэрофотоснимков, которые сочетают в себе несколько изображений перекрывающихся областей. В подзадачи, к которой проблема широчайшего пути обращается, два изображения уже были преобразованы в единую систему координат; оставшаяся задача состоит в том, чтобы выбрать шов, кривая которого проходит через область перекрытия и делит одно из двух изображений с другим. Пикселей на одной стороне шва будет скопировано из одного из изображений, а пиксели на другой стороне шва будут скопированы с другого изображения. В отличие от других методов композитинга, где средние пиксели от обоих изображений, этот дает действительное фотографическое изображение каждой части фотографируемой области. Они нагружают грани решетки с помощью цифровой оценки как визуально будет очевиден шов сквозь грань, и найти a bottleneck кратчайший путь для этих весов. Используя этот путь как шов, а не более традиционный кратчайший путь, causes их систему, чтобы найти шов, который трудно различить во всех точках, а не позволяя ему разменять большую видимость в одной части изображения для меньшей видимости в другом месте.[4]

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

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

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

У:ZigZak

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


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

Попарная задача о максимальной пропускной способности имеет приложения в Методе Щульце где используется выбор победителя в многоходовых Выборах где голосующие оценивали кандидатов в Преференциальном голосовании. В методе Щульце конструировался полный ориентированный граф в котором вершины представляют себя кандидатов и каждые две вершины соединены с ребром. Каждое ребро направлено от победителя к проигравшему в парном соревновании между двумя соединенными кандидатами и помечено победой соревнования. После метод просчитывал максимальную пропускную способность между парами вершин, и победителем являлся кандидат вершина которого имела максимальную пропускную способность и наоборот.[16] Результаты данных выборов используя этот метод соотносятся с методом Condorcet где кандидат, который победил во всех парных соревнованиях автоматически побеждает в выборах – но в общих чертах позволяет победителю быть выбранным даже в ситуациях, где этот метод сам по себе не работает.[17] Метод Щюльце используется несколькими организациями, включая Фонд Викимедиа.[18]

Для того чтобы вычислить ширину максимальной пропускной способности для всех пар точек в плотных ориентированных графах, таких как тех что появляются в приложении для голосования, известный асимптотически быстрый подход берет время O(n(3+ω)/2) где ω экспонента для алгоритмов быстрого перемножения матриц. Используя широко известные алгоритмы для перемножения матриц, временные границы становится O(n2.688).[19] Вместо этого, соответствующая реализация для метода Щульце использует модифицированную версию более простого алгоритма Флойда — Уоршелла, который берет время O(n3).[3] Для разреженных граф, может быть более эффективно повторно использовать едино-источный алгоритм максимальной пропускной способности.

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

Если ребра отсортированы по их весу, тогда модифицированная версия алгоритма Дейкстры сможет вычислить узкие места между обозначенной начальной вершиной и любой другой вершиной в графе, в линейном времени. Основная идея ускорения через обычный вариант алгоритма Дейкстры это последовательность расстояний узких мест для каждой вершины, для того чтобы вершины считались через этот алгоритм, где Монотонная функция подпоследовательности отсортировано последовательностью вес ребер; следовательно, очередь с приоритетом алгоритма Дейкстры может быть реализовано как очередь с ведром: массив индексируемая по числу от 1 до m (кол-во ребер в графе), где элемент массива i содержит вершины, чьи расстояние узкого пространства является весом ребер с расположением i в отсортированном порядке. Данный метод позволяет задаче о максимальной пропускной способности решиться также быстро как сортировка; Например, если вес ребер представлен в виде целочисленного, тогда временные границы для целочисленной сортировки листа m целочисленных будет также применяться к этой проблеме.[12]

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

Berman & Handler (1987) предположили что коммунальные машины и аварийные машины должны использовать минимаксные пути когда возвращаются с вызова на базу. В этом приложении, время возвращения менее важно чем время отклика на очередной вызов во время возвращения на базу. Используя минимаксный путь, где вес ребра это максимально пройденный путь из одной точки в ребре до самого дальнего вызова, человек может спланировать путь минимизирует максимально возможную задержку между получением вызова и прибытием и вызванной машины.[7] Ullah, Lee & Hassoun (2009) использовали максиминые пути для моделирования цепочки доминирующих реакция в метаболической сети; в их модели, вес ребра и свободной энергии метаболической реакции представлены в виде ребра.[5]

Другое приложение максимальной пропускной способности поднимается в алгоритме Форда — Фалкерсона для задачи о максимальном потоке. Постепенно приумножая поток вдоль максимально вместимого пути в остаточной сети потока ведет к небольшому пределу, O(m log U), от количества приращений необходимых, чтобы найти максимальный поток; here, краевые мощности предполагаются целыми числами, that are at most U. Тем не менее, этот анализ не зависит от нахождения пути, который имеет точный максимум мощности; любой путь, емкость которого в пределах постоянного множителя максимальных потойдет. Комбинируя эту идею приближения с кратчайшим методом приумножения Алгоритма Эдмондса — Карпа приводит к алгоритму максимального потока с управлением времениO(mn log U).[6]

У:LeraZaitseva

Существуют эффективные способы поиска пути с максимальной пропускной способностью и минимаксные пути с единственным источником и единственным местом назначения в вычислительных моделях, в которых разрешено сравнивать веса рёбер графа, поданного на вход, но нельзя выполнять над ними никаких действий.[20][21] Это алгоритм построения набора рёбер S, при этом на каждой итерации известно, что S' продолжает содержать "узкое место" (bottleneckedge) оптимального пути; первоначально, S просто набор всех m рёбер графа. На каждой итерации алгоритма множество S' делят на упорядоченную последовательность подмножеств S1, S2, ... приблизительно равного размера; количество подмножеств в этом разбиении выбрано таким образом, чтобы все точки между подмножествами могли быть найдены повторным применением поиска медианы за время O(m). Тогда алгоритм пересчитывает веса, индексируя каждое ребро графа подмножества рёбер, содержащее ребро и используют модифицированный алгоритм Дейкстры на графе с обновлёнными значениями весов; на основе этих вычислений можно определить за какое линейное время, которое из подмножеств содержит ребро, соответствующее узкому месту. Затем заменяем S на то подмножество Si так, как мы определили, содержит вес узкого места и начинаем следующую итерацию с этим новым набором S. Количество подмножеств, на которые набор S может быть разделён, растёт по экспоненте с каждым шагом, поэтому число итераций пропорционально итерированному логарифму , O(), и полное время составитO() [22].  В модели вычисления, где каждое ребро - машинное целое число, использование повторного деления пополам в этом алгоритме может быть заменено методом разбиения списка Han & Thorup (2002), позволяющим разбить множество S' на O(√m) множеств Si поменьше за один шаг, что даёт полиномиальную временную сложность[23].

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

Темно-синяя полоса отделяет пары Гауссовских простых чисел, минимаксная длина пути которых равняется двум или больше.

Исследована задача максимальной пропускной способности для множеств точек на Евклидовой плоскости. Как и в случае задачи с неориентированным графом, эта Евклидова задача минимаксного пути может быть решена эффективно за счёт поиска Евклидова минимального остовного дерева[en]: каждый путь в дереве - это минимаксный путь. Однако проблема становится более сложной, когда искомый путь должен не только минимизировать длину перехода, но также среди путей с той же длиной перехода должен минимизировать или приближённо минимизировать общую длину пути. С помощью геометрических прогрессий[en]может быть получено приближённые решения [24].

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

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

  1. ↑ Pollack, 1960.
  2. ↑ Shacham, N. (1992), "Multicast routing of hierarchical data", IEEE International Conference on Communications (ICC '92), vol. 3, pp. 1217—1221, doi:10.1109/ICC.1992.268047; Wang, Zheng; Crowcroft, J. (1995), "Bandwidth-delay based routing algorithms", IEEE Global Telecommunications Conference (GLOBECOM '95), vol. 3, pp. 2129—2133, doi:10.1109/GLOCOM.1995.502780
  3. ↑ 1 2 Schulze, Markus (2011), "A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method", Social Choice and Welfare, 36 (2): 267—303, doi:10.1007/s00355-010-0475-4
  4. ↑ 1 2 Fernandez, Elena; Garfinkel, Robert; Arbiol, Roman (1998), "Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths", Operations Research, 46 (3): 293—304, doi:10.1287/opre.46.3.293, JSTOR 222823
  5. ↑ 1 2 Ullah, E.; Lee, Kyongbum; Hassoun, S. (2009), "An algorithm for identifying dominant-edge metabolic pathways", IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009), pp. 144—150
  6. ↑ 1 2 Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "7.3 Capacity Scaling Algorithm", Network Flows: Theory, Algorithms and Applications, Prentice Hall, pp. 210—212, ISBN 0-13-617549-X
  7. ↑ 1 2 Berman, Oded; Handler, Gabriel Y. (1987), "Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations", Transportation Science, 21 (2): 115—122, doi:10.1287/trsc.21.2.115
  8. ↑ Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898—900, doi:10.1287/opre.9.6.898, JSTOR 167055
  9. ↑ 1 2 Punnen, Abraham P. (1991), "A linear time algorithm for the maximum capacity path problem", European Journal of Operational Research, 53 (3): 402—404, doi:10.1016/0377-2217(91)90073-5
  10. ↑ Malpani, Navneet; Chen, Jianer (2002), "A note on practical construction of maximum bandwidth paths", Information Processing Letters, 83 (3): 175—180, doi:10.1016/S0020-0190(01)00323-4, MR 1904226
  11. ↑ Camerini, P. M. (1978), "The min-max spanning tree problem and some extensions", Information Processing Letters, 7 (1): 10—14, doi:10.1016/0020-0190(78)90030-3
  12. ↑ 1 2 Kaibel, Volker; Peinhardt, Matthias A. F. (2006), On the bottleneck shortest path problem (PDF), ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin
  13. ↑ Alt, Helmut; Godau, Michael (1995), "Computing the Fréchet distance between two polygonal curves" (PDF), International Journal of Computational Geometry and Applications, 5 (1—2): 75—91, doi:10.1142/S0218195995000064.
  14. ↑ Leclerc, Bruno (1981), "Description combinatoire des ultramétriques", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (фр.) (73): 5—37, 127, MR 0623034
  15. ↑ Demaine, Erik D.; Landau, Gad M.; Weimann, Oren (2009), "On Cartesian trees and range minimum queries", Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Lecture Notes in Computer Science, vol. 5555, pp. 341—353, doi:10.1007/978-3-642-02927-1_29
  16. ↑ Ошибка в сносках?: Неверный тег <ref>; для сносок Щульце не указан текст
  17. ↑ Более точно есть единственная нить которую метод Щульце не сможет порвать, между двумя кандидатами, которые равны по максимальной пропускной способности друг к другу.
  18. ↑ See 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.
  19. ↑ Duan, Ran; Pettie, Seth (2009), "Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths", Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 384—391. For an earlier algorithm that also used fast matrix multiplication to speed up all pairs widest paths, see Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael (2007), "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, pp. 585—589, doi:10.1145/1250790.1250876, MR 2402484 and Chapter 5 of Vassilevska, Virginia (2008), Efficient Algorithms for Path Problems in Weighted Graphs (PDF), Ph.D. thesis, Report CMU-CS-08-147, Carnegie Mellon University School of Computer Science
  20. ↑ Kaibel, 2006.
  21. ↑ Gabow, 1988.
  22. ↑ Ошибка в сносках?: Неверный тег <ref>; для сносок gt не указан текст
  23. ↑ Han, 2002.
  24. ↑ Bose, 2006.
  25. ↑ Gethner, 1998.

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

Ссылки[править | править код]

Category:Network theory Category:Polynomial-time problems Category:Graph algorithms Category:Computational problems in graph theory

Источник — https://ru.wikipedia.org/w/index.php?title=Участник:AKA_MBG/Задача_о_максимальной_пропускной_способности&oldid=82372836