Ungersk algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 mars 2020; kontroller kräver 6 redigeringar .

Den ungerska algoritmen är en optimeringsalgoritm som löser tilldelningsproblemet i polynomtid (se operations research ). Den utvecklades och publicerades av Harold Kuhn 1955 . Författaren gav den namnet "Ungerska metoden" på grund av att algoritmen till stor del är baserad på två ungerska matematikers tidigare arbete König och Egerváry

James Mancres observerade 1957 att algoritmen är (enbart) polynom. Sedan dess har algoritmen också varit känd som Kuhn-Mankres- algoritmen eller Mankres-algoritmen för att lösa tilldelningsproblemet . Tidskomplexiteten för den ursprungliga algoritmen var, men Edmonds Karp såväl visade att den kunde modifieras för att uppnå en körtid på. Den modifierade ungerska algoritmen kallas Hopcroft-Karp-algoritmen. Ford och Fulkerson utökade metoden till allmänna transportproblem. År 2006 upptäcktes att Jacobi hade hittat en 1800-talslösning på uppdragsproblemet, som publicerades på latin i en postum 1890-samling av tidningar. [1] [2] $O(n^{4})$ $O(n^{3})$

Exempel

Anta att det är tre anställda: Ivan, Peter och Andrey. Det är nödvändigt att fördela utförandet av tre typer av arbete mellan dem (som vi kommer att kalla A, B, C), varje arbetare måste endast utföra en typ av arbete. Hur gör man det på ett sådant sätt att man spenderar minsta möjliga summa pengar på arbetarnas löner? Först måste du bygga en kostnadsmatris .

	A	B	C
Ivan	10 000 rub.	20 000 rub.	30 000 rub.
Peter	30 000 rub.	30 000 rub.	30 000 rub.
Andrew	30 000 rub.	30 000 rub.	20 000 rub.

Den ungerska algoritmen som tillämpas på tabellen ovan ger oss den nödvändiga fördelningen: Ivan gör jobb A, Peter gör jobb B, Andrey gör jobb C.

Förklaring av problemet

Givet en icke-negativ n × n matris , där elementet i den i : te raden och den j -te kolumnen motsvarar kostnaden för att utföra den j : te typen av arbete av den i :e arbetaren. Det är nödvändigt att hitta en sådan överensstämmelse mellan arbete och anställda så att arbetskostnaderna är de lägsta. Om målet är att hitta destinationen med den högsta kostnaden, reduceras lösningen till att lösa det just formulerade problemet genom att ersätta varje kostnad C med skillnaden mellan den maximala kostnaden och C . [3]

Huvudidéer

Algoritmen bygger på två idéer:

om samma antal subtraheras från alla element i en viss rad eller kolumn , kommer den totala kostnaden att minska med , och den optimala lösningen kommer inte att förändras; $y$ $y$
om det finns en nollkostnadslösning så är den optimal.

Algoritmen letar efter värden som ska subtraheras från alla element i varje rad och varje kolumn (olika för olika rader och kolumner), så att alla element i matrisen förblir icke-negativa, men en nolllösning visas.

Definitioner

Algoritmen är lättare att beskriva om problemet formuleras med hjälp av en tvådelad graf . Givet en fullständig tvådelad graf G=(S, T; E) med n hörn som motsvarar anställda ( S ) och n hörn som motsvarar typer av arbete ( T ); kostnaden för varje kant c(i, j) är icke-negativ. Det krävs för att hitta en perfekt eller komplett matchning till lägsta kostnad.

Vi kommer att kalla funktionen potential if för varje . Det potentiella värdet definieras som . Det är lätt att se att kostnaden för en perfekt matchning inte är mindre än värdet av någon potential. Den ungerska metoden finner en full matchning och en potential med samma kostnad/värde, vilket bevisar att båda kvantiteterna är optimala. Faktum är att han hittar en perfekt matchning av stela kanter: en kant sägs vara stel för potentialen om . Den stela kantens subgraf kommer att betecknas som . Kostnaden för en fullständig matchning i (om den finns) är lika med . $y\colon (S\cup T)\to \mathbb {R}$ $y(i)+y(j)\leq c(i,j)$ $i\in S,j\in T$ $y=\sum _{v\in S\cup T}y(v)$ $I j$ $y$ $y(i)+y(j)=c(i,j)$ ${\mathbf {G_{y))}$ ${\mathbf {G_{y))}$ $y$

