Maďarský algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. března 2020; kontroly vyžadují 6 úprav .

Maďarský algoritmus je optimalizační algoritmus , který řeší problém zadání v polynomiálním čase (viz operační výzkum ). Byl vyvinut a publikován Haroldem Kuhnem v roce 1955 . Autor jí dal název "Maďarská metoda" kvůli skutečnosti, že algoritmus je z velké části založen na dřívější práci dvou maďarských matematiků König a Egerváry

James Mancres v roce 1957 poznamenal, že algoritmus je (přísně) polynomiální. Od té doby je algoritmus známý také jako Kuhn-Mankresův algoritmus nebo Mankresův algoritmus pro řešení zadávacího problému . Časová složitost původního algoritmu byla, ale Edmonds Karp stejně ukázali, že jej lze upravit tak, aby bylo dosaženo provozní doby. Upravený maďarský algoritmus se nazývá Hopcroft-Karpův algoritmus. Ford a Fulkerson rozšířili metodu na obecné dopravní problémy. V roce 2006 bylo zjištěno, že Jacobi našel řešení problému zadání z 19. století, které bylo publikováno v latině v posmrtném sborníku z roku 1890. [1] [2] $O(n^{4})$ $O(n^{3})$

Příklad

Předpokládejme, že existují tři zaměstnanci: Ivan, Peter a Andrey. Mezi ně je nutné rozdělit výkon tří druhů prací (které budeme nazývat A, B, C), každý pracovník musí vykonávat pouze jeden druh práce. Jak to udělat tak, aby se na mzdy dělníků utratilo co nejméně peněz? Nejprve musíte vytvořit matici nákladů .

	A	B	C
Ivane	10 000 rublů.	20 000 rublů.	30 000 rublů.
Petr	30 000 rublů.	30 000 rublů.	30 000 rublů.
Andrew	30 000 rublů.	30 000 rublů.	20 000 rublů.

Maďarský algoritmus aplikovaný na výše uvedenou tabulku nám poskytne požadované rozdělení: Ivan dělá práci A, Peter dělá práci B, Andrey dělá práci C.

Prohlášení o problému

Je dána nezáporná matice n × n , kde prvek v i -té řadě a j -tém sloupci odpovídá nákladům na provedení j -tého typu práce i -tým pracovníkem. Je třeba najít takovou shodu práce se zaměstnanci, aby náklady práce byly co nejnižší. Pokud je cílem najít místo určení s nejvyššími náklady, pak se řešení redukuje na vyřešení právě formulovaného problému nahrazením každého nákladu C rozdílem mezi maximálními náklady a C . [3]

Hlavní myšlenky

Algoritmus je založen na dvou myšlenkách:

pokud je stejné číslo odečteno od všech prvků určitého řádku nebo sloupce , celkové náklady se sníží o a optimální řešení se nezmění; $y$ $y$
pokud existuje řešení s nulovými náklady, pak je optimální.

Algoritmus hledá hodnoty, které mají být odečteny od všech prvků každého řádku a každého sloupce (různé pro různé řádky a sloupce), takže všechny prvky matice zůstanou nezáporné, ale objeví se nulové řešení.

Definice

Algoritmus se snadněji popisuje, pokud je problém formulován pomocí bipartitního grafu . Je dán úplný bipartitní graf G=(S, T; E) s n vrcholy odpovídajícími zaměstnancům ( S ) a n vrcholy odpovídajícími typům práce ( T ); cena každé hrany c(i, j) je nezáporná. Je nutné najít dokonalé nebo úplné sladění s co nejnižšími náklady.

Funkční potenciál budeme nazývat if pro každý . Potenciální hodnota je definována jako . Je snadné vidět, že náklady na dokonalé sladění nejsou menší než hodnota jakéhokoli potenciálu. Maďarská metoda najde plnou shodu a potenciál se stejnou cenou/hodnotou, což dokazuje, že obě veličiny jsou optimální. Ve skutečnosti nalezne dokonalé sladění tuhých hran: o hraně se říká, že je tuhá pro potenciální if . Podgraf s pevnou hranou bude označen jako . Cena úplného párování v (pokud existuje) se rovná . $y\colon (S\cup T)\to \mathbb {R}$ $y(i)+y(j)\leq c(i,j)$ $i\v S,j\v 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$

Algoritmus z hlediska bipartitních grafů

Algoritmus ukládá do paměti potenciál a orientaci (nastavení směru) každé tuhé hrany, která má tu vlastnost, že hrany směřují , aby vytvořily shodu, kterou označujeme . Orientovaný graf skládající se z pevných hran s danou orientací se značí . V každém okamžiku tedy existují tři typy hran: $y\$ $T\$ $S\$ $M$ $\mathbf {{\overrightarrow {G}}_{y}}$

netuhý (a nepatřící ) $M\$
tvrdý, ale nepatřící $M\$
tvrdé a vlastněné $M\$

Zpočátku je všude 0 a všechny hrany směřují od do (tedy prázdné). V každém kroku se buď upraví tak, že se zvětší množina vrcholů definovaná v dalším odstavci, nebo se změní orientace, aby se dosáhlo shody s větším počtem hran; vždy platí, že všechny hrany jsou tuhé. Proces končí, pokud je dokonalé spárování. $y\$ $S\$ $T\$ $M\$ $y\$ $Z\$ $M\$ $M\$

Nechť na každém kroku a je množina vrcholů, které nejsou incidentní s hranami z (tedy množina vrcholů z , které neobsahují žádnou hranu, ale množinu vrcholů z , ze kterých žádná hrana nevychází). Označte množinou vrcholů dosažitelných od do (lze najít vyhledáváním do šířky ). $R_{S}\subseteq S$ $R_{T}\subseteq T$ $M\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Pokud není prázdné, znamená to, že existuje alespoň jedna cesta k od do . Zvolíme kteroukoli z těchto cest a změníme orientaci všech jejích hran na opačnou. Velikost shody se zvýší o 1. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

Pro důkaz uvádíme dvě zřejmé skutečnosti:

Na zvolené cestě se hrany od do střídají s hranami od do . Vyplývá to z bipartitního grafu. $S\$ $T\$ $T\$ $S\$
První vrchol cesty patří do a poslední vrchol patří do . Jeho první a poslední hrana je tedy směrována z do . $S\$ $T\$ $S\$ $T\$

Z definice vyplývá, že na zvolené cestě se střídají hrany patřící a nepatřící a první a poslední hrana nepatří do , tedy dráha stoupá, z čehož vyplývá dokazované tvrzení. $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$ $M\$

Pokud je prázdný, vložte . je pozitivní, protože mezi a nejsou žádné ostré hrany . $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$

Nechť taková hrana (i, j) skutečně existuje. Od , ale , vrchol je dosažitelný od do , ale vrchol je nedosažitelný. $i\in Z$ $j\notin Z$ $já\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Nemůže tedy obsahovat hrany (i, j) . Proto , odkud . Protože je dosažitelná z do , existuje cesta do z nějakého vrcholu patřícího do . Zvažte poslední okraj této cesty. Označte to (k, i). Protože je dosažitelná od do , ale nedosažitelná . Od , . Proto je incident se dvěma hranami od : a , což je nemožné, protože jde o shodu. Rozpor. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\v M$ $i\notin R_{S}$ $já\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $já\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neq j$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\v M$ $já\$ $M\$ $(i,j)\$ $(i,k)\$ $M\$

Zvyšme o na vrcholech od a snižme o u vrcholů zahrnutých v . Ten nový zůstává potenciálem. $y\$ $\Delta$ $Z\cap S$ $y\$ $\Delta$ $Z\cap T$ $y\$

Opravdu, pro jakoukoli hranu (i, j), , : $i\v S$ $j\in T$

jestliže , , pak se c(i, j)-y(i)-y(j) nezmění, protože ani y(i) ani y(j) $i\notin Z$ $j\notin Z$
jestliže , , pak se c(i, j)-y(i)-y(j) nezmění, protože y(i) se zvětší o , a y(j) se o stejnou hodnotu sníží $i\in Z$ $j\in Z$ $\Delta$
jestliže , , rozdíl c(i, j)-y(i)-y(j) vzroste o , proto zůstává nezáporný $i\notin Z$ $j\in Z$ $\Delta$
jestliže , , rozdíl c(i, j)-y(i)-y(j) se sníží o , ale stále zůstává nezáporný, protože je nejmenší z těchto rozdílů. $i\in Z$ $j\notin Z$ $\Delta$ $\Delta$

Graf se mění, ale přesto obsahuje . $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$

Ve skutečnosti, abychom z nějaké hrany (i, j), , , vyloučili, je nutné ji učinit nerigidní, tedy zvýšit rozdíl c(i, j)-y(i)-y(j) . Jak jsme viděli, rozdíl se zvyšuje pouze tehdy , je-li , , jinými slovy, nedosažitelné z , ale je dosažitelné. Ale v tomto případě hrana (j, i) nemůže patřit do , proto hrana nepatří do . $\mathbf {{\overrightarrow {G}}_{y}}$ $i\v S$ $j\in T$ $i\notin Z$ $j\in Z$ $i$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $M$

Orientujte nové okraje od do . Podle definice se množina vrcholů dosažitelných z zvýší (a počet pevných hran se nezbytně nezvýší). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

Abychom toto tvrzení dokázali, nejprve dokážeme, že ze Z nezmizí žádný vrchol. Let . Pak existuje cesta z nějakého vrcholu, který patří k V do V. Všechny vrcholy na této cestě jsou dosažitelné z , to znamená, že patří do Z. Každá hrana na této cestě je incidentní ke dvěma vrcholům od Z. Jak jsme viděli výše, pro takové hrany se rozdíl c(i, j )-y(i)-y(j) nemění. To znamená, že všechny hrany cesty zůstanou tuhé a V bude stále dosažitelné z . Nyní dokažme, že k Z je přidán alespoň jeden vrchol. Uvažujme hranu, na které je dosaženo minima . Pro tuto hranu bude rozdíl c(i, j)-y(i)-y(j) nulový, proto ztuhne a bude směřovat z S do T, tj. z i do j. Protože , j bude také dosažitelné z , to znamená, že bude přidáno k 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\in Z$ $R_{S}$

Opakujeme tyto kroky, dokud se nestane dokonalou shodou; v tomto případě dává zadání s nejnižšími náklady. Doba provádění této verze algoritmu je : je jednou vyplněna a ve fázi, kdy se nemění, již nemůže dojít k žádným dalším potenciálním změnám (protože se pokaždé zvyšuje). Čas potřebný ke změně potenciálu je . $M\$ $O(n^{4})$ $M\$ $n\$ $M\$ $n\$ $Z\$ $O(n^{2})$

Maticový výklad

Pro pracovníky a pracovní místa je dána matice n × n , která specifikuje náklady na každou práci pro každého pracovníka. Najděte minimální náklady na provedení práce tak, aby každý pracovník dělal přesně jednu práci a každou práci dělal přesně jeden pracovník. $n$

V následujícím textu rozumíme zadáním korespondenci mezi pracovníky a pracovními místy, která má nulové náklady poté, co jsme provedli transformace, které ovlivňují pouze celkové náklady na pracovní místa.

Nejprve napišme problém v maticové formě:

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

kde a, b, c, d jsou pracovníci, kteří musí vykonávat zaměstnání 1, 2, 3, 4. Koeficienty a1, a2, a3, a4 označují náklady na výkon zaměstnání 1, 2, 3, 4 zaměstnancem „a“, respektive. Ostatní symboly mají podobný význam. Matice je čtvercová, takže každý pracovník může dělat pouze jednu práci.

Krok 1

Prvky zmenšujeme řádek po řádku. Najdeme nejmenší z prvků prvního řádku (a1, a2, a3, a4) a odečteme jej od všech prvků prvního řádku. V tomto případě bude alespoň jeden z prvků prvního řádku nastaven na nulu. Totéž uděláme pro všechny ostatní řádky. Nyní má každý řádek matice alespoň jednu nulu. Někdy už k nalezení cíle stačí nuly. Příklad je uveden v tabulce. Červené nuly označují přiřazené úlohy.

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

S velkým počtem nul můžete pro nalezení cíle (nulové náklady) použít algoritmus pro nalezení maximální shody bipartitních grafů, například Hopcroft-Karpův algoritmus . Také pokud alespoň jeden sloupec nemá žádné prvky null, pak přiřazení není možné.

Krok 2

Často v prvním kroku není žádné přiřazení, jako v následujícím případě:

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

Úkol 1 může efektivně (s nulovými náklady) provést pracovník a i pracovník c, ale úkol 3 nemůže efektivně provést nikdo.

V takových případech opakujeme krok 1 pro sloupce a znovu zkontrolujeme, zda je přiřazení možné.

Krok 3

V mnoha případech dosáhneme požadovaného výsledku po kroku 2. Ale někdy tomu tak není, například:

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

Pokud pracovník d dělá práci 2, nemá kdo dělat práci 3 a naopak.

V takových případech postupujeme podle níže uvedeného postupu.

Za prvé, pomocí libovolného algoritmu pro nalezení maximální shody v bipartitním grafu přidělíme co nejvíce pracovních míst těm pracovníkům, kteří je mohou vykonávat s nulovými náklady. Příklad je uveden v tabulce, přiřazené úlohy jsou zvýrazněny červeně.

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

Poznamenejte si všechny řádky bez přiřazení (řádek 1). Poznamenejte si všechny sloupce s nulami v těchto řádcích (sloupec 1). Poznamenejte si všechny řádky s "červenými" nulami v těchto sloupcích (řádek 3). Pokračujeme, dokud nové řádky a sloupce přestanou být označeny.

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

Nyní vedeme čáry přes všechny označené sloupce a neoznačené řádky.

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

Všechny tyto akce sledovaly jediný cíl: nakreslit co nejmenší počet čar (vertikálních a horizontálních), aby byly pokryty všechny nuly. Místo popsané metody můžete použít jakoukoli jinou.

Krok 4

Z prvků matice, které nejsou pokryty čarami (v tomto případě jsou to a2', a3', a4', c2', c3', c4'), najděte nejmenší. Odečtěte jej od všech neoznačených řádků a přidejte ke všem průsečíkům označených řádků a sloupců. Pokud je tedy například nejmenší prvek ze seznamu a2', dostaneme

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

Opakujte postup (kroky 1-4), dokud nebude schůzka možná.

Bibliografie

R. E. Burkard, M. Dell'Amico, S. Martello: Problémy s přiřazením . SIAM, Philadelphia (PA.) 2009. ISBN 978-0-89871-663-4
Harold W. Kuhn, "The Hungarian Method for the Association Problem," Naval Research Logistics Quarterly , 2 :83-97, 1955. Kuhnova původní publikace.
Harold W. Kuhn, „Varianty maďarské metody pro problémy s přiřazením“, 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, březen 1957.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Itálie, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993.

Poznámky

↑ Jacobi C. De investigando ordine systematis aequationum Differentum vulgarium cujuscunque, CGJ Jacobiho gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (nedostupný odkaz) politechnique.fr Archivováno 29. ledna 2020 na Wayback Machine
↑ Archivovaná kopie (odkaz není dostupný) . Získáno 11. února 2010. Archivováno z originálu 19. července 2011. (neurčitý)