Hopcroft–Karp-algoritm

Hopcroft–Karp-algoritm

Klass	Grafalgoritm
Datastruktur	Graf
Prestanda i värsta fall	$O(E{\sqrt {V}})$
Värsta tänkbara rymdkomplexitet	$O(V)$

Inom datavetenskap är Hopcroft -Karp-algoritmen (ibland mer exakt kallad Hopcroft-Karp-Karzanov-algoritmen ) en algoritm som tar en tvådelad graf som indata och producerar en maximal kardinalitetsmatchning som utdata - en uppsättning av så många kanter som möjligt med egenskapen att inga två kanter delar en ändpunkt. Den körs i $O(|E|{\sqrt {|V|}})$ tid i värsta fall , där $E$ är en uppsättning kanter i graf, $V$ är en uppsättning av hörn i grafen, och det antas att $|E|=\Omega (|V|)$ . I fallet med täta grafer blir tidsgränsen $O(|V|^{2.5})$ , och för glesa slumpmässiga grafer körs den i tiden $O(|E|\log |V|)$ med hög sannolikhet.

Algoritmen upptäcktes av John Hopcroft och Richard Karp ( 1973 ) och oberoende av Alexander Karzanov ( 1973 ). Som i tidigare metoder för matchning, såsom den ungerska algoritmen och Edmonds (1965) arbete, ökar Hopcroft-Karp-algoritmen upprepade gånger storleken på en partiell matchning genom att hitta förstärkningsvägar . Dessa banor är sekvenser av kanter på grafen, som alternerar mellan kanter i matchningen och kanter utanför den partiella matchningen, och där den initiala och sista kanten inte är i den partiella matchningen. Genom att hitta en förstärkningsbana kan vi öka storleken på den partiella matchningen, genom att helt enkelt växla kanterna på förstärkningsbanan (sätta in den partiella matchningen av de som inte var det, och vice versa). Enklare algoritmer för tvådelad matchning, såsom Ford–Fulkerson-algoritmen ‚ hittar en förstärkningsväg per iteration: Hopcroft-Karp-algoritmen hittar istället en maximal uppsättning kortaste förstärkningsvägar, för att säkerställa att endast ${\ displaystyle O({\sqrt {|V|}})}$ iterationer behövs istället för $O(|V|)$ iterationer. Samma prestanda för $O(|E|{\sqrt {|V|}})$ kan uppnås för att hitta maximal kardinalitetsmatchningar i godtyckliga grafer, med den mer komplicerade algoritmen av Micali och Vazirani.

Hopcroft–Karp-algoritmen kan ses som ett specialfall av Dinics algoritm för maximalflödesproblemet .

Öka vägar

En vertex som inte är ändpunkten för en kant i någon partiell matchande $M$ kallas en fri vertex . Det grundläggande konceptet som algoritmen förlitar sig på är det med en förstärkande bana , en bana som börjar vid ett fritt hörn, slutar vid ett fritt hörn och växlar mellan omatchade och matchade kanter inom banan. Det följer av denna definition att, förutom ändpunkterna, alla andra hörn (om några) i förstärkningsvägen måste vara icke-fria hörn. En förstärkningsbana kan bestå av endast två hörn (båda fria) och en enda oöverträffad kant mellan dem.

Om $M$ är en matchning, och $P$ är en förstärkningsbana relativt ${\displaystyle M},$ då är den symmetriska skillnaden mellan de två uppsättningarna kanter, $M\ oplus P$ , skulle bilda en matchning med storlek $|M|+1$ . Således, genom att hitta förstärkningsvägar, kan en algoritm öka storleken på matchningen.

Omvänt, anta att en matchande $M$ inte är optimal, och låt $P$ vara den symmetriska skillnaden $M\oplus M^{*}$ där $M^{*}$ är en optimal matchning. Eftersom $M$ och $M^{*}$ båda är matchningar, har varje vertex grad som högst 2 i $P$ . Så $P$ måste bilda en samling av osammanhängande cykler, av banor med lika antal matchade och omatchade kanter i ${\displaystyle M} ,$ av utökade banor för $M$ och av utökade banor för $M^{*}$ ; men det senare är omöjligt eftersom $M^{*}$ är optimal. Nu bidrar inte cyklerna och banorna med lika antal matchade och omatchade hörn till skillnaden i storlek mellan $M$ och $M^{*}$ , så denna skillnad är lika med antal utökade sökvägar för $M$ i $P$ . Således, närhelst det finns en matchande $M^{*}$ större än den nuvarande matchande $M$ , måste det också finnas en utökad väg. Om ingen förstärkningsväg kan hittas kan en algoritm säkert avslutas, eftersom ${\displaystyle M} i detta fall$ måste vara optimal.

En förstärkningsväg i ett matchningsproblem är nära besläktad med de förstärkningsvägar som uppstår vid problem med maximalt flöde, vägar längs vilka man kan öka mängden flöde mellan flödesterminalerna. Det är möjligt att omvandla det tvådelade matchningsproblemet till en maximal flödesinstans, så att de alternerande vägarna för matchningsproblemet blir förstärkande vägar för flödesproblemet. Det räcker med att infoga två hörn, source och sink, och infoga kanter av enhetskapacitet från källan till varje vertex i $U$ och från varje vertex i $V$ till sinken; och låt kanter från $U$ till $V$ ha enhetskapacitet. En generalisering av tekniken som används i Hopcroft-Karps algoritm för att hitta maximalt flöde i ett godtyckligt nätverk kallas Dinics algoritm .

Algoritm

Algoritmen kan uttryckas i följande pseudokod .

Ingång : Bipartit graf $G(U\cup V,E)$

Output : Matchande $M\subseteq E$

$M\leftarrow \emptyset$

upprepa

${\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}$ maximal uppsättning vertex-disjunkte kortaste förstärkningsvägar

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

tills ${\mathcal {P}}=\emptyset$

Mer detaljerat, låt $U$ och $V$ vara de två uppsättningarna i bipartitionen av $G$ och låt matchningen från $U$ till $V$ när som helst representeras som mängden $M$ . Algoritmen körs i faser. Varje fas består av följande steg.

• En sökning på bredden först delar upp grafens hörn i lager. De fria hörnen i $U$ används som startpunkten för denna sökning och bildar det första lagret av partitioneringen. På den första nivån av sökningen finns det bara omatchade kanter, eftersom de fria hörnen i $U$ per definition inte ligger intill några matchade kanter. På efterföljande nivåer av sökningen måste de korsade kanterna växla mellan matchade och omatchade. Det vill säga, när man söker efter efterföljare från en vertex i $U$ får endast omatchade kanter korsas, medan från en vertex i $V$ får endast matchade kanter korsas. Sökningen avslutas vid det första lagret $k$ där en eller flera fria hörn i $V$ nås.
• Alla fria hörn i $V$ vid lager $k$ samlas i en uppsättning $F$ . Det vill säga, en vertex $v$ läggs in i $F$ om och endast om den avslutar en kortaste förstärkningsväg.
• Algoritmen hittar en maximal uppsättning av vertexdisjunkta förstärkningsbanor med längden $k$ . ( Maximal betyder att inga fler sådana vägar kan läggas till. Detta skiljer sig från att hitta det maximala antalet sådana vägar, vilket skulle vara svårare att göra. Lyckligtvis räcker det här för att hitta en maximal uppsättning vägar.) Denna uppsättning kan vara beräknas genom djup-först-sökning (DFS) från $F$ till de fria hörnen i $U$ , med hjälp av bredden första lagret för att styra sökningen: DFS får endast följa kanter som leder till en oanvänd vertex i föregående lager och sökvägar i DFS-trädet måste växla mellan matchade och omatchade kanter. När en förstärkningsväg hittas som involverar en av hörnen i $F$ , fortsätter DFS från nästa startpunkt. Varje hörn som påträffas under DFS kan omedelbart markeras som använd, eftersom om det inte finns någon väg från den till $U$ vid den aktuella punkten i DFS, så kan den vertexen inte användas för att nå $U$ vid någon annan punkt i DFS. Detta säkerställer $O(|E|)$ körtid för DFS. Det är också möjligt att arbeta åt andra hållet, från fria hörn i $U$ till de i $V$ , som är varianten som används i pseudokoden.
• Var och en av sökvägarna som hittas på detta sätt används för att förstora $M$ .

Algoritmen avslutas när inga fler utökade sökvägar hittas i den första sökdelen av bredden i en av faserna.

Analys

Varje fas består av en enda bredd först sökning och en enda djup-först sökning. Således kan en enda fas implementeras i $O(|E|)$ tid. Därför är den första ${\sqrt {|V|}}$ faser, i en graf med $|V|$ hörn och $|E|$ kanter, ta tid $O(|E|{\sqrt {|V|}})$ .

Varje fas ökar längden på den kortaste förstärkningsvägen med minst en: fasen hittar en maximal uppsättning förstärkningsvägar av den givna längden, så eventuell återstående förstärkningsbana måste vara längre. Därför, när initialen ${\sqrt {|V|}}$ faser av algoritmen är klara, den kortaste återstående ökningsvägen har minst ${\sqrt {|V|}}$ kanter i den. Emellertid bildar den symmetriska skillnaden mellan den eventuella optimala matchningen och den partiella matchningen M som hittas av de initiala faserna en samling av vertex-disjunkta förstärkningsvägar och alternerande cykler. Om var och en av vägarna i denna samling har längd minst ${\sqrt {|V|}}$ , det kan vara högst ${\sqrt {|V|}}$ sökvägar i samlingen, och storleken på den optimala matchningen kan skilja sig från storleken på $M$ med högst ${\sqrt {|V|}}$ kanter. Eftersom varje fas i algoritmen ökar storleken på matchningen med minst en, kan det finnas högst ${\sqrt {|V|}}$ ytterligare faser innan algoritmen avslutas.

Eftersom algoritmen utför totalt högst $2{\sqrt {|V|}}$ faser, det tar en total tid av $O(|E|{\sqrt {|V|}})$ i värsta fall.

I många fall kan dock tiden som algoritmen tar vara ännu snabbare än vad den här värsta fallet-analysen indikerar. Till exempel, i det genomsnittliga fallet för glesa tvådelade slumpmässiga grafer, Bast et al. (2006) (som förbättrar ett tidigare resultat från Motwani 1994 ) visade att med hög sannolikhet har alla icke-optimala matchningar förstärkande vägar med logaritmisk längd. Som en konsekvens för dessa grafer tar Hopcroft–Karp-algoritmen $O(\log |V|)$ faser och $O(|E|\log |V|)$ total tid.

Jämförelse med andra tvådelade matchningsalgoritmer

För glesa grafer fortsätter Hopcroft–Karp-algoritmen att ha den mest kända prestanda i värsta fall, men för täta grafer ( $|E|=\Omega (|V|^ {2})$ ) en nyare algoritm av Alt et al. (1991) uppnår en något bättre tidsbunden, $O\left(|V|^{1.5}{\sqrt {\frac {|E|} {\log |V|}}}\right)$ . Deras algoritm är baserad på att använda en push-relabel maximalt flödesalgoritm och sedan, när matchningen som skapas av denna algoritm blir nära optimal, byta till Hopcroft–Karp-metoden.

Flera författare har utfört experimentella jämförelser av tvådelade matchningsalgoritmer. Deras resultat i allmänhet tenderar att visa att Hopcroft–Karp-metoden inte är lika bra i praktiken som den är i teorin: den överträffas både av enklare bredd-först- och djup-först-strategier för att hitta förstärkningsvägar och av push-relabel-tekniker .

Icke-tvådelade grafer

Samma idé att hitta en maximal uppsättning kortaste förstärkningsvägar fungerar också för att hitta maximal kardinalitetsmatchning i icke-tvådelade grafer, och av samma skäl tar algoritmerna baserade på denna idé O ( | V | ) $\ sqrt {|V|}})}$ faser. Men för icke-tvådelade grafer är uppgiften att hitta förstärkningsvägarna inom varje fas svårare. Med utgångspunkt i arbetet från flera långsammare föregångare Micali & Vazirani (1980) hur man implementerar en fas i linjär tid, vilket resulterar i en icke-tvådelad matchningsalgoritm med samma tidsbunden som Hopcroft-Karp-algoritmen för tvådelade grafer. Micali–Vazirani-tekniken är komplex, och dess författare gav inte fullständiga bevis för deras resultat; därefter publicerades en "tydlig utläggning" av Peterson & Loui (1988) och alternativa metoder beskrevs av andra författare. 2012 erbjöd Vazirani ett nytt förenklat bevis på Micali-Vazirani-algoritmen.

Pseudokod

    
        
            
                
    
        
            
                
    
        
            
                 /* G = U ∪ V ∪ {NIL} där U och V är vänster och höger sida av den tvådelade grafen och NIL är en speciell nollpunkt */ funktion  BFS  ()  är  för varje  u  i  U  do  if  Pair_U[u] = NIL  sedan  Dist[u] := 0 Enqueue(Q, u)  else  Dist[u] := ∞ Dist[NIL] := ∞  medan  Empty(Q) = false  do  u := Dequeue(Q)  if  Dist[u ] < Dist[NIL]  gör  sedan  för varje  v  i  Adj[u]  om  Dist[Pair_V[v]] = ∞  sedan  Dist[Pair_V[v]] := Dist[u] + 1 Enqueue(Q, Pair_V[v] )  returnera  Dist[NIL] ≠ ∞  funktion  DFS(u)  är  om  u ≠ NIL  då  för varje  v  i  Adj[u]  gör  om  Dist[Pair_V[v]] = Dist[u] + 1  sedan  om  DFS(Pair_V[v] ]) = sant  sedan  Pair_V[v] := u Pair_U[u] := v  returnera  sant Dist[u] := ∞  returnera  false  return  true  funktion  Hopcroft–Karp  är  för varje  u  i  U  do  Pair_U[u] := NIL  för varje  v  i  V  gör  Pair_V[v] := NIL-matchning := 0  medan  BFS() = sant  gör  för varje  u  i  U  gör  om  Pair_U[u] = NIL  sedan  om  DFS(u) = sant  så  matchar := matchning  +  1  returmatchning 

Utförande på ett exempeldiagram som visar ingångsdiagram och matchning efter mellanliggande iteration 1 och slutlig iteration 2.

Förklaring

Låt hörn av vår graf delas upp i U och V och överväg en partiell matchning, vilket indikeras av tabellerna Pair_U och Pair_V som innehåller den enda vertex som varje hörn av U och V är matchad till, eller NIL för omatchade hörn. Nyckelidén är att lägga till två dummy-hörn på varje sida av grafen: uDummy kopplad till alla omatchade hörn i U och vDummy ansluten till alla omatchade hörn i V. Om vi ​​nu kör en bredd-först-sökning (BFS) från uDummy till vDummy då kan vi få banorna med minimal längd som förbinder för närvarande omatchade hörn i U till för närvarande omatchade hörn i V. Observera att eftersom grafen är tvådelad, växlar dessa banor alltid mellan hörn i U och hörn i V, och vi kräver i vår BFS att när vi går från V till U väljer vi alltid en matchad kant. Om vi ​​når en oöverträffad vertex av V, så slutar vi vid vDummy och sökningen efter banor i BFS avslutas. För att sammanfatta, BFS börjar vid omatchade hörn i U, går till alla deras grannar i V, om alla är matchade går det tillbaka till de hörn i U som alla dessa hörn är matchade till (och som inte besöktes tidigare), sedan den går till alla grannar till dessa hörn, etc., tills en av hörnen som nås i V är oöverträffad.

Observera särskilt att BFS markerar de omatchade noderna för U med avståndet 0, och sedan ökar avståndet varje gång det kommer tillbaka till U. Detta garanterar att vägarna som betraktas i BFS är av minimal längd för att ansluta omatchade hörn av U till omatchade hörn av V samtidigt som man alltid går tillbaka från V till U på kanter som för närvarande är en del av matchningen. Särskilt den speciella NIL-vertexen, som motsvarar vDummy, tilldelas sedan ett ändligt avstånd, så BFS-funktionen returnerar sant om någon väg har hittats. Om ingen sökväg har hittats finns det inga förstärkningsvägar kvar och matchningen är maximal.

Om BFS returnerar sant kan vi gå vidare och uppdatera parningen för hörn på banorna med minimal längd från U till V: vi gör det med en djup-först-sökning (DFS). Observera att varje hörn i V på en sådan väg, förutom den sista, för närvarande matchas. Så vi kan utforska med DFS och se till att vägarna som vi följer motsvarar avstånden som beräknas i BFS. Vi uppdaterar längs varje sådan väg genom att ta bort alla kanter på sökvägen som för närvarande finns i matchningen från matchningen och lägga till alla kanter på vägen som för närvarande inte finns i matchningen till matchningen: eftersom detta är en utökad väg (den första och sista kanterna på banan inte var en del av matchningen, och banan växlade mellan matchade och omatchade kanter), ökar detta antalet kanter i matchningen. Detta är samma sak som att ersätta strömmatchningen med den symmetriska skillnaden mellan strömmatchningen och hela vägen.

Observera att koden säkerställer att alla förstärkningsvägar som vi anser är hörn osammanhängande. Efter att ha gjort den symmetriska skillnaden för en bana kunde ingen av dess hörn övervägas igen i DFS, bara för att Dist[Pair_V[v]] inte kommer att vara lika med Dist[u] + 1 (det skulle vara exakt Dist) [u]).

Observera också att DFS inte besöker samma vertex flera gånger. Detta tack vare följande rader:

Dist[u] = ∞ returnerar falskt

När vi inte kunde hitta någon kortaste förstärkningsväg från ett vertex u, så markerar DFS vertex u genom att ställa in Dist[u] på oändligt, så att dessa hörn inte besöks igen.

En sista observation är att vi faktiskt inte behöver uDummy: dess roll är helt enkelt att sätta alla oöverträffade hörn av U i kön när vi startar BFS. När det gäller vDummy, betecknas det som NIL i pseudokoden ovan.

Se även

• Maximal kardinalitetsmatchning , problemet löst av algoritmen och dess generalisering till icke-tvådelade grafer
• Tilldelningsproblem , en generalisering av detta problem på viktade grafer, löst t.ex. med den ungerska algoritmen
• Edmonds-Karp-algoritmen för att hitta maximalt flöde, en generalisering av Hopcroft-Karp-algoritmen

Anteckningar

• Ahuja, Ravindra K. ; Magnanti, Thomas L. ; Orlin, James B. (1993), Nätverksflöden: teori, algoritmer och tillämpningar , Prentice-Hall .
• Alt, H.; Blum, N.; Mehlhorn, K .; Paul, M. (1991), "Beräknar en maximal kardinalitetsmatchning i en tvådelad graf i tid $\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 .
•    Annamalai, Chidambaram (2018), "Finding perfect matchings in bipartite hypergraphs", Combinatorica , 38 (6): 1285–1307, arXiv : 1509.07007 , doi : 10.1007/s00493-017-915 , 7C 3-017-915 , 7C 97334
•   Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Matchningsalgoritmer är snabba i sparse random graphs", Theory of Computing Systems , 39 (1): 3–14, doi : 10.1007/s00224-005-1254-y , MR 21829506 , MR 21829556 , 69  
• Chang, S. Frank; McCormick, S. Thomas (1990), A faster implementation of a bipartite cardinity matching algorithm , Tech. Rep. 90-MSC-005, fakulteten för handel och företagsekonomi, Univ. av British Columbia . Som citeras av Setubal (1996) .
• Darby-Dowman, Kenneth (1980), Exploateringen av sparsitet i storskaliga linjära programmeringsproblem – Datastrukturer och omstruktureringsalgoritmer , Ph.D. avhandling, Brunel University . Som citeras av Setubal (1996) .
• Dinitz, Yefim (2006), "Dinitz' Algorithm: Originalversionen och Evens version", i Goldreich, Oded ; Rosenberg, Arnold L. ; Selman, Alan L. (red.), Theoretical Computer Science: Essays in Memory of Shimon Even (PDF) , Lecture Notes in Computer Science, vol. 3895, Berlin och Heidelberg: Springer, s. 218–240, doi : 10.1007/11685654_10 .
•    Edmonds, Jack (1965), "Paths, Trees and Flowers", Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , MR 0177907 , S2CID 340 189 .
•    Gabow, Harold N. (2017), "The weighted matching approach to maximum cardinality matching", Fundamenta Informaticae , 154 (1–4): 109–130, arXiv : 1703.03998 , doi : 10.3233/FI-25517-9MR 35517 , 7MR 5017-9 , S2CID 386509
•   Gabow, Harold N .; Tarjan, Robert E. (1991), "Faster scaling algorithms for general graph matching problems", Journal of the ACM , 38 (4): 815–853, doi : 10.1145/115234.115366 , S2CID 18350108 .
• Hopcroft, John E .; Karp, Richard M. (1973), "An n ^5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing , 2 (4): 225–231, doi : 10.1137/0202019 . Tidigare tillkännagiven vid det 12:e årliga symposiet om omkopplings- och automatteori, 1971.
• Karzanov, AV (1973), "En exakt uppskattning av en algoritm för att hitta ett maximalt flöde, applicerad på problemet på representanter", Problems in Cybernetics , 5 : 66–70 . Tidigare tillkännagiven vid seminariet om kombinatorisk matematik (Moskva, 1971).
•   Micali, S .; Vazirani, VV (1980), "En ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}-$ algoritm för att hitta maximal matchning i allmänna grafer ", Proc. 21:a IEEE Symp. Foundations of Computer Science , s. 17–27, doi : 10.1109/SFCS.1980.12 , S2CID 27467816 .
•     Peterson, Paul A.; Loui, Michael C. (november 1988), "The general maximum matching algorithm of Micali and Vazirani", Algorithmica , 3 (1–4): 511–533, CiteSeerX 10.1.1.228.9625 , doi : 10.1007 , ISSNF 3212097/21207/21207/212043 -0541 , S2CID 16820 .
•   Motwani, Rajeev (1994), "Average-case analysis of algorithms for matchings and related problems", Journal of the ACM , 41 (6): 1329–1356, doi : 10.1145/195613.195663 , S2CID 2968208 .
• Setubal, João C. (1993), "Nya experimentella resultat för tvådelad matchning", Proc. Netflow93 , Institutionen för informatik, Univ. av Pisa, s. 211–216 . Som citeras av Setubal (1996) .
•   Setubal, João C. (1996), Sekventiella och parallella experimentella resultat med bipartite matchande algoritmer, Tech. Rep. IC-96-09, Inst. of Computing, Univ. från Campinas, CiteSeerX 10.1.1.48.3539 .
•   Tarjan, Robert Endre (1983). Datastrukturer och nätverksalgoritmer . CBMS-NSF Regional Conference Series in Applied Mathematics. Föreningen för industriell och tillämpad matematik. doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5 .
• Vazirani, Vijay (2012), An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm , CoRR abs/1210.4594, arXiv : 1210.4594 , Bibcode : 2012arXiv12410 4 .