Algoritm i termer av tvådelade grafer

Algoritmen lagrar i minnet potentialen och orienteringen (ställer in riktningen) för varje stel kant, som har egenskapen att kanterna riktas från för att bilda en matchning, som vi betecknar med . En riktad graf som består av stela kanter med en given orientering betecknas med . Således finns det tre typer av kanter när som helst: $y\$ $T\$ $S\$ $M$ $\mathbf {{\overrightarrow {G}}_{y}}$

icke-styv (och inte tillhörande ) $M\$
tuff men inte tillhörande $M\$
hårt och ägt $M\$

Inledningsvis är överallt 0, och alla kanter är riktade från till (alltså tomma). Vid varje steg modifieras antingen så att uppsättningen av hörn , som definieras i nästa stycke, ökas, eller så ändras orienteringen för att erhålla en matchning med ett större antal kanter; det förblir alltid sant att alla kanter på är stela. Processen avslutas om är en perfekt matchning. $y\$ $S\$ $T\$ $M\$ $y\$ $Z\$ $M\$ $M\$

Låt vid varje steg och vara uppsättningen av hörn som inte faller in mot kanter från (det vill säga uppsättningen av hörn från , som inte inkluderar någon kant, men uppsättningen av hörn från , från vilken ingen kant kommer ut). Beteckna med uppsättningen av hörn som kan nås från till (den kan hittas genom sökning på bredden först ). $R_{S}\subseteq S$ $R_{T}\subseteq T$ $M\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Om det inte är tomt betyder det att det finns minst en väg till från till . Vi väljer vilken som helst av dessa vägar och ändrar orienteringen på alla dess kanter till det omvända. Storleken på matchningen kommer att öka med 1. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

Som bevis noterar vi två uppenbara fakta:

På den valda banan växlar kanter från till kanter från till . Detta följer av den tvådelade grafen. $S\$ $T\$ $T\$ $S\$
Det första hörnet på banan tillhör , och det sista hörnet tillhör . Därför är dess första och sista kanter riktade från till . $S\$ $T\$ $S\$ $T\$

Per definition följer det att på den valda vägen växlar kanterna som tillhör och inte tillhör, och de första och sista kanterna hör inte till , det vill säga vägen höjs, varifrån påståendet som bevisas följer. $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$ $M\$

Om den är tom, lägg . är positivt eftersom det inte finns några hårda kanter mellan och . $R_{T}\cap Z$ $\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $\Delta$ $Z\cap S$ $T\setminus Z$

Låt verkligen en sådan kant (i, j) existera. Eftersom , men , kan spetsen nås från till , men spetsen går inte att nå. $i\i Z$ $j\notin Z$ $jag\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Kan därför inte innehålla kanter (i, j). Därför , varifrån . Eftersom det är nåbart från till finns det en väg till från någon vertex som tillhör . Tänk på den sista kanten av denna väg. Beteckna det (k, i). Eftersom det är tillgängligt från till , men oåtkomligt, . Sedan , . Därför är infallande till två kanter från : och , vilket är omöjligt, eftersom är en matchning. Motsägelse. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\i M$ $i\notin R_{S}$ $jag\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $jag\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neq j$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\i M$ $jag\$ $M\$ $(I j)\$ $(i,k)\$ $M\$

Låt oss öka med på hörnen från och minska med vid de hörn som ingår i . Den nya förblir potential. $y\$ $\Delta$ $Z\cap S$ $y\$ $\Delta$ $Z\cap T$ $y\$

För alla kanter (i, j), , : $i\i S$ $j\in T$

om , , så ändras inte c(i, j)-y(i)-y(j) eftersom varken y(i) eller y(j) $i\notin Z$ $j\notin Z$
om , , så ändras inte c(i, j)-y(i)-y(j) eftersom y(i) ökar med , och y(j) minskar lika mycket $i\i Z$ $j\in Z$ $\Delta$
om , , skillnaden c(i, j)-y(i)-y(j) ökar med , förblir därför icke-negativ $i\notin Z$ $j\in Z$ $\Delta$
om , , skillnaden c(i, j)-y(i)-y(j) minskar med , men förblir fortfarande icke-negativ, eftersom är den minsta av sådana skillnader. $i\i Z$ $j\notin Z$ $\Delta$ $\Delta$

Grafen ändras, men innehåller trots detta . $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$

I själva verket, för att utesluta från någon kant (i, j), , , är det nödvändigt att göra det icke-styvt, det vill säga att öka skillnaden c(i, j)-y(i)-y(j) . Som vi har sett ökar skillnaden endast om , , med andra ord är ouppnåeligt från , men är uppnåeligt. Men i det här fallet kan kanten (j, i) inte tillhöra , därför hör kanten inte till . $\mathbf {{\overrightarrow {G}}_{y}}$ $i\i S$ $j\in T$ $i\notin Z$ $j\in Z$ $i$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $M$

Orientera de nya kanterna från till . Per definition kommer uppsättningen av hörn som kan nås från att öka (och antalet stela kanter ökar inte nödvändigtvis). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

För att bevisa detta påstående, bevisar vi först att ingen vertex försvinner från Z. Låt . Sedan finns det en bana från någon vertex som tillhör V till V. Alla hörn på denna bana är nåbara från , det vill säga de tillhör Z. Varje kant på denna bana faller ihop med två hörn från Z. Som vi såg ovan, för sådana kanter ändras inte skillnaden c(i, j)-y(i)-y(j). Detta innebär att alla kanter av banan kommer att förbli stela och V kommer fortfarande att kunna nås från . Låt oss nu bevisa att minst en vertex läggs till Z. Betrakta kanten på vilken minimum nås . För denna kant kommer skillnaden c(i, j)-y(i)-y(j) att vara noll, därför blir den stel och kommer att riktas från S till T, dvs från i till j. Eftersom , j också blir tillgänglig från , det vill säga att den läggs till Z. $V\in Z$ $R_{S}$ $R_{S}$ $R_{S}$ $\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $i\i Z$ $R_{S}$

Vi upprepar dessa steg tills det blir en perfekt matchning; i detta fall ger det uppdraget med lägst kostnad. Exekveringstiden för den här versionen av algoritmen är : den utfylls en gång, och i det skede när den inte ändras kan det inte finnas fler potentiella förändringar (eftersom den ökar varje gång). Tiden som krävs för att ändra potentialen är . $M\$ $O(n^{4})$ $M\$ $n\$ $M\$ $n\$ $Z\$ $O(n^{2})$

Matristolkning

För arbetare och jobb, givet en n × n matris som anger kostnaden för varje jobb för varje arbetare. Hitta minimikostnaden för att utföra ett jobb så att varje arbetare gör exakt ett jobb och varje jobb utförs av exakt en arbetare. $n$

I det följande förstår vi med uppdrag korrespondensen mellan arbetare och jobb, som har noll kostnad efter att vi har gjort omvandlingar som endast påverkar den totala kostnaden för jobb.

Först av allt, låt oss skriva problemet i matrisform:

{\begin{bmatrix}a1&a2&a3&a4\\b1&b2&b3&b4\\c1&c2&c3&c4\\d1&d2&d3&d4\end{bmatrix))

där a, b, c, d är arbetare som måste utföra jobb 1, 2, 3, 4. Koefficienterna a1, a2, a3, a4 anger kostnaden för att utföra jobb 1, 2, 3, 4 av anställd "a", respektive. Andra symboler har en liknande betydelse. Matrisen är kvadratisk, så varje arbetare kan bara göra ett jobb.

Steg 1

Vi reducerar elementen rad för rad. Vi hittar det minsta av elementen i den första raden (a1, a2, a3, a4) och subtraherar det från alla element i den första raden. I detta fall kommer åtminstone ett av elementen i den första raden att vara noll. Vi gör samma sak för alla andra linjer. Nu har varje rad i matrisen minst en nolla. Ibland räcker det redan med nollor för att hitta destinationen. Ett exempel visas i tabellen. Röda nollor indikerar tilldelade jobb.

0	a2'	0	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Med ett stort antal nollor, för att hitta destinationen (noll kostnad), kan du använda en algoritm för att hitta maximal matchning av tvådelade grafer, till exempel Hopcroft-Karp-algoritmen . Dessutom, om minst en kolumn inte har några null-element, är tilldelningen inte möjlig.

Steg 2

Ofta finns det ingen uppgift i det första steget, som i följande fall:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Uppgift 1 kan utföras effektivt (till noll kostnad) av både arbetare a och arbetare c, men uppgift 3 kan inte utföras effektivt av någon.

I sådana fall upprepar vi steg 1 för kolumnerna och kontrollerar igen om tilldelningen är möjlig.

Steg 3

I många fall kommer vi att uppnå önskat resultat efter steg 2. Men ibland är det inte fallet, till exempel:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	0	d4'

Om arbetare d gör jobb 2 finns det ingen som gör jobb 3, och vice versa.

I sådana fall följer vi proceduren som beskrivs nedan.

Först, med hjälp av valfri algoritm för att hitta den maximala matchningen i en tvådelad graf, tilldelar vi så många jobb som möjligt till de arbetare som kan utföra dem utan kostnad. Ett exempel visas i tabellen, tilldelade jobb är rödmarkerade.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	0	d4'

Notera alla rader utan tilldelningar (rad 1). Notera alla kolumner med nollor i dessa rader (kolumn 1). Notera alla rader med "röda" nollor i dessa kolumner (rad 3). Vi fortsätter tills nya rader och kolumner inte längre är markerade.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0
0	c2'	c3'	c4'	×
d1'	0	0	d4'

Nu ritar vi linjer genom alla markerade kolumner och omarkerade rader.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0
0	c2'	c3'	c4'	×
d1'	0	0	d4'

Alla dessa åtgärder eftersträvade bara ett mål: att rita minsta antal linjer (vertikala och horisontella) för att täcka alla nollor. Du kan använda vilken annan metod som helst istället för den som beskrivs.

Steg 4

Av de matriselement som inte täcks av linjer (i detta fall är dessa a2', a3', a4', c2', c3', c4'), hitta den minsta. Subtrahera det från alla omarkerade rader och lägg till det i alla skärningspunkter mellan markerade rader och kolumner. Så, till exempel, om det minsta elementet i den listade är a2', får vi

×
0	0	a3'-a2'	a4'-a2'	×
b1'+a2'	b2'	b3'	0
0	c2'-a2'	c3'-a2'	c4'-à2'	×
d1'+a2'	0	0	d4'

Upprepa proceduren (steg 1-4) tills det är möjligt att boka tid.

Bibliografi

R.E. Burkard, M. Dell'Amico, S. Martello: Uppdragsproblem . SIAM, Philadelphia (PA.) 2009. ISBN 978-0-89871-663-4
Harold W. Kuhn, "The Hungarian Method for the assignment problem," Naval Research Logistics Quarterly , 2 :83-97, 1955. Kuhns originalpublikation.
Harold W. Kuhn, "Variants of the Hungarian method for assignment problems," Naval Research Logistics Quarterly , 3 : 253-258, 1956.
J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics , 5 (1):32-38, 1957 mars.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Italien, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993.

Anteckningar

↑ Jacobi C. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, CGJ Jacobi's gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (ej tillgänglig länk) politechnique.fr Arkiverad 29 januari 2020 på Wayback Machine
↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 11 februari 2010. Arkiverad från originalet 19 juli 2011. (obestämd)