Проблема самого широкого пути - Widest path problem

На этом графике самый широкий путь от Maldon к Feering имеет пропускную способность 29 и проходит через Clacton, Типтри, Harwich, и Blaxhall.

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

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

Тесно связанная проблема, задача минимаксного пути, запрашивает путь, который минимизирует максимальный вес любого из его ребер. В нем есть приложения, которые включают планирование транспортировки.[7] Любой алгоритм для задачи о самом широком пути может быть преобразован в алгоритм для задачи о минимаксном пути или наоборот, изменив смысл всех сравнений весов, выполняемых алгоритмом, или, что то же самое, заменив каждый вес ребра его отрицанием.

Ненаправленные графы

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

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

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

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

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

Направленные графы

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

Все пары

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

Чтобы вычислить ширину самого широкого пути для всех пар узлов в плотный ориентированный граф, такой как те, которые возникают в приложении для голосования, асимптотически самый быстрый из известных подходов требует времени О(п(3 + ω) / 2) где ω - показатель степени быстрое матричное умножение. Используя наиболее известные алгоритмы умножения матриц, эта временная граница становится О(п2.688).[18] Вместо этого в эталонной реализации метода Шульце используется модифицированная версия более простого Алгоритм Флойда-Уоршолла, который занимает О(п3) время.[3] За разреженные графики, может быть более эффективным многократное применение алгоритма самого широкого пути с одним источником.

Единственный источник

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

Единый источник и единый пункт назначения

Берман и Хэндлер (1987) Предлагаем, чтобы служебные автомобили и автомобили экстренных служб использовали минимаксные пути при возвращении после вызова службы поддержки на свою базу. В этом приложении время возврата менее важно, чем время ответа, если другой вызов службы происходит, когда транспортное средство находится в процессе возврата. Используя минимаксный путь, где вес ребра - это максимальное время прохождения от точки на границе до самого дальнего возможного вызова службы, можно спланировать маршрут, который минимизирует максимально возможную задержку между получением вызова службы и прибытием отвечающий автомобиль.[7] Улла, Ли и Хассун (2009) использовать максиминные пути для моделирования доминирующих цепочек реакций в метаболические сети; в их модели вес ребра - это свободная энергия метаболической реакции, представленной ребром.[5]

Еще одно применение широчайших путей возникает в Алгоритм Форда – Фулкерсона для проблема максимального расхода. Неоднократное увеличение потока по пути максимальной пропускной способности в остаточной сети потока приводит к небольшой границе, О(м бревно U), от количества аугментаций, необходимых для определения максимального потока; здесь предполагается, что мощности ребер являются целыми числами, не более чем U. Однако этот анализ не зависит от поиска пути с точным максимумом пропускной способности; любой путь, пропускная способность которого находится в пределах постоянного максимального коэффициента. Объединяя эту идею приближения с методом увеличения кратчайшего пути Алгоритм Эдмондса – Карпа приводит к алгоритму максимального расхода со временем работы О(мин бревно U).[6]

Можно очень эффективно находить пути максимальной емкости и минимаксные пути с одним источником и одним местом назначения даже в моделях вычислений, которые позволяют только сравнения весов ребер входного графа, а не арифметические операции с ними.[12][19] Алгоритм поддерживает набор S ребер, которые, как известно, содержат ребро узкого места оптимального пути; первоначально, S это просто набор всех м ребра графа. На каждой итерации алгоритма он разбивает S в упорядоченную последовательность подмножеств S1, S2, ... примерно равного размера; количество подмножеств в этом разделе выбирается таким образом, чтобы все точки разделения между подмножествами можно было найти путем повторного определения медианы во времени О(м). Затем алгоритм повторно взвешивает каждое ребро графа по индексу подмножества, содержащего это ребро, и использует модифицированный алгоритм Дейкстры на перезвешенном графе; на основе результатов этого вычисления он может определить за линейное время, какой из подмножеств содержит вес края узкого места. Затем он заменяет S подмножеством Sя что он определил, что он должен содержать вес узкого места, и начинает следующую итерацию с этим новым наборомS. Количество подмножеств, в которые S могут быть разделены экспоненциально с каждым шагом, поэтому количество итераций пропорционально повторный логарифм функция О(бревно*п), а общее время О(м бревно*п).[19] В модели вычислений, где каждый вес ребра является машинным целым числом, использование повторного деления пополам в этом алгоритме может быть заменено методом разделения списка Хан и Торуп (2002), позволяя S быть разделенным на О(√м) меньшие наборы Sя за один шаг и приводит к линейной общей временной шкале.[20]

Евклидовы точечные множества

Темно-синяя полоса разделяет пары Гауссовские простые числа минимаксная длина пути которого равна 2 или более.

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

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

Рекомендации

  1. ^ Поллак, Морис (1960), «Максимальная пропускная способность в сети», Исследование операций, 8 (5): 733–736, Дои:10.1287 / opre.8.5.733, JSTOR  167387
  2. ^ Шахам, Н. (1992), "Многоадресная маршрутизация иерархических данных", Международная конференция IEEE по коммуникациям (ICC '92), 3, стр. 1217–1221, Дои:10.1109 / ICC.1992.268047, HDL:2060/19990017646, ISBN  978-0-7803-0599-1; Ван, Чжэн; Кроукрофт, Дж. (1995), "Алгоритмы маршрутизации на основе задержки полосы пропускания", Международная конференция по телекоммуникациям IEEE (GLOBECOM '95), 3, стр. 2129–2133, Дои:10.1109 / GLOCOM.1995.502780, ISBN  978-0-7803-2509-8
  3. ^ а б c Шульце, Маркус (2011), «Новый монотонный, независимый от клонов, обратносимметричный и согласованный по Кондорсе метод выборов с одним победителем», Социальный выбор и благосостояние, 36 (2): 267–303, Дои:10.1007 / s00355-010-0475-4
  4. ^ а б Фернандес, Елена; Гарфинкель, Роберт; Арбиоль, Роман (1998), "Мозаика аэрофотоснимков по швам, обозначенным кратчайшими путями узких мест", Исследование операций, 46 (3): 293–304, Дои:10.1287 / opre.46.3.293, JSTOR  222823
  5. ^ а б Уллах, Э .; Ли, Кёнбум; Хассун, С. (2009), «Алгоритм определения метаболических путей с доминирующим краем», Международная конференция IEEE / ACM по автоматизированному проектированию (ICCAD 2009), стр. 144–150
  6. ^ а б Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993), "7.3 Алгоритм масштабирования емкости", Сетевые потоки: теория, алгоритмы и приложения, Прентис Холл, стр. 210–212, ISBN  978-0-13-617549-0
  7. ^ а б Берман, Одед; Хэндлер, Габриэль Ю. (1987), «Оптимальный минимаксный путь от одного обслуживающего устройства в сети до не обслуживающих пунктов назначения», Транспортная Наука, 21 (2): 115–122, Дои:10.1287 / trsc.21.2.115
  8. ^ Ху, Т. С. (1961), "Проблема маршрута с максимальной пропускной способностью", Исследование операций, 9 (6): 898–900, Дои:10.1287 / opre.9.6.898, JSTOR  167055
  9. ^ а б Пуннен, Абрахам П. (1991), "Алгоритм с линейным временем для задачи максимальной пропускной способности пути", Европейский журнал операционных исследований, 53 (3): 402–404, Дои:10.1016/0377-2217(91)90073-5
  10. ^ Малпани, Навнит; Chen, Jianer (2002), "Примечание о практическом построении путей с максимальной пропускной способностью", Письма об обработке информации, 83 (3): 175–180, Дои:10.1016 / S0020-0190 (01) 00323-4, МИСТЕР  1904226
  11. ^ Камерини, П. М. (1978), "Задача минимального и максимального остовного дерева и некоторые расширения", Письма об обработке информации, 7 (1): 10–14, Дои:10.1016/0020-0190(78)90030-3
  12. ^ а б c Кайбель, Фолькер; Пейнхардт, Маттиас А. Ф. (2006), О проблеме кратчайшего пути узкого места (PDF), ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin
  13. ^ Альт, Гельмут; Годау, Майкл (1995), «Вычисление расстояния Фреше между двумя многоугольными кривыми» (PDF), Международный журнал вычислительной геометрии и приложений, 5 (1–2): 75–91, Дои:10.1142 / S0218195995000064.
  14. ^ Леклерк, Бруно (1981), "Описание Combinatoire des ultramétriques", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (на французском языке) (73): 5–37, 127, МИСТЕР  0623034
  15. ^ Демейн, Эрик Д.; Ландау, Гад М.; Вейманн, Орен (2009), «О декартовых деревьях и минимальных запросах диапазона», Автоматы, языки и программирование, 36-й международный коллоквиум, ICALP 2009, Родос, Греция, 5-12 июля 2009 г., Конспект лекций по информатике, 5555, стр. 341–353, Дои:10.1007/978-3-642-02927-1_29, HDL:1721.1/61963, ISBN  978-3-642-02926-4
  16. ^ В частности, единственный вид связи, которую метод Шульце не может разрушить, - это отношения между двумя кандидатами, у которых есть одинаково широкие пути друг к другу.
  17. ^ См. Джесси Пламондон-Уиллард, Выборы совета директоров для использования предпочтительного голосования, Май 2008 г .; Марк Райан, Результаты выборов в Правление Викимедиа в 2008 г., Июнь 2008 г .; Выборы в Правление 2008 г., Июнь 2008 г .; и Выборы в Правление 2009 г., Август 2009 г.
  18. ^ Дуан, Ран; Петти, Сет (2009), «Быстрые алгоритмы для (макс., Мин.) -Матричного умножения и кратчайшие пути узких мест», Материалы 20-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '09), стр. 384–391. Для более раннего алгоритма, который также использовал быстрое умножение матриц для ускорения самых широких путей всех пар, см. Василевска, Вирджиния; Уильямс, Райан; Юстер, Рафаэль (2007), "Узкие места всех пар для общих графов в истинно субкубическом времени", Материалы 39-го ежегодного симпозиума ACM по теории вычислений (STOC '07), Нью-Йорк: ACM, стр. 585–589, CiteSeerX  10.1.1.164.9808, Дои:10.1145/1250790.1250876, ISBN  9781595936318, МИСТЕР  2402484 и глава 5 Василевская, Вирджиния (2008), Эффективные алгоритмы решения проблем пути в взвешенных графах (PDF), Кандидат наук. дипломная работа, отчет CMU-CS-08-147, Школа компьютерных наук Университета Карнеги-Меллона
  19. ^ а б Габоу, Гарольд Н .; Тарджан, Роберт Э. (1988), «Алгоритмы для двух задач оптимизации узких мест», Журнал алгоритмов, 9 (3): 411–417, Дои:10.1016/0196-6774(88)90031-4, МИСТЕР  0955149
  20. ^ Хан, Ицзе; Торуп, М. (2002), "Целочисленная сортировка в O (п√журнал журнал п) ожидаемое время и линейное пространство », Proc. 43-й ежегодный симпозиум по основам компьютерных наук (FOCS 2002), стр. 135–144, Дои:10.1109 / SFCS.2002.1181890, ISBN  978-0-7695-1822-0.
  21. ^ Бозе, Просенджит; Махешвари, Анил; Нарасимхан, Гири; Smid, Michiel; Zeh, Norbert (2004), "Приближение геометрических кратчайших узких мест", Вычислительная геометрия. Теория и приложения, 29 (3): 233–249, Дои:10.1016 / j.comgeo.2004.04.003, МИСТЕР  2095376
  22. ^ Гетнер, Эллен; Вагон, Стан; Вик, Брайан (1998), "Прогулка по простым числам Гаусса", Американский математический ежемесячный журнал, 105 (4): 327–337, Дои:10.2307/2589708, JSTOR  2589708, МИСТЕР  1614871.