Ungersk algoritm

Den ungerska metoden är en kombinatorisk optimeringsalgoritm som löser tilldelningsproblemet i polynomtid och som förutsåg senare primal–dual metoder . Den utvecklades och publicerades 1955 av Harold Kuhn , som gav namnet "ungersk metod" eftersom algoritmen till stor del baserades på tidigare verk av två ungerska matematiker: Dénes Kőnig och Jenő Egerváry .

James Munkres granskade algoritmen 1957 och observerade att den är (starkt) polynom . Sedan dess har algoritmen också varit känd som Kuhn–Munkres-algoritmen eller Munkres-tilldelningsalgoritmen . Tidskomplexiteten för den ursprungliga algoritmen var ${\displaystyle O(n^{4})} ,$ dock noterade Edmonds och Karp , och oberoende Tomizawa att den kan modifieras för att uppnå ett ${\ displaystyle O(n^{3})}$ körtid. ^{[ hur? ]} En av de mest populära ^{[ citat behövs ]} $O(n^{3})$ varianter är Jonker–Volgenant-algoritmen. Ford och Fulkerson utökade metoden till generella problem med maximalt flöde i form av Ford-Fulkerson-algoritmen . 2006 upptäcktes att Carl Gustav Jacobi löst uppdragsproblemet på 1800-talet och lösningen hade publicerats postumt 1890 på latin.

Problemet

Exempel

I detta enkla exempel finns det tre arbetare: Paul, Dave och Chris. En av dem ska städa badrummet, en annan sopa golv och den tredje tvättar fönstren, men de kräver olika lön för de olika uppgifterna. Problemet är att hitta det billigaste sättet att tilldela jobben. Problemet kan representeras i en matris över kostnaderna för de arbetare som utför jobbet. Till exempel:

	Rent badrum	Sopa golv	Tvätta fönster
Paul	$2	$3	$3
Dave	$3	$2	$3
Chris	$3	$3	$2

Den ungerska metoden, när den tillämpas på tabellen ovan, skulle ge den lägsta kostnaden: detta är $6, uppnått genom att Paul städa badrummet, Dave sopa golven och Chris tvätta fönstren.

Matrisformulering

I matrisformuleringen får vi en icke-negativ n × n matris , där elementet i den i :e raden och den j -te kolumnen representerar kostnaden för att tilldela det j :te jobbet till den i :te arbetaren. Vi måste hitta en tilldelning av jobben till arbetarna, så att varje jobb tilldelas en arbetare och varje arbetare tilldelas ett jobb, så att den totala kostnaden för uppdraget är minimum.

Detta kan uttryckas som att permutera raderna i en kostnadsmatris C för att minimera spåret av en matris,

\min _{P}\operatörsnamn {Tr} (PC)\;,

där P är en permutationsmatris . (På motsvarande sätt kan kolumnerna permuteras med CP .)

Om målet är att hitta uppdraget som ger maximal kostnad kan problemet lösas genom att negera kostnadsmatrisen C .

Tvådelad grafformulering

Algoritmen kan på motsvarande sätt beskrivas genom att formulera problemet med hjälp av en tvådelad graf. Vi har en komplett tvådelad graf $G=(S,T;E)$ med $n$ arbetarpunktpunkter ( $S$ ) och $n$ jobbpunktpunkter ( $T$ ), och varje kant har en icke-negativ kostnad $c(i,j)$ . Vi vill hitta en perfekt matchning med en lägsta totalkostnad.

Algoritmen i termer av tvådelade grafer

Låt oss kalla en funktion $y:(S\cup T)\to \mathbb {R}$ en potential om $y(i)+y(j)\leq c(i,j)$ för varje $i\in S,j\in T$ . Värdet av potential $y är$ summan av potentialen över alla hörn: $\summa _{v\in S\cup T}y(v)$ .

Kostnaden för varje perfekt matchning är åtminstone värdet av varje potential: den totala kostnaden för matchningen är summan av kostnaderna för alla kanter; kostnaden för varje kant är åtminstone summan av potentialerna för dess ändpunkter; eftersom matchningen är perfekt är varje vertex en ändpunkt med exakt en kant; därför är den totala kostnaden åtminstone den totala potentialen.

