Алгоритм Хопкрофта – Карпа

Алгоритм Хопкрофта – Карпа

Сорт	Алгоритм графа
Структура данных	График
Худшая производительность	$O(E{\sqrt {V}})$
Наихудшая пространственная сложность	$O(V)$

В информатике — алгоритм Хопкрофта-Карпа (иногда точнее называемый алгоритмом Хопкрофта-Карпа-Карзанова ). — это алгоритм , который принимает на вход двудольный граф и на выходе создает сопоставление максимальной мощности — набор из максимально возможного количества ребер со свойством, что никакие два ребра не имеют общей конечной точки. Он работает в $O(|E|{\sqrt {|V|}})$ время в худшем случае , где $E$ множество ребер в графе, $V$ – множество вершин графа, и предполагается, что $|E|=\Omega (|V|)$. В случае плотных графов временная граница становится $O(|V|^{2.5})$, а для разреженных случайных графов он выполняется за время $O(|E|\log |V|)$ с высокой вероятностью.

Алгоритм был открыт Джоном Хопкрофтом и Ричардом Карпом ( 1973 ) и независимо Александром Карзановым ( 1973 ). Как и в предыдущих методах сопоставления, таких как венгерский алгоритм и работа Эдмондса (1965) , алгоритм Хопкрофта-Карпа многократно увеличивает размер частичного сопоставления путем поиска дополнительных путей . Эти пути представляют собой последовательности ребер графа, которые чередуются между ребрами в совпадении и ребрами вне частичного совпадения, и где начальное и последнее ребро не входят в частичное совпадение. Нахождение дополняющего пути позволяет нам увеличивать размер частичного совпадения, просто переключая края дополняющего пути (вставляя в частичное совпадение те, которых не было, и наоборот). Более простые алгоритмы двустороннего сопоставления, такие как алгоритм Форда – Фулкерсона , находят один дополняющий путь за итерацию: вместо этого алгоритм Хопкрофта-Карпа находит максимальный набор кратчайших дополняющих путей, чтобы гарантировать, что только $O({\sqrt {|V|}})$ необходимы итерации вместо $O(|V|)$ итерации. То же исполнение $O(|E|{\sqrt {|V|}})$ может быть достигнуто для поиска паросочетаний максимальной мощности в произвольных графах с помощью более сложного алгоритма Микали и Вазирани.

Алгоритм Хопкрофта-Карпа можно рассматривать как частный случай алгоритма Диника для задачи максимального потока .

Расширение путей

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

Если $M$ является соответствием, и $P$ является увеличивающим путем относительно $M$, то симметричная разность двух наборов ребер, $M\oplus P$, будет формировать соответствие с размером $|M|+1$. Таким образом, находя дополнительные пути, алгоритм может увеличить размер сопоставления.

Обратно, предположим, что сопоставление $M$ не является оптимальным, и пусть $P$ быть симметричной разностью $M\oplus M^{*}$ где $M^{*}$ является оптимальным соответствием. Потому что $M$ и $M^{*}$ оба паросочетания, каждая вершина имеет степень не выше 2 в $P$. Так $P$ должен образовывать набор непересекающихся циклов путей с равным количеством совпадающих и несовпадающих ребер в $M$, расширения путей для $M$и расширения путей для $M^{*}$; но последнее невозможно, потому что $M^{*}$ является оптимальным. Теперь циклы и пути с равным количеством совпадающих и несовпадающих вершин не влияют на разницу в размерах между $M$ и $M^{*}$, поэтому эта разница равна числу дополняющих путей для $M$ в $P$. Таким образом, всякий раз, когда существует соответствие $M^{*}$ больше, чем текущее соответствие $M$, также должен существовать дополняющий путь. Если дополняющий путь не найден, алгоритм может безопасно завершиться, поскольку в этом случае $M$ должно быть оптимальным.

