В информатике , то алгоритм Хопкрофт-Карп (иногда более точно называют алгоритм Хопкрофт-Карп-Карзан ) [1] представляет собой алгоритм , который принимает в качестве входного двудольного графа и производит в качестве выходного сигнала с максимальным согласованием числа элементов - это набор , как много кромок насколько это возможно, с тем свойством, что никакие два ребра не имеют общей конечной точки. Он работает ввремя в худшем случае , когда - множество ребер в графе, - множество вершин графа, и предполагается, что . В случае плотных графов временная граница становится, а для разреженных случайных графов он выполняется во временис большой вероятностью. [2]
Класс | Алгоритм графа |
---|---|
Структура данных | График |
Наихудшая производительность | |
Сложность пространства в наихудшем случае |
Алгоритм был найден Джоном Хопкрофтом и Ричардом Карпом ( 1973 ) и независимо Александром Карзановым ( 1973 ). [3] Как и в предыдущих методах сопоставления, таких как венгерский алгоритм и работа Эдмондса (1965) , алгоритм Хопкрофта-Карпа многократно увеличивает размер частичного сопоставления путем поиска дополнительных путей . Эти пути представляют собой последовательности ребер графа, которые чередуются между ребрами в сопоставлении и ребрами из частичного сопоставления, и где начальное и конечное ребро не входят в частичное сопоставление. Нахождение увеличивающего пути позволяет нам увеличивать размер частичного совпадения, просто переключая края увеличивающего пути (вставляя частичное совпадение с теми, которые не были, и наоборот). Более простые алгоритмы для двустороннего сопоставления, такие как алгоритм Форда – Фулкерсона ‚находят один увеличивающий путь за итерацию: алгоритм Хопкрофта-Карпа вместо этого находит максимальный набор кратчайших увеличивающих путей, чтобы гарантировать, что только необходимы итерации вместо итераций. Такое же исполнениеможет быть достигнуто для поиска совпадений максимальной мощности в произвольных графах с помощью более сложного алгоритма Микали и Вазирани. [4]
Алгоритм Хопкрофта – Карпа можно рассматривать как частный случай алгоритма Динича для задачи о максимальном потоке . [5]
Расширение путей
Вершина, которая не является конечной точкой ребра в некотором частичном совпадении называется свободной вершиной . Основная концепция, на которую опирается алгоритм, - это дополняющий путь , путь, который начинается в свободной вершине, заканчивается в свободной вершине и чередуется между несовпадающими и согласованными ребрами в пределах пути. Из этого определения следует, что, за исключением конечных точек, все другие вершины (если есть) в увеличивающем пути должны быть несвободными вершинами. Расширяющий путь может состоять только из двух вершин (обе свободные) и единственного несовпадающего ребра между ними.
Если соответствует, и является дополнительным путем относительно , то симметричная разность двух наборов ребер,, будет соответствовать размеру . Таким образом, найдя дополнительные пути, алгоритм может увеличить размер сопоставления.
Наоборот, предположим, что соответствие не оптимально, и пусть быть симметричной разностью где оптимальное соответствие. Так как а также являются паросочетаниями, каждая вершина имеет степень не выше 2 в . Так должны образовывать набор непересекающихся циклов путей с равным количеством совпадающих и несовпадающих ребер в , дополнительных путей для , и дополнительных путей для ; но последнее невозможно, потому чтооптимально. Теперь циклы и пути с равным количеством совпавших и несовпадающих вершин не влияют на разницу в размере между а также , поэтому эта разница равна количеству дополнительных путей для в . Таким образом, всякий раз, когда существует соответствие больше, чем текущее соответствие , также должен существовать дополнительный путь. Если не удается найти расширяющий путь, алгоритм может безопасно завершиться, поскольку в этом случае должен быть оптимальным.
Расширяющий путь в задаче согласования тесно связан с увеличивающими путями, возникающими в задачах максимального потока , путями, вдоль которых можно увеличить количество потока между терминалами потока. Можно преобразовать задачу двустороннего согласования в пример максимального потока, так что чередующиеся пути задачи согласования становятся дополнительными путями проблемы потока. Достаточно вставить две вершины, источник и сток, и вставить ребра единичной мощности от источника до каждой вершины в, и из каждой вершины в к раковине; и пусть края от к имеют единицу мощности. [6] Обобщение техники, используемой в алгоритме Хопкрофта – Карпа для поиска максимального потока в произвольной сети, известно как алгоритм Динича .
Алгоритм
Алгоритм может быть выражен в следующем псевдокоде .
- Вход : двудольный граф.
- Выход : Соответствие
- повторить
- максимальный набор непересекающихся по вершинам кратчайших дополняющих путей
- до того как
Более подробно пусть а также - два множества в двудольном , и пусть совпадение из к в любой момент можно представить как набор . Алгоритм выполняется поэтапно. Каждый этап состоит из следующих шагов.
- Поиск в ширину разделяет вершины графа в слои. Свободные вершины виспользуются как начальные вершины этого поиска и образуют первый слой разбиения. На первом уровне поиска есть только несовпадающие ребра, так как свободные вершины впо определению не примыкают ни к каким согласованным ребрам. На последующих уровнях поиска пройденные кромки должны чередоваться между совпадающими и несогласованными. То есть при поиске наследников из вершины в, могут быть пересечены только несовпадающие ребра, а из вершины в могут быть пересечены только совпадающие кромки. Поиск заканчивается на первом слое. где одна или несколько свободных вершин в достигнуты.
- Все свободные вершины в на слое собраны в набор . То есть вершина помещается в тогда и только тогда, когда он заканчивается кратчайшим путем увеличения.
- Алгоритм находит максимальный набор вершинных непересекающихся увеличивающих путей длины. ( Максимальный означает, что такие пути больше не могут быть добавлены. Это отличается от поиска максимального количества таких путей, что было бы труднее сделать. К счастью, здесь достаточно найти максимальный набор путей.) Этот набор может быть вычисляется методом поиска в глубину (DFS) из к свободным вершинам в , используя слои в ширину для направления поиска: DFS разрешено следовать только за ребрами, которые ведут к неиспользуемой вершине на предыдущем уровне, а пути в дереве DFS должны чередоваться между совпадающими и несовпадающими ребрами. Как только будет найден дополнительный путь, включающий одну из вершин в, ДФС продолжается со следующей стартовой вершины. Любая вершина, обнаруженная во время DFS, может быть немедленно помечена как использованная, поскольку, если от нее нет пути к в текущей точке DFS, то эту вершину нельзя использовать для достижения в любой другой точке DFS. Это гарантируетвремя работы DFS. Также можно работать в обратном направлении, от свободных вершин в тем, кто в , который является вариантом, используемым в псевдокоде.
- Каждый из найденных таким образом путей используется для увеличения .
Алгоритм завершается, когда в первой в ширину части поиска одной из фаз не обнаруживаются дополнительные пути.
Анализ
Каждая фаза состоит из одного поиска в ширину и одного поиска в глубину. Таким образом, одна фаза может быть реализована ввремя. Поэтому первый фаз, на графике с вершины и края, не торопитесь .
Каждая фаза увеличивает длину кратчайшего пути увеличения по крайней мере на один: фаза находит максимальный набор путей увеличения заданной длины, поэтому любой оставшийся путь увеличения должен быть длиннее. Поэтому, как только начальный фазы алгоритма завершены, самый короткий оставшийся путь дополнения имеет не менее края в нем. Однако симметричная разность окончательного оптимального согласования и частичного согласования M, найденного на начальных этапах, образует совокупность непересекающихся по вершинам дополняющих путей и чередующихся циклов. Если каждый из путей в этой коллекции имеет длину не менее, может быть не больше путей в коллекции, а размер оптимального соответствия может отличаться от размера самое большее края. Поскольку каждая фаза алгоритма увеличивает размер сопоставления по крайней мере на один, может быть не более дополнительные фазы перед завершением алгоритма.
Поскольку алгоритм выполняет в общей сложности не более фаз, это занимает общее время в худшем случае.
Однако во многих случаях время, затрачиваемое алгоритмом, может быть даже быстрее, чем показывает анализ наихудшего случая. Так , например, в среднем случае для разреженных двудольных случайных графов , Баст и др. (2006) (улучшая предыдущий результат Motwani 1994 ) показали, что с высокой вероятностью все неоптимальные сопоставления имеют увеличивающиеся пути логарифмической длины. Как следствие, для этих графов алгоритм Хопкрофта – Карпа принимает фазы и общее время.
Сравнение с другими алгоритмами двудольного сопоставления
Для разреженных графов алгоритм Хопкрофта – Карпа по-прежнему имеет наиболее известную производительность в худшем случае, но для плотных графов () более поздний алгоритм Alt et al. (1991) достигает немного лучших временных рамок,. Их алгоритм основан на использовании алгоритма максимального потока push-relabel, а затем, когда соответствие, созданное этим алгоритмом, становится близким к оптимальному, переключение на метод Хопкрофта – Карпа.
Несколько авторов выполнили экспериментальные сравнения алгоритмов двустороннего сопоставления. Их результаты в целом, как правило, показывают, что метод Хопкрофта – Карпа на практике не так хорош, как в теории: он уступает как более простым стратегиям поиска в ширину и в глубину для поиска дополнительных путей, так и методам push-relabel. . [7]
Недвудольные графы
Та же самая идея поиска максимального набора кратчайших увеличивающих путей работает также для поиска совпадений максимальной мощности в недвудольных графах, и по тем же причинам алгоритмы, основанные на этой идее, принимают фазы. Однако для недвудольных графов задача поиска увеличивающих путей внутри каждой фазы является более сложной. Основываясь на работе нескольких более медленных предшественников, Микали и Вазирани (1980) показали, как реализовать фазу за линейное время, что привело к недвудольному алгоритму сопоставления с той же временной границей, что и алгоритм Хопкрофта – Карпа для двудольных графов. Методика Микали – Вазирани сложна, и ее авторы не предоставили полных доказательств своих результатов; впоследствии Peterson & Loui (1988) опубликовали «ясное изложение». harvtxt error: множественные цели (2 ×): CITEREFPetersonLoui1988 ( справка ), а альтернативные методы были описаны другими авторами. [8] В 2012 году Вазирани предложил новое упрощенное доказательство алгоритма Микали-Вазирани. [9]
Псевдокод
/ * G = U ∪ V ∪ {NIL} где U и V - левая и правая части двудольного графа, а NIL - специальная нулевая вершина* / функция BFS () предназначена для каждого u в U , если Pair_U [u] = NIL, то Расстояние [u]: = 0 Поставить в очередь (Q, u) еще Расстояние [u]: = ∞ Расстояние [NIL]: = ∞ в то время как Empty (Q) = false делать u: = Удалить из очереди (Q) если Dist [u]то для каждого v в Adj [u] выполнить, если Dist [Pair_V [v]] = ∞, то Расст. [Pair_V [v]]: = Расст. [U] + 1 Поставить в очередь (Q, Pair_V [v]) return Dist [NIL] ≠ ∞функция DFS (u) имеет вид, если u ≠ NIL, тогда для каждого v в Adj [u] do, если Dist [Pair_V [v]] = Dist [u] + 1, то если DFS (Pair_V [v]) = true, то Pair_V [v]: = u Pair_U [u]: = v вернуть истину Расстояние [u]: = ∞ вернуть ложь вернуть истинуФункция Hopcroft-Карп является для каждого U в U делать Pair_U [u]: = NIL для каждого v в V делаем Pair_V [v]: = NIL соответствие: = 0 в то время как BFS () = true делать для каждого u в U делать, если Pair_U [u] = NIL, тогда если DFS (u) = true, то соответствие: = соответствие + 1 вернуть соответствие
Объяснение
Пусть вершины нашего графа разделены на U и V, и рассмотрим частичное совпадение, как указано в таблицах Pair_U и Pair_V, которые содержат одну вершину, с которой сопоставляется каждая вершина U и V, или NIL для несовпадающих вершин. Ключевая идея состоит в том, чтобы добавить две фиктивные вершины с каждой стороны графа: uDummy, подключенный ко всем несовпадающим вершинам в U, и vDummy, подключенный ко всем несовпадающим вершинам в V. Теперь, если мы запустим поиск в ширину (BFS) от uDummy до vDummy, тогда мы можем получить пути минимальной длины, которые соединяют в настоящее время несовпадающие вершины в U с несогласованными в настоящее время вершинами в V. Обратите внимание, что, поскольку граф является двудольным, эти пути всегда чередуются между вершинами в U и вершинами в V, и нам требуется наша BFS, что при переходе от V к U мы всегда выбираем совпадающую кромку. Если мы достигаем несовпадающей вершины V, то мы заканчиваем на vDummy, и поиск путей в BFS прекращается. Подводя итог, BFS начинается с несовпадающих вершин в U, переходит ко всем их соседям в V, если все совпадают, то он возвращается к вершинам в U, которым сопоставлены все эти вершины (и которые не были посещены ранее), затем он переходит ко всем соседям этих вершин и т. д., пока одна из вершин, достигнутая в V, не станет несовместимой.
Обратите внимание, в частности, что BFS отмечает несогласованные узлы U с расстоянием 0, затем увеличивает расстояние каждый раз, когда он возвращается к U. Это гарантирует, что пути, рассматриваемые в BFS, имеют минимальную длину для соединения несовпадающих вершин U с несовпадающими вершинами V, всегда возвращаясь от V к U на ребрах, которые в настоящее время являются частью соответствия. В частности, специальной вершине NIL, которая соответствует vDummy, затем назначается конечное расстояние, поэтому функция BFS возвращает истину, если был найден какой-то путь. Если путь не найден, значит, дополнительных путей не осталось и соответствие максимальное.
Если BFS возвращает истину, мы можем продолжить и обновить пары для вершин на путях минимальной длины, найденных от U до V: мы делаем это, используя поиск в глубину (DFS). Обратите внимание, что каждая вершина в V на таком пути, кроме последней, в настоящее время сопоставляется. Таким образом, мы можем исследовать с помощью DFS, убедившись, что пути, по которым мы идем, соответствуют расстояниям, вычисленным в BFS. Мы обновляем вдоль каждого такого пути, удаляя из сопоставления все ребра пути, которые в настоящее время находятся в сопоставлении, и добавляя к сопоставлению все кромки пути, которые в настоящее время не находятся в сопоставлении: так как это дополняющий путь (первый и последние кромки пути не были частью сопоставления, и путь чередовался между сопоставленными и несовпадающими кромками), то это увеличивает количество кромок в сопоставлении. Это то же самое, что заменить текущее совпадение симметричной разницей между текущим совпадением и всем путем.
Обратите внимание, что код гарантирует, что все рассматриваемые дополняющие пути не пересекаются по вершинам. Действительно, после выполнения симметричной разницы для пути ни одна из его вершин не может быть снова рассмотрена в DFS только потому, что Dist [Pair_V [v]] не будет равно Dist [u] + 1 (это будет в точности Dist [u]).
Также обратите внимание, что DFS не посещает одну и ту же вершину несколько раз. Это благодаря следующим строчкам:
Расстояние [u] = ∞вернуть ложь
Когда нам не удалось найти какой-либо кратчайший увеличивающий путь из вершины u, тогда DFS помечает вершину u, устанавливая Dist [u] равным бесконечности, чтобы эти вершины больше не посещались.
И последнее наблюдение: на самом деле uDummy нам не нужен: его роль просто помещать все несовпадающие вершины U в очередь, когда мы запускаем BFS. Что касается vDummy, в псевдокоде выше он обозначен как NIL.
Смотрите также
- Соответствие максимальной мощности , проблема, решаемая алгоритмом, и ее обобщение на недвудольные графы
- Задача присваивания , обобщение этой проблемы на взвешенных графах , решаемая, например, с помощью венгерского алгоритма.
- Алгоритм Эдмондса – Карпа для поиска максимального потока, обобщение алгоритма Хопкрофта – Карпа
Заметки
- ^ Габоу (2017) ; Аннамалай (2018)
- ^ Баст и др. (2006) .
- ^ Диниц (2006) .
- ^ Петерсон, Пол А .; Луи, Майкл К. (1988-11-01). «Общий алгоритм максимального соответствия Микали и Вазирани». Алгоритмика . 3 (1): 511–533. DOI : 10.1007 / BF01762129 . ISSN 1432-0541 . S2CID 16820 .
- ^ Тарджан, Роберт Эндре (1983-01-01). Структуры данных и сетевые алгоритмы . CBMS-NSF Серия региональных конференций по прикладной математике. Общество промышленной и прикладной математики. DOI : 10.1137 / 1.9781611970265 . ISBN 978-0-89871-187-5., стр.102
- ^ Ахадж, Magnanti & Орлин (1993) , раздел 12.3, двудольная проблема соответствия кардинального, стр. 469-470.
- ^ Чанг и Маккормик (1990) ; Дарби-Доуман (1980) ; Сетубал (1993) ; Сетубал (1996) .
- ^ Gabow & Тарьян (1991) .
- ^ Вазирани (2012)
Рекомендации
- Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993), Сетевые потоки: теория, алгоритмы и приложения , Прентис-Холл.
- Alt, H .; Blum, N .; Мельхорн, К .; Пол, М. (1991), "Вычисление максимального соответствия мощности в двудольном графе во времени", Информационные письма , 37 (4): 237–240, DOI : 10.1016 / 0020-0190 (91) 90195-N.
- Annamalai, Chidambaram (2018), " В поисках идеальных паросочетания в двудольных гиперграфах", Combinatorica , 38 (6): 1285-1307, Arxiv : 1509,07007 , DOI : 10.1007 / s00493-017-3567-2 , MR 3910876 , S2CID 1997334
- Баст, Хольгер; Мельхорн, Курт; Шефер, Гвидо; Тамаки, Хисао (2006), «Алгоритмы сопоставления работают быстро в разреженных случайных графах», Теория вычислительных систем , 39 (1): 3–14, DOI : 10.1007 / s00224-005-1254-y , MR 2189556
- Чанг, С. Франк; Маккормик, С. Томас (1990), Более быстрая реализация алгоритма двудольного соответствия мощности , Tech. Rep.90-MSC-005, Факультет торговли и делового администрирования, Univ. Британской Колумбии. Цитируется Сетубалом (1996) .
- Дарби-Доуман, Кеннет (1980), Использование разреженности в крупномасштабных задачах линейного программирования - Структуры данных и алгоритмы реструктуризации , доктор философии. кандидатская диссертация, Брунельский университет. Цитируется Сетубалом (1996) .
- Диниц, Ефим (2006), «Алгоритм Диница: исходная версия и версия Эвена», в Goldreich, Oded ; Розенберг, Арнольд Л .; Зельман, Алан Л. (ред.), Теоретическая информатика: Очерки Памяти Шимона Даже , Lecture Notes в области компьютерных наук, 3895 , Берлин и Гейдельберг: Springer, С. 218-240,. DOI : 10.1007 / 11685654_10.
- Эдмондс, Джек (1965), "Пути, деревья и цветы", Canadian Journal математики , 17 : 449-467, DOI : 10,4153 / CJM-1965-045-4 , MR 0177907.
- Габоу, Гарольд Н. (2017), «Подход взвешенного сопоставления к сопоставлению максимальной мощности», Fundamenta Informaticae , 154 (1–4): 109–130, arXiv : 1703.03998 , doi : 10.3233 / FI-2017-1555 , MR 3690573 , S2CID 386509
- Габоу, Гарольд Н .; Тарьян, Роберт Е. (1991), "Быстрее масштабирования алгоритмы для сопоставления общего графа", Журнал ACM , 38 (4): 815-853, DOI : 10,1145 / 115234,115366 , S2CID 18350108.
- Хопкрофт, Джон Э .; Карп, Ричард М. (1973), "О п 5/2 алгоритма максимальных паросочетаний в двудольных графах", SIAM журнал по вычислениям , 2 (4): 225-231, DOI : 10,1137 / 0202019. Ранее было объявлено на 12-м ежегодном симпозиуме по теории переключений и автоматов в 1971 году.
- Карзанов А.В. (1973), "Точная оценка алгоритма нахождения максимального потока применительно к задаче о представителях", Проблемы кибернетики , 5 : 66–70.. Ранее анонсировано на семинаре по комбинаторной математике (Москва, 1971).
- Микали, С .; Вазирани, В.В. (1980), "Аналгоритм поиска максимального соответствия в общих графах ", Proc. 21st IEEE Symp. Foundations of Computer Science , pp. 17–27, doi : 10.1109 / SFCS.1980.12 , S2CID 27467816.
- Петерсон, Пол А .; Луи, Майкл С. (1988), "Общий алгоритм максимального согласования Микали и Вазираньте", Algorithmica , 3 (1-4): 511-533, CiteSeerX 10.1.1.228.9625 , DOI : 10.1007 / BF01762129 , S2CID 16820.
- Мотвани, Райеев (1994), "Средне-случай , анализ алгоритмов для паросочетаний и связанных с ними задач", Журнал ACM , 41 (6): 1329-1356, DOI : 10,1145 / 195613,195663 , S2CID 2968208.
- Сетубал, Жоао К. (1993), "Новые экспериментальные результаты для двустороннего сопоставления", Proc. Netflow93 , кафедра информатики, Univ. Пизы, стр. 211–216. Цитируется Сетубалом (1996) .
- Сетубал, Жоао К. (1996), Последовательные и параллельные экспериментальные результаты с алгоритмами двустороннего сопоставления , Tech. Представитель IC-96-09, Inst. вычислительной техники, Univ. из Кампинаса, CiteSeerX 10.1.1.48.3539.
- Вазирани, Виджай (2012), Улучшенное определение цветков и более простое доказательство алгоритма сопоставления MV , CoRR abs / 1210.4594, arXiv : 1210.4594 , Bibcode : 2012arXiv1210.4594V.