Den ungerska metoden hittar en perfekt matchning och en potential så att matchningskostnaden är lika med det potentiella värdet. Detta bevisar att båda är optimala. Faktum är att den ungerska metoden hittar en perfekt matchning av snäva kanter : en kant $ij$ kallas tight för en potentiell $y(i)+y(j)=c(i,j)$ $om$ y . Låt oss beteckna subgrafen för snäva kanter med $G_{y}$ . Kostnaden för en perfekt matchning i $G_{y}$ (om det finns en) är lika med värdet av $y$ .

Under algoritmen upprätthåller vi en potentiell $y$ och en orientering av $G_{y}$ (betecknad med ${\displaystyle {\overrightarrow {G_{y}}}} )$ som har egenskapen att kanterna orienterad från $T$ till $S$ bildar ett matchande $M$ . Inledningsvis $y$ 0 överallt, och alla kanter är orienterade från $S$ till $T$ (så $M$ är tom). I varje steg, antingen modifierar vi $y$ så att dess värde ökar, eller modifierar orienteringen för att få en matchning med fler kanter. Vi upprätthåller invarianten att alla kanter på $M$ är täta. Vi är klara om $M$ är en perfekt matchning.

I ett allmänt steg, låt $R_{S}\subseteq S$ och $R_{T}\subseteq T$ vara de hörn som inte täcks av $M$ (så ${\ displaystyle R_{S}}$ består av hörnen i $S$ utan inkommande kant och $R_{T}$ består av hörnen i $T$ utan utgående kant). Låt $Z$ vara uppsättningen av hörn som kan nås i ${\overrightarrow {G_{y}}}$ från $R_{S}$ med en riktad bana som endast följer kanter som är täta. Detta kan beräknas med bredd-först-sökning .

Om $R_{T}\cap Z$ inte är tom, vänd sedan om orienteringen av en riktad bana i ${\overrightarrow {G_{y}}}$ från ${\ displaystyle R_{S}}$ till $R_{T}$ . Således ökar storleken på motsvarande matchning med 1.

Om $R_{T}\cap Z$ är tom, låt

\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}.

$Δ$ är väldefinierad eftersom minst en sådan kant $ij$ måste existera när matchningen ännu inte är av största möjliga storlek (se följande avsnitt); den är positiv eftersom det inte finns några snäva kanter mellan $Z\cap S$ och $T\setminus Z$ . Öka $y$ med $Δ$ på hörnen på $Z\cap S$ och minska $y$ med $Δ$ på hörnen på $Z\cap T$ . Det resulterande $y$ är fortfarande en potential, och även om grafen $G_{y}$ ändras, innehåller den fortfarande $M$ (se nästa underavsnitt). Vi orienterar de nya kanterna från $S$ till $T$ . Enligt definitionen av $Δ ökar$ mängden $Z$ av hörn som kan nås från $R_{S}$ (observera att antalet snäva kanter inte nödvändigtvis ökar).

Vi upprepar dessa steg tills $M$ är en perfekt matchning, i vilket fall det ger ett minimikostnadsuppdrag. Körtiden för denna version av metoden är $O(n^{4})$ : $M$ utökas $n$ gånger, och i en fas där $M$ är oförändrad, finns det högst $n$ potentiella förändringar (eftersom $Z$ ökar för varje gång). Den tid som är tillräcklig för en potentiell förändring är $O(n^{2})$ .

Bevis på att algoritmen gör framsteg

Vi måste visa att så länge som matchningen inte är av största möjliga storlek, kan algoritmen alltid göra framsteg - det vill säga att antingen öka antalet matchade kanter eller dra åt minst en kant. Det räcker med att visa att minst ett av följande gäller vid varje steg:

$M$ är av största möjliga storlek.
$G_{y}$ innehåller en utökad sökväg.
$G$ innehåller en lössvansad bana : en bana från någon vertex i $R_{S}$ till en vertex i $T\setminus Z$ som består av valfritt antal (eventuellt noll) av tight kanter följt av en enda lös kant. Den bakre lösa kanten på en lös-tailed bana är alltså från $Z\cap S$ , vilket garanterar att $Δ$ är väldefinierad.