Увеличивающий путь в задаче сопоставления тесно связан с увеличивающими путями, возникающими в задачах о максимальном потоке , путями, по которым можно увеличить величину потока между терминалами потока. Можно преобразовать задачу двустороннего сопоставления в экземпляр максимального потока, так что чередующиеся пути задачи сопоставления становятся дополнительными путями задачи потока. Достаточно вставить две вершины, исток и сток, и вставить ребра единичной емкости из истока в каждую вершину в $U$, и из каждой вершины в $V$ в раковину; и пусть края из $U$ к $V$ имеют единичную мощность. Обобщение метода, используемого в алгоритме Хопкрофта-Карпа для поиска максимального потока в произвольной сети, известно как алгоритм Диника .

Алгоритм

Алгоритм может быть выражен в следующем псевдокоде .

Входные данные : двудольный граф. $G(U\cup V,E)$

Выход : Сопоставление $M\subseteq E$

$M\leftarrow \emptyset$

повторить

${\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}$ максимальный набор вершинно-непересекающихся кратчайших дополняющих путей

$M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})$

до ${\mathcal {P}}=\emptyset$

Подробнее позвольте $U$ и $V$ быть двумя множествами в двуразделении $G$, и пусть сопоставление из $U$ к $V$ в любой момент быть представлено в виде множества $M$. Алгоритм выполняется поэтапно. Каждый этап состоит из следующих шагов.

• Поиск в ширину разбивает вершины графа на слои. Свободные вершины в $U$ используются в качестве начальных вершин этого поиска и образуют первый уровень разбиения. На первом уровне поиска имеются только несовпадающие ребра, так как свободные вершины в $U$ по определению не смежны ни с одним совпадающим ребром. На последующих уровнях поиска пройденные ребра должны чередоваться совпадающими и несовпадающими. То есть при поиске наследников вершины в $U$, можно проходить только несовпадающие ребра, а из вершины в $V$ можно пересекать только совпадающие края. Поиск завершается на первом уровне $k$ где одна или несколько свободных вершин в $V$ достигаются.
• Все свободные вершины в $V$ на слое $k$ собраны в комплект $F$. То есть вершина $v$ помещается в $F$ тогда и только тогда, когда он заканчивает кратчайший увеличивающий путь.
• Алгоритм находит максимальный набор непересекающихся вершин, увеличивающих пути длины $k$. ( Максимальный означает, что больше таких путей добавлять нельзя. Это отличается от поиска максимального числа таких путей, что было бы сложнее сделать. К счастью, здесь достаточно найти максимальный набор путей.) Этот набор может быть вычисляется методом поиска в глубину (DFS) из $F$ к свободным вершинам в $U$, используя для поиска слои по ширине: DFS разрешено следовать только по ребрам, которые ведут к неиспользуемой вершине на предыдущем уровне, а пути в дереве DFS должны чередоваться между совпадающими и несовпадающими рёбрами. Как только будет найден увеличивающий путь, включающий одну из вершин $F$, DFS продолжается со следующей начальной вершины. Любую вершину, встреченную во время DFS, можно сразу пометить как использованную, так как при отсутствии пути от нее к $U$ в текущей точке DFS, то эту вершину нельзя использовать для достижения $U$ в любой другой точке DFS. Это обеспечивает $O(|E|)$ время работы DFS. Возможна работа и в другом направлении, от свободных вершин в $U$ тем, кто в $V$, который является вариантом, используемым в псевдокоде.
• Каждый из найденных таким образом путей используется для увеличения $M$.

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

Анализ

Каждая фаза состоит из одного поиска в ширину и одного поиска в глубину. Таким образом, одна фаза может быть реализована в $O(|E|)$ время. Поэтому первый ${\sqrt {|V|}}$ фазы, на графике с $|V|$ вершины и $|E|$ края, нужно время $O(|E|{\sqrt {|V|}})$.

Каждая фаза увеличивает длину кратчайшего увеличивающего пути как минимум на один: фаза находит максимальный набор дополнительных путей заданной длины, поэтому любой оставшийся увеличивающий путь должен быть длиннее. Поэтому, как только начальный ${\sqrt {|V|}}$ фазы алгоритма завершены, кратчайший оставшийся увеличивающий путь имеет по крайней мере ${\sqrt {|V|}}$ края в нем. Однако симметричная разница окончательного оптимального сопоставления и частичного сопоставления M, найденного на начальных этапах, образует набор непересекающихся по вершинам дополняющих путей и чередующихся циклов. Если каждый из путей в этой коллекции имеет длину не менее ${\sqrt {|V|}}$, может быть максимум ${\sqrt {|V|}}$ путей в коллекции, а размер оптимального соответствия может отличаться от размера $M$ максимум ${\sqrt {|V|}}$ края. Поскольку каждая фаза алгоритма увеличивает размер паросочетания как минимум на один, может быть не более ${\sqrt {|V|}}$ дополнительные этапы перед завершением работы алгоритма.

Поскольку алгоритм выполняет в общей сложности не более $2{\sqrt {|V|}}$ фаз, общее время занимает $O(|E|{\sqrt {|V|}})$ в худшем случае.

Однако во многих случаях время, затрачиваемое алгоритмом, может быть даже быстрее, чем показывает анализ наихудшего случая. Например, в среднем случае для разреженных двудольных случайных графов Баст и др. (2006) (улучшив предыдущий результат Мотвани 1994 ) показали, что с высокой вероятностью все неоптимальные сопоставления имеют увеличивающиеся пути логарифмической длины. Как следствие, для этих графов алгоритм Хопкрофта–Карпа принимает $O(\log |V|)$ фазы и $O(|E|\log |V|)$ общее время.

Сравнение с другими алгоритмами двустороннего сопоставления

Для разреженных графов алгоритм Хопкрофта-Карпа продолжает иметь наилучшую известную производительность в наихудшем случае, но для плотных графов ( $|E|=\Omega (|V|^{2})$) более поздний алгоритм Alt et al. (1991) достигают немного лучших временных ограничений: $O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)$. Их алгоритм основан на использовании алгоритма максимального потока push-relabel с последующим переключением на метод Хопкрофта-Карпа, когда сопоставление, созданное этим алгоритмом, становится близким к оптимальному.

Несколько авторов провели экспериментальное сравнение алгоритмов двустороннего сопоставления. Их результаты в целом показывают, что метод Хопкрофта-Карпа на практике не так хорош, как в теории: его превосходят как более простые стратегии поиска расширяющих путей, ориентированные на ширину и глубину, так и методы push-relabel. .

Недвудольные графы

Та же идея поиска максимального набора кратчайших дополняющих путей работает и для поиска паросочетаний максимальной мощности в недвудольных графах, и по тем же причинам алгоритмы, основанные на этой идее, принимают $O({\sqrt {|V|}})$ фазы. Однако для недвудольных графов задача поиска дополнительных путей внутри каждой фазы более сложна. Опираясь на работу нескольких более медленных предшественников, Микали и Вазирани (1980) показали, как реализовать фазу в линейном времени, в результате чего был получен недвудольный алгоритм сопоставления с той же временной привязкой, что и алгоритм Хопкрофта-Карпа для двудольных графов. Методика Микали-Вазирани сложна, и ее авторы не предоставили полных доказательств своих результатов; впоследствии, «ясное изложение» было опубликовано Петерсоном и Луи (1988) , а альтернативные методы были описаны другими авторами. В 2012 году Вазирани предложил новое упрощенное доказательство алгоритма Микали-Вазирани.

Псевдокод

/* 
 G = U ∪ V ∪ {NIL}
 where U and V are the left and right sides of the bipartite graph and NIL is a special null vertex
*/
  
function BFS() is
    for each u in U do
        if Pair_U[u] = NIL then
            Dist[u] := 0
            Enqueue(Q, u)
        else
            Dist[u] := ∞
    Dist[NIL] := ∞
    while Empty(Q) = false do
        u := Dequeue(Q)
        if Dist[u] < Dist[NIL] then
            for each v in Adj[u] do
                if Dist[Pair_V[v]] = ∞ then
                    Dist[Pair_V[v]] := Dist[u] + 1
                    Enqueue(Q, Pair_V[v])
    return Dist[NIL] ≠ ∞

function DFS(u) is
    if u ≠ NIL then
        for each v in Adj[u] do
            if Dist[Pair_V[v]] = Dist[u] + 1 then
                if DFS(Pair_V[v]) = true then
                    Pair_V[v] := u
                    Pair_U[u] := v
                    return true
        Dist[u] := ∞
        return false
    return true

function Hopcroft–Karp is
    for each u in U do
        Pair_U[u] := NIL
    for each v in V do
        Pair_V[v] := NIL
    matching := 0
    while BFS() = true do
        for each u in U do
            if Pair_U[u] = NIL then
                if DFS(u) = true then
                    matching := matching + 1
    return matching

Выполнение на примере графа, показывающего входной граф и сопоставление после промежуточной итерации 1 и последней итерации 2.

Объяснение

Пусть вершины нашего графа разделены на 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 с несовпадающими вершинами U. V, всегда возвращаясь от V к U на ребрах, которые в данный момент являются частью сопоставления. В частности, специальной NIL-вершине, соответствующей vDummy, затем присваивается конечное расстояние, поэтому функция BFS возвращает true, если какой-то путь был найден. Если путь не найден, значит, дополнительных путей не осталось и совпадение максимально.

Если BFS возвращает true, то мы можем продолжить и обновить пары вершин на путях минимальной длины, найденных от U до V: мы делаем это, используя поиск в глубину (DFS). Обратите внимание, что каждая вершина в V на таком пути, кроме последней, в данный момент сопоставлена. Таким образом, мы можем исследовать с помощью DFS, убедившись, что пути, по которым мы следуем, соответствуют расстояниям, вычисленным в BFS. Мы обновляем вдоль каждого такого пути, удаляя из сопоставления все ребра пути, которые в данный момент находятся в сопоставлении, и добавляя к сопоставлению все ребра пути, которые в данный момент не находятся в сопоставлении: поскольку это дополняющий путь (первый и последние ребра пути не были частью сопоставления, и путь чередовался между совпадающими и несовпадающими ребрами), то это увеличивает количество ребер в сопоставлении. Это то же самое, что заменить текущее сопоставление симметричной разницей между текущим сопоставлением и всем путем.

Обратите внимание, что код гарантирует, что все дополняющие пути, которые мы рассматриваем, не пересекаются по вершинам. Действительно, после выполнения симметричного различия пути ни одна из его вершин не может быть снова рассмотрена в DFS только потому, что Dist[Pair_V[v]] не будет равен Dist[u] + 1 (это будет именно Dist [у]).

Также обратите внимание, что DFS не посещает одну и ту же вершину несколько раз. Это благодаря следующим строкам:

Dist[u] = ∞
return false

Когда нам не удалось найти кратчайший увеличивающий путь из вершины u, DFS помечает вершину u, устанавливая Dist[u] на бесконечность, чтобы эти вершины больше не посещались.

И последнее наблюдение: на самом деле нам не нужен uDummy: его роль состоит в том, чтобы просто поместить все несовпадающие вершины U в очередь при запуске BFS. Что касается vDummy, то в приведенном выше псевдокоде он обозначен как NIL.

См. также

• Сопоставление максимальной мощности , задача, решаемая алгоритмом, и ее обобщение на недвудольные графы
• Проблема назначения , обобщение этой проблемы на взвешенных графах , решаемая, например, венгерским алгоритмом.
• Алгоритм Эдмондса-Карпа для поиска максимального потока, обобщение алгоритма Хопкрофта-Карпа.

Ссылки

• Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993), Сетевые потоки: теория, алгоритмы и приложения , Прентис-Холл .
• Альт, Х.; Блюм, Н.; Мельхорн, К. ; Пол, М. (1991), «Вычисление соответствия максимальной мощности в двудольном графе во времени». $\scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)$", Information Processing Letters , 37 (4): 237–240, doi : 10.1016/0020-0190(91)90195-N .
• Аннамалай, Чидамбарам (2018), «Нахождение идеальных паросочетаний в двудольных гиперграфах», Combinatorica , 38 (6): 1285–1307, arXiv : 1509.07007 , doi : 10.1007/s00493-017-3567-2 , MR   3910876 , S2CID   199 7334
• Баст, Хольгер; Мельхорн, Курт; Шефер, Гвидо; Тамаки, Хисао (2006), «Алгоритмы сопоставления быстры в разреженных случайных графах», Theory of Computing Systems , 39 (1): 3–14, CiteSeerX   10.1.1.395.6643 , doi : 10.1007/s00224-005-1254-y , МР   2189556 , S2CID   9321036
• Чанг, С. Франк; Маккормик, С. Томас (1990), Более быстрая реализация алгоритма двустороннего сопоставления мощности , Tech. Представитель 90-MSC-005, Факультет коммерции и делового администрирования, Univ. Британской Колумбии . Цитируется Сетубалом (1996) .
• Дарби-Доуман, Кеннет (1980), Использование разреженности в крупномасштабных задачах линейного программирования - Структуры данных и алгоритмы реструктуризации , доктор философии. диссертация, Университет Брюнеля . Цитируется Сетубалом (1996) .
• Диниц, Ефим (2006), «Алгоритм Диница: оригинальная версия и версия Эвена», в Goldreich, Oded ; Розенберг, Арнольд Л .; Селман, Алан Л. (ред.), Теоретическая информатика: очерки памяти Шимона Эвена (PDF) , Конспекты лекций по информатике, том. 3895, Берлин и Гейдельберг: Springer, стр. 218–240, doi : 10.1007/11685654_10 , ISBN.  978-3-540-32880-3 .
• Эдмондс, Джек (1965), «Пути, деревья и цветы», Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , MR   0177907 , S2CID   18909734 .
• Габоу, Гарольд Н. (2017), «Подход к взвешенному сопоставлению для сопоставления максимальной мощности», Fundamenta Informaticae , 154 (1–4): 109–130, arXiv : 1703.03998 , doi : 10.3233/FI-2017-1555 , MR   3690573 , S2CID   386509
• Габоу, Гарольд Н .; Тарьян, Роберт Э. (1991), «Алгоритмы более быстрого масштабирования для общих задач сопоставления графов», Journal of the ACM , 38 (4): 815–853, doi : 10.1145/115234.115366 , S2CID   18350108 .
• Хопкрофт, Джон Э .; Карп, Ричард М. (1973), «Ан н ^5/2 Алгоритм максимальных паросочетаний в двудольных графах», SIAM Journal on Computing , 2 (4): 225–231, doi : 10.1137/0202019 . Ранее было объявлено на 12-м ежегодном симпозиуме по теории коммутации и автоматов, 1971 г.
• Карзанов А.В. (1973), "Точная оценка алгоритма нахождения максимального потока применительно к задаче о представителях", Проблемы кибернетики , 5 : 66–70 . Ранее анонсировано на семинаре по комбинаторной математике (Москва, 1971 г.).
• Микали, С .; Вазирани, В.В. (1980), «Ан $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ Алгоритм поиска максимального соответствия в общих графах», Proc. 21st IEEE Symp. Foundations of Computer Science , стр. 17–27, doi : 10.1109/SFCS.1980.12 , S2CID   27467816 .
• Петерсон, Пол А.; Луи, Майкл К. (ноябрь 1988 г.), «Общий алгоритм максимального соответствия Микали и ( 1–4 ) : 511–533 CiteSeerX   , , » Algorithmica 3 Вазирани ,   -0541 , S2CID   16820 .
• Мотвани, Раджив (1994), «Анализ алгоритмов сопоставления и связанных с ними задач в среднем», Journal of the ACM , 41 (6): 1329–1356, doi : 10.1145/195613.195663 , S2CID   2968208 .
• Сетубал, Жоао К. (1993), «Новые экспериментальные результаты двустороннего соответствия», Proc. Netflow93 , отд. информатики, унив. Пизы, стр. 211–216 . Цитируется Сетубалом (1996) .
• Сетубал, Жоао К. (1996), Последовательные и параллельные экспериментальные результаты с алгоритмами двустороннего сопоставления , Tech. Реп. ИК-96-09, Инт. вычислительной техники, Univ. Кампинас, CiteSeerX   10.1.1.48.3539 .
• Тарьян, Роберт Эндре (1983). Структуры данных и сетевые алгоритмы . Серия региональных конференций CBMS-NSF по прикладной математике. Общество промышленной и прикладной математики. дои : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5 .
• Вазирани, Виджай (2012), Улучшенное определение цветков и более простое доказательство алгоритма сопоставления MV , CoRR abs/1210.4594, arXiv : 1210.4594 , Bibcode : 2012arXiv1210.4594V .