Ungarsk algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 4. marts 2020; checks kræver 6 redigeringer .

Den ungarske algoritme er en optimeringsalgoritme , der løser opgaveproblemet i polynomisk tid (se operations research ). Den blev udviklet og udgivet af Harold Kuhn i 1955 . Forfatteren gav den navnet "Ungarsk metode" på grund af det faktum, at algoritmen i vid udstrækning er baseret på det tidligere arbejde fra to ungarske matematikere König og Egerváry

James Mancres observerede i 1957, at algoritmen er (strengt) polynomium. Siden dengang har algoritmen også været kendt som Kuhn-Mankres- algoritmen eller Mankres-algoritmen til løsning af opgaveproblemet . Tidskompleksiteten af den oprindelige algoritme var, men Edmonds Karp såvel viste, at den kunne modificeres for at opnå en køretid på. Den modificerede ungarske algoritme kaldes Hopcroft-Karp-algoritmen. Ford og Fulkerson udvidede metoden til generelle transportproblemer. I 2006 blev det opdaget, at Jacobi havde fundet en løsning fra det 19. århundrede på opgaveproblemet, som blev udgivet på latin i en posthum 1890-samling af papirer. [1] [2] $O(n^{4})$ $O(n^{3})$

Eksempel

Antag, at der er tre ansatte: Ivan, Peter og Andrey. Det er nødvendigt at fordele udførelsen af tre typer arbejde mellem dem (som vi vil kalde A, B, C), hver arbejder skal kun udføre en type arbejde. Hvordan gør man det på en sådan måde, at man bruger det mindste beløb på arbejdernes løn? Først skal du opbygge en omkostningsmatrix .

	EN	B	C
Ivan	10.000 gnid.	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 ungarske algoritme anvendt på ovenstående tabel vil give os den nødvendige fordeling: Ivan udfører job A, Peter udfører job B, Andrey udfører job C.

Udtalelse af problemet

Givet en ikke-negativ n × n matrix , hvor elementet i den i -te række og den j -te kolonne svarer til omkostningerne ved at udføre den j -te type arbejde af den i -te arbejder. Det er nødvendigt at finde en sådan korrespondance af arbejde til medarbejdere, så lønomkostningerne er lavest. Hvis målet er at finde destinationen med den højeste omkostning, så reduceres løsningen til at løse det netop formulerede problem ved at erstatte hver omkostning C med forskellen mellem den maksimale omkostning og C . [3]

Hovedideer

Algoritmen er baseret på to ideer:

hvis det samme tal trækkes fra alle elementer i en bestemt række eller kolonne , vil de samlede omkostninger falde med , og den optimale løsning ændres ikke; $y$ $y$
hvis der er en nul-omkostningsløsning, så er den optimal.

Algoritmen søger efter værdier, der skal trækkes fra alle elementer i hver række og hver kolonne (forskellige for forskellige rækker og kolonner), således at alle elementer i matrixen forbliver ikke-negative, men en nulløsning vises.

Definitioner

Algoritmen er lettere at beskrive, hvis problemet er formuleret ved hjælp af en todelt graf . Givet en komplet todelt graf G=(S, T; E) med n toppunkter svarende til medarbejdere ( S ) og n toppunkter svarende til arbejdstyper ( T ); prisen på hver kant c(i, j) er ikke-negativ. Det er påkrævet at finde en perfekt eller komplet matching med de mindste omkostninger.

Vi vil kalde funktionen potentiale hvis for hver . Den potentielle værdi er defineret som . Det er let at se, at prisen for enhver perfekt matchning ikke er mindre end værdien af ethvert potentiale. Den ungarske metode finder en fuld matchning og et potentiale med samme omkostning/værdi, hvilket beviser, at begge mængder er optimale. Faktisk finder han et perfekt match af stive kanter: en kant siges at være stiv for potentialet, hvis . Den stive kant undergraf vil blive betegnet som . Prisen for en komplet matchning i (hvis den findes) er lig 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)$ $ij$ $y$ $y(i)+y(j)=c(i,j)$ ${\mathbf {G_{y))}$ ${\mathbf {G_{y))}$ $y$

Algoritme i form af todelte grafer

Algoritmen gemmer i hukommelsen potentialet og orienteringen (indstilling af retningen) af hver stiv kant, som har den egenskab, at kanterne ledes fra for at danne en matchning, som vi betegner med . En rettet graf bestående af stive kanter med en given orientering er angivet med . Således er der til enhver tid tre typer kanter: $y\$ $T\$ $S\$ $M$ $\mathbf {{\overrightarrow {G}}_{y}}$

ikke-stiv (og hører ikke til ) $M\$
hård, men ikke tilhørende $M\$
hårdt og ejet $M\$

Til at begynde med er overalt 0, og alle kanter er rettet fra til (altså tomme). Ved hvert trin modificeres enten, så sættet af hjørner , defineret i næste afsnit, øges, eller orienteringen ændres for at opnå en matchning med et større antal kanter; det forbliver altid sandt, at alle kanter af er stive. Processen afsluttes, hvis er en perfekt matchning. $y\$ $S\$ $T\$ $M\$ $y\$ $Z\$ $M\$ $M\$

Lad ved hvert trin og være det sæt af knudepunkter, der ikke falder ind i kanter fra (det vil sige , det sæt af spidser fra , som ikke omfatter nogen kant, men det sæt af spidser fra , hvorfra ingen kant kommer ud). Angiv med det sæt af hjørner, der kan nås fra til (det kan findes ved bredde-først søgning ). $R_{S}\subseteq S$ $R_{T}\subseteq T$ $M\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Hvis ikke er tom, betyder det, at der er mindst én vej til fra til . Vi vælger en af disse stier og ændrer orienteringen af alle dens kanter til det modsatte. Størrelsen på matchningen vil øges med 1. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

Som bevis bemærker vi to indlysende fakta:

På den valgte sti veksler kanter fra til med kanter fra til . Dette følger af todelt graf. $S\$ $T\$ $T\$ $S\$
Det første toppunkt på stien tilhører , og det sidste toppunkt tilhører . Derfor er dens første og sidste kanter rettet fra til . $S\$ $T\$ $S\$ $T\$

Per definition følger det, at på den valgte vej veksler de kanter, der hører til og ikke tilhører, og den første og sidste kant hører ikke til , det vil sige, at stien hæver sig, hvorfra den påstand, der bevises, følger. $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$ $M\$

Hvis tom, læg . er positiv, fordi der ikke er nogen hårde kanter mellem og . $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$

Lad faktisk en sådan kant (i, j) eksistere. Siden , men , toppunktet er tilgængeligt fra til , men toppunktet er ikke tilgængeligt. $i\i Z$ $j\notin Z$ $jeg\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Kan derfor ikke indeholde kanter (i, j). Derfor , hvorfra . Da det er tilgængeligt fra til , er der en sti til fra et eller andet toppunkt tilhørende . Overvej den sidste kant af denne vej. Betegn det (k, i). Da den er tilgængelig fra til , men ikke tilgængelig, . Siden ,. _ Derfor er indfaldende til to kanter fra : og , hvilket er umuligt, da er en matchning. Modsigelse. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\i M$ $i\notin R_{S}$ $jeg\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $jeg\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neq j$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\i M$ $jeg\$ $M\$ $(i,j)\$ $(i,k)\$ $M\$

Lad os øge med på toppunkterne fra og mindske med på toppunkterne inkluderet i . Den nye forbliver potentiel. $y\$ $\Delta$ $Z\cap S$ $y\$ $\Delta$ $Z\cap T$ $y\$

Faktisk for enhver kant (i, j), , : $i\i S$ $j\in T$

hvis , , så ændres c(i, j)-y(i)-y(j) ikke, fordi hverken y(i) eller y(j) $i\notin Z$ $j\notin Z$
hvis , , så ændres c(i, j)-y(i)-y(j) ikke, fordi y(i) stiger med , og y(j) falder med samme mængde $i\i Z$ $j\in Z$ $\Delta$
hvis , , stiger forskellen c(i, j)-y(i)-y(j) med , forbliver derfor ikke-negativ $i\notin Z$ $j\in Z$ $\Delta$
hvis , , forskellen c(i, j)-y(i)-y(j) falder med , men forbliver stadig ikke-negativ, fordi er den mindste af sådanne forskelle. $i\i Z$ $j\notin Z$ $\Delta$ $\Delta$

Grafen ændres, men indeholder på trods af dette . $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$

Faktisk, for at udelukke fra en eller anden kant (i, j), , , er det nødvendigt at gøre det ikke-stivt, det vil sige at øge forskellen c(i, j)-y(i)-y(j) . Som vi har set, stiger forskellen kun, hvis , med andre ord, er uopnåelig fra , men er opnåelig. Men i dette tilfælde kan kanten (j, i) ikke tilhøre , derfor hører kanten ikke til . $\mathbf {{\overrightarrow {G}}_{y}}$ $i\i S$ $j\in T$ $i\notin Z$ $j\in Z$ $jeg$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $M$

Orienter de nye kanter fra til . Per definition vil det sæt af hjørner, der kan nås fra , stige (og antallet af stive kanter øges ikke nødvendigvis). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

For at bevise dette udsagn, beviser vi først, at ingen toppunkt forsvinder fra Z. Lad . Så er der en sti fra et eller andet toppunkt, der tilhører V til V. Alle toppunkter på denne sti kan nås fra , det vil sige, at de tilhører Z. Hver kant på denne sti falder sammen med to toppunkter fra Z. Som vi så ovenfor, for sådanne kanter ændres forskellen c(i, j )-y(i)-y(j) ikke. Det betyder, at alle kanter af stien forbliver stive, og V vil stadig være tilgængelig fra . Lad os nu bevise, at mindst et toppunkt er tilføjet Z. Overvej den kant, hvor minimum er nået . For denne kant vil forskellen c(i, j)-y(i)-y(j) være nul, derfor vil den blive stiv og vil blive rettet fra S til T, dvs. fra i til j. Da , j også bliver tilgængelig fra , det vil sige, at den føjes til 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 gentager disse trin, indtil det bliver et perfekt match; i dette tilfælde giver det opgaven med den laveste omkostning. Udførelsestiden for denne version af algoritmen er : den polstres én gang, og i den fase, hvor den ikke ændrer sig, kan der ikke være flere potentielle ændringer (da den øges hver gang). Den tid det tager at ændre potentialet er . $M\$ $O(n^{4})$ $M\$ $n\$ $M\$ $n\$ $Z\$ $O(n^{2})$

Matrix fortolkning

For arbejdere og job, givet en n × n matrix , der specificerer omkostningerne ved hvert job for hver arbejder. Find minimumsomkostningerne ved at udføre et job, således at hver arbejder udfører præcis ét job, og hvert job udføres af præcis én arbejder. $n$

I det følgende forstår vi ved tildeling korrespondancen mellem arbejdere og job, som har nul omkostninger, efter at vi har foretaget transformationer, der kun påvirker de samlede omkostninger ved job.

Først og fremmest, lad os skrive problemet i matrixform:

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

hvor a, b, c, d er arbejdere, der skal udføre job 1, 2, 3, 4. Koefficienterne a1, a2, a3, a4 angiver omkostningerne ved at udføre job 1, 2, 3, 4 af medarbejder "a", henholdsvis. Andre symboler har en lignende betydning. Matrixen er kvadratisk, så hver medarbejder kan kun udføre ét job.

Trin 1

Vi reducerer elementerne linje for linje. Vi finder det mindste af elementerne i den første række (a1, a2, a3, a4), og trækker det fra alle elementerne i den første række. I dette tilfælde vil mindst et af elementerne i den første række blive sat til nul. Vi gør det samme for alle andre linjer. Nu har hver række i matrixen mindst ét nul. Nogle gange er nuller allerede nok til at finde destinationen. Et eksempel er vist i tabellen. Røde nuller angiver tildelte job.

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

Med et stort antal nuller, for at finde destinationen (nul omkostninger), kan du bruge en algoritme til at finde den maksimale matchning af todelte grafer, for eksempel Hopcroft-Karp-algoritmen . Desuden, hvis mindst én kolonne ikke har nul-elementer, er tildelingen ikke mulig.

Trin 2

Ofte er der ingen opgave i det første trin, som i følgende tilfælde:

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

Opgave 1 kan udføres effektivt (uden omkostninger) af både arbejder a og arbejder c, men opgave 3 kan ikke udføres effektivt af nogen.

I sådanne tilfælde gentager vi trin 1 for kolonnerne og tjekker igen, om tildelingen er mulig.

Trin 3

I mange tilfælde vil vi opnå det ønskede resultat efter trin 2. Men nogle gange er det ikke tilfældet, f.eks.

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

Hvis arbejder d udfører job 2, er der ingen til at udføre job 3, og omvendt.

I sådanne tilfælde følger vi proceduren beskrevet nedenfor.

For det første, ved at bruge en hvilken som helst algoritme til at finde den maksimale matchning i en todelt graf, tildeler vi så mange job som muligt til de arbejdere, der kan udføre dem uden omkostninger. Et eksempel er vist i tabellen, tildelte job er fremhævet med rødt.

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

Bemærk alle linjer uden tildelinger (linje 1). Bemærk alle kolonner med nul i disse rækker (kolonne 1). Bemærk alle rækker med "røde" nuller i disse kolonner (linje 3). Vi fortsætter, indtil nye rækker og kolonner ikke længere er markeret.

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

Nu tegner vi linjer gennem alle de markerede kolonner og umarkerede rækker.

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

Alle disse handlinger forfulgte kun ét mål: at tegne det mindste antal linjer (lodrette og vandrette) for at dække alle nuller. Du kan bruge en hvilken som helst anden metode i stedet for den beskrevne.

Trin 4

Af de matrixelementer, der ikke er dækket af linjer (i dette tilfælde er disse a2', a3', a4', c2', c3', c4'), find den mindste. Træk det fra alle umarkerede rækker og føj det til alle skæringspunkter mellem markerede rækker og kolonner. Så for eksempel, hvis det mindste element i den listede er 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'

Gentag proceduren (trin 1-4), indtil aftalen er mulig.

Bibliografi

R.E. Burkard, M. Dell'Amico, S. Martello: Opgaveproblemer . 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 originale publikation.
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 marts.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Italien, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993.

Noter

↑ Jacobi C. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, CGJ Jacobi's gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (utilgængeligt link) politechnique.fr Arkiveret 29. januar 2020 på Wayback Machine
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 11. februar 2010. Arkiveret fra originalen 19. juli 2011. (ubestemt)