Om $M$ är av högsta möjliga storlek är vi såklart klara. Annars måste det enligt Berges lemma finnas en förstärkande väg $P$ med avseende på $M$ i den underliggande grafen $G$ . Den här vägen kanske inte finns i $G_{y}$ : Även om varje jämnt numrerad kant i $P$ är snäv enligt definitionen av $M$ , kan udda numrerade kanter vara lösa och därmed frånvarande från ${\ displaystil G_{y}}$ . En slutpunkt för $P$ är i ${\displaystyle R_{S}} ,$ den andra i $R_{T}$ ; wlog, anta att den börjar i $R_{S}$ . Om varje kant på $P$ är snäv, så förblir det en utökad bana i $G_{y}$ och vi är klara. Annars, låt $uv$ vara den första lösa kanten på $P$ . Om $v\notin Z$ så har vi hittat en lössvansad bana och vi är klara. Annars $v$ nås från någon annan väg $Q$ för snäva kanter från en vertex i $R_{S}$ . Låt $P_{v}$ vara undervägen till $P$ som börjar vid $v$ och fortsätter till slutet, och låt $P'$ vara den väg som bildas genom att resa längs $Q$ tills en vertex på $P_{v}$ nås och fortsätter sedan till slutet av $P_{v}$ . Observera att $P'$ är en förstärkningsbana i $G$ med minst en lös kant mindre än $P$ . $P$ kan ersättas med $P'$ och denna resonemangsprocess itererades (formellt med användning av induktion på antalet lösa kanter) tills antingen en utökad bana i $G_{y}$ eller en lös- svansbana i $G$ finns.

Bevis på att justering av potentialen y lämnar M oförändrad

För att visa att varje kant i $M$ finns kvar efter justering av $y$ räcker det att visa att för en godtycklig kant i $M$ är antingen båda dess ändpunkter, eller ingen av dem, i $Z$ . Låt därför $vu$ vara en kant i $M$ från $T$ till $S$ . Det är lätt att se att om $v$ är i $Z$ så måste $u$ också vara det, eftersom varje kant i $M$ är snäv. Antag nu, motsägelsefullt, att $u\in Z$ men $v\notin Z$ . $u$ själv kan inte vara i $R_{S}$ eftersom det är ändpunkten för en matchad kant, så det måste finnas någon riktad bana av snäva kanter från en vertex i $R_{S}$ till $u$ . Den här vägen måste undvika $v$ , eftersom det är av antagande inte i $Z$ , så vertex omedelbart före $u$ i denna väg är någon annan vertex $v'\in T$ . $v'u$ är en snäv kant från $T$ till $S$ och är alltså i $M$ . Men då $M$ två kanter som delar vertex $u$ , vilket motsäger det faktum att $M$ är en matchning. Således har varje kant i $M$ antingen båda ändpunkterna eller ingen ändpunkt i $Z$ .

Bevis på att $y$ förblir en potential

För att visa att $y$ förblir en potential efter att ha justerats, räcker det att visa att ingen kant har sin totala potential ökad utöver sin kostnad. Detta är redan fastställt för kanter i $M$ i föregående stycke, så överväg en godtycklig kant $uv$ från $S$ till $T$ . Om $y(u)$ ökas med $Δ$ , då antingen $v\in Z\cap T$ , i vilket fall $y(v) )$ minskas med $Δ$ , vilket lämnar kantens totala potential oförändrad, eller $v\in T\setminus Z$ , i vilket fall definitionen av $Δ$ garanterar att $y(u)+y(v)+\Delta \leq c(u,v)$ . Således $y$ en potential.

Matristolkning

Givet $n$ arbetare och uppgifter skrivs problemet i form av en $n$ × $n$ matris

en ₁	en ₂	en ₃	en ₄
b ₁	b ₂	b ₃	b ₄
c ₁	c ₂	c ₃	c ₄
d ₁	d ₂	d ₃	d ₄

där a, b, c och d är arbetare som måste utföra uppgifterna 1, 2, 3 och 4. a ₁ , a ₂ , a ₃ och a ₄ anger de påföljder som uppstår när arbetare "a" utför uppgift 1, 2, 3 respektive 4.

Problemet motsvarar att tilldela varje arbetare en unik uppgift så att den totala straffavgiften minimeras. Observera att varje uppgift endast kan arbetas med av en arbetare.

Steg 1

För varje rad subtraheras dess minimielement från varje element i den raden. Detta gör att alla element har icke-negativa värden. Därför är ett uppdrag med ett totalstraff på 0 per definition ett minimiuppdrag.

Detta leder också till minst en nolla i varje rad. Som sådan kan en naiv girig algoritm försöka tilldela alla arbetare en uppgift med ett straff på noll. Detta illustreras nedan.

0	en ₂	en ₃	en ₄
b ₁	b ₂	b ₃	0
c ₁	0	c ₃	c ₄
d ₁	d ₂	0	d ₄

Nollorna ovan skulle vara de tilldelade uppgifterna.

I värsta fall finns det $n$ ! kombinationer att prova, eftersom flera nollor kan visas i rad om flera element är minimum. Så någon gång borde den här naiva algoritmen kortslutas.

Steg 2

Ibland kan det visa sig att matrisen i detta skede inte kan användas för tilldelning, vilket är fallet för matrisen nedan.

0	en ₂	0	en ₄
b ₁	0	b ₃	0
0	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

För att övervinna detta upprepar vi ovanstående procedur för alla kolumner (dvs minimielementet i varje kolumn subtraheras från alla element i den kolumnen ) och kontrollerar sedan om en tilldelning med straff 0 är möjlig.

I de flesta situationer kommer detta att ge resultatet, men om det fortfarande inte är möjligt måste vi fortsätta.

Steg 3

Alla nollor i matrisen ska täckas genom att markera så få rader och/eller kolumner som möjligt. Steg 3 och 4 utgör ett sätt att åstadkomma detta.

För varje rad, försök att tilldela en godtycklig nolla. Tilldelade uppgifter representeras genom att stjärnmärka en nolla. Observera att tilldelningar inte kan finnas i samma rad eller kolumn.

Vi tilldelar den första nollan i rad 1. Den andra nollan i rad 1 kan inte tilldelas.
Vi tilldelar den första nollan i rad 2. Den andra nollan i rad 2 kan inte tilldelas.
Nollor på rad 3 och rad 4 kan inte tilldelas, eftersom de finns i samma kolumn som nollan som tilldelats på rad 1.

Vi skulle kunna avsluta med ytterligare ett uppdrag om vi väljer en annan ordning av rader och kolumner.

0*	en ₂	0	en ₄
b ₁	0*	b ₃	0
0	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

Steg 4

Täck alla kolumner som innehåller en (stjärnmärkt) nolla.

×	×
0*	en ₂	0	en ₄
b ₁	0*	b ₃	0
0	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

Hitta en icke täckt nolla och prima den. (Om alla nollor är täckta, hoppa till steg 5.)

Om nollan är på samma rad som en stjärnmärkt nolla, täck över motsvarande rad och avslöja kolumnen för den stjärnmärkta nollan.
Sedan, GÅ TILL "Hitta en icke täckt nolla och fylla på den."
- Här avslöjas den andra nollan i rad 1. Eftersom det finns ytterligare en nolla på rad 1, täcker vi rad 1 och avslöjar kolumn 1.
- Sedan avslöjas den andra nollan i rad 2. Vi täcker rad 2 och avslöjar kolumn 2.

	×
0*	en ₂	0'	en ₄	×
b ₁	0*	b ₃	0
0	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄


0*	en ₂	0'	en ₄	×
b ₁	0*	b ₃	0'	×
0	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

Annars har den icke täckta nollan ingen tilldelad nolla på sin rad. Vi skapar en väg som börjar från noll genom att utföra följande steg:
1. Delsteg 1: Hitta en stjärnmärkt nolla i motsvarande kolumn. Om det finns en, gå till understeg 2, annars, sluta.
2. Delsteg 2: Hitta en primerad nolla på motsvarande rad (det ska alltid finnas en). Gå till delsteg 1.

Nollan på rad 3 avslöjas. Vi lägger till den första nollan på rad 1, sedan den andra nollan på rad 1, så är vi klara.


0*	en ₂	0'	en ₄	×
b ₁	0*	b ₃	0'	×
0'	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

(Annas gren fortsatte) För alla nollor som påträffats under vägen, stjärnmärkta nollor och stjärnmärkta nollor.
- När banan börjar och slutar med en primerad nolla vid byte av stjärnmärkta nollor, har vi tilldelat en nolla till.

0	en ₂	0*	en ₄
b ₁	0*	b ₃	0
0*	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

(Annas gren fortsatte) Avprima alla primerade nollor och avtäck alla linjer.
Upprepa de föregående stegen (fortsätt att loopa tills ovanstående "hoppa till steg 5" nås).
- Vi täcker kolumnerna 1, 2 och 3. Den andra nollan på rad 2 är avslöjad, så vi täcker rad 2 och avslöjar kolumn 2:

×		×
0	en ₂	0*	en ₄
b ₁	0*	b ₃	0'	×
0*	c ₂	c ₃	c ₄
0	d ₂	d ₃	d ₄

Alla nollor är nu täckta med ett minimalt antal rader och kolumner.

Den tidigare nämnda detaljerade beskrivningen är bara ett sätt att rita det minsta antalet rader för att täcka alla nollor. Andra metoder fungerar också.

Steg 5

Hitta det lägsta avslöjade värdet. Subtrahera detta från varje omärkt element och lägg till det till varje element som täcks av två rader.

Detta motsvarar att subtrahera ett tal från alla rader som inte täcks och lägga till samma nummer till alla kolumner som täcks. Dessa operationer ändrar inte optimala tilldelningar.

Upprepa steg 4–5 tills en tilldelning är möjlig; detta är när det minsta antalet rader som används för att täcka alla nollor är lika med min (antal personer, antal uppdrag), förutsatt att dummyvariabler (vanligtvis maxkostnaden) används för att fylla i när antalet personer är större än antalet uppdrag.

Om du följer denna specifika version av algoritmen, utgör de stjärnmärkta nollorna minimitilldelningen.

Från Kőnigs teorem kommer det minsta antalet linjer (minsta Vertex-täckning) att vara $n$ (storleken på maximal matchning). Således, när $n$ rader krävs, kan minimikostnadstilldelning hittas genom att endast titta på nollor i matrisen.

Bibliografi

RE Burkard, M. Dell'Amico, S. Martello: Uppdragsproblem (reviderat omtryck). SIAM, Philadelphia (PA.) 2012. ISBN 978-1-61197-222-1
M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italien, 1995.
R. Ahuja , T. Magnanti , J. Orlin , "Network Flows", Prentice Hall, 1993.
S. Martello, "Jeno Egerváry: från ursprunget till den ungerska algoritmen till satellitkommunikation". Central European Journal of Operational Research 18, 47–58, 2010

externa länkar

Bruff, Derek, Uppdragsproblemet och den ungerska metoden (matrisformalism).
Mordecai J. Golin, Bipartite Matching and the Hungarian Method (bigraph formalism), Kursanteckningar, Hong Kong University of Science and Technology .
Ungersk maximal matchningsalgoritm (båda formalismer), på Brilliant hemsida.
RA Pilgrim, Munkres' uppdragsalgoritm. Modifierad för rektangulära matriser , kursanteckningar, Murray State University .
Mike Dawes , The Optimal Assignment Problem , Kursanteckningar, University of Western Ontario .
On Kuhn's Hungarian Method – A tribute from Hungary , András Frank , Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Ungern.
Föreläsning: Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm , Prof. G. Srinivasan, Institutionen för managementstudier, IIT Madras.
Tillägg: Uppdragskänslighetsanalys (med O(n^4) tidskomplexitet), Liu, Shell.
Lös alla uppdragsproblem online , ger en steg för steg förklaring av den ungerska algoritmen.

Genomföranden

Observera att inte alla dessa uppfyller tidskomplexiteten för ${\displaystyle O(n^{3})}, även om de hävdar det.$ Vissa kan innehålla fel, implementera den långsammare ${\displaystyle O(n^{4})}-$ algoritmen eller ha andra ineffektiviteter. I värsta fall kan ett kodexempel länkat från Wikipedia senare modifieras för att inkludera exploateringskod. Verifiering och benchmarking är nödvändigt när man använder sådana kodexempel från okända författare.