algorytm węgierski

Metoda węgierska to kombinatoryczny algorytm optymalizacyjny , który rozwiązuje problem przypisania w czasie wielomianowym i który przewidywał późniejsze metody pierwotne i dualne . Został opracowany i opublikowany w 1955 roku przez Harolda Kuhna , który nadał mu nazwę „metoda węgierska”, ponieważ algorytm był w dużej mierze oparty na wcześniejszych pracach dwóch węgierskich matematyków: Dénesa Kőniga i Jenő Egerváry'ego .

James Munkres dokonał przeglądu algorytmu w 1957 roku i zauważył, że jest on (silnie) wielomianowy . Od tego czasu algorytm znany jest również jako algorytm Kuhna-Munkresa lub algorytm przypisania Munkresa . Złożoność czasowa oryginalnego algorytmu $,$ jednak Edmonds i Karp oraz można go zmodyfikować, aby osiągnąć ${\ displaystyle O (n ^ {3})}$ czas pracy. ^{[ jak? ]} Jednym z najpopularniejszych $]$ ^{[ potrzebne źródło jest} algorytm Ford i Fulkerson rozszerzyli tę metodę na ogólne problemy maksymalnego przepływu w postaci algorytmu Forda-Fulkersona . W 2006 roku odkryto, że Carl Gustav Jacobi rozwiązał problem przypisania w XIX wieku, a rozwiązanie zostało opublikowane pośmiertnie w 1890 roku po łacinie.

Problem

Przykład

W tym prostym przykładzie jest trzech pracowników: Paul, Dave i Chris. Jeden z nich musi sprzątać łazienkę, inny zamiatać podłogi, a trzeci myć okna, ale każdy żąda innego wynagrodzenia za różne zadania. Problem polega na znalezieniu najtańszego sposobu przydziału zadań. Problem można przedstawić w postaci macierzy kosztów pracowników wykonujących pracę. Na przykład:

	Czysta łazienka	Zamiataj podłogi	Umyj okna
Paweł	2 dolary	3 dolary	3 dolary
Dave'a	3 dolary	2 dolary	3 dolary
Chris	3 dolary	3 dolary	2 dolary

Metoda węgierska zastosowana do powyższej tabeli dałaby minimalny koszt: to 6 dolarów, osiągnięty dzięki temu, że Paul posprzątał łazienkę, Dave zamiatał podłogi, a Chris umył okna.

Formuła matrycy

W sformułowaniu macierzowym otrzymujemy nieujemną macierz n × n , gdzie element w i -tym wierszu i j -tej kolumnie reprezentuje koszt przydzielenia j -tej pracy i -temu pracownikowi. Musimy znaleźć przydział zadań do pracowników, tak aby każde zadanie było przypisane do jednego pracownika i każdemu pracownikowi przydzielono jedno zadanie, tak aby całkowity koszt przydziału był minimalny.

Można to wyrazić jako permutację wierszy macierzy kosztów C w celu zminimalizowania śladu macierzy,

{\ Displaystyle \ min _ {P} \ operatorname {Tr} (PC) \;,}

gdzie P jest macierzą permutacji . (Równoważnie kolumny można permutować za pomocą CP .)

Jeśli celem jest znalezienie przypisania, które daje maksymalny koszt, problem można rozwiązać, negując macierz kosztów C .

Sformułowanie wykresu dwudzielnego

Algorytm można równoważnie opisać, formułując problem za pomocą wykresu dwudzielnego. Mamy $wykres$ dwudzielny z $n$ $wierzchołkami$ roboczymi ( ) i ( $T$ $nieujemny$ koszt ${\ Displaystyle c (i, j)}$ . Chcemy znaleźć idealne dopasowanie przy minimalnym koszcie całkowitym.

Algorytm w ujęciu grafów dwudzielnych

Nazwijmy funkcję $}$ ${\ Displaystyle y (i) + y (j) \ równoważnik c (i, j)}$ potencjał , jeśli ) dla każdego ${\ Displaystyle i \ w S, j \ w T}$ . The wartość potencjału $y$ jest sumą potencjału we wszystkich wierzchołkach: ${\ Displaystyle \ suma _ {v \ w S \ kubek T} y (v)}$ .

Koszt każdego idealnego dopasowania to co najmniej wartość każdego potencjału: całkowity koszt dopasowania to suma kosztów wszystkich krawędzi; koszt każdej krawędzi jest co najmniej sumą potencjałów jej punktów końcowych; ponieważ dopasowanie jest idealne, każdy wierzchołek jest punktem końcowym dokładnie jednej krawędzi; stąd całkowity koszt jest co najmniej całkowitym potencjałem.

Metoda węgierska znajduje idealne dopasowanie i potencjał taki, że koszt dopasowania jest równy potencjalnej wartości. To dowodzi, że oba są optymalne. $węgierska$ znajduje idealne dopasowanie ciasnych krawędzi : krawędź ${\ displaystyle y(i)+y(j)=c(i,j)}$ ciasną dla potencjału $y$ , jeśli . Oznaczmy podwykres ciasnych krawędzi przez ${\ displaystyle G_ {y}}$ . Koszt idealnego dopasowania w $istnieje)$ jest równy wartości $y$ .

$),$ algorytmu utrzymujemy potencjał y $i$ orientację ( $oznaczoną$ przez krawędzie zorientowane od $T$ do $S$ tworzą pasujące $M$ . Początkowo $y$ wszędzie wynosi 0, a wszystkie krawędzie są zorientowane od $S$ do $T$ (więc $M$ jest puste). W każdym kroku modyfikujemy $y$ aby jego wartość wzrosła, lub zmodyfikuj orientację, aby uzyskać dopasowanie z większą liczbą krawędzi. Utrzymujemy niezmiennik, że wszystkie krawędzie $M$ są ciasne. Skończyliśmy, jeśli $M$ jest idealnym dopasowaniem.

W ogólnym kroku niech ${\ Displaystyle R_ {S} \ subseteq S}$ i ${\ Displaystyle R_ {T} \ subseteq T}$ będą wierzchołkami nieobjętymi przez $M$ (więc $R_ {S}} składa$ ${\$ $się$ z wierzchołków w $S$ bez krawędzi przychodzącej i składa z wierzchołków w $T$ bez krawędzi wychodzącej). Niech $Z$ będzie zbiorem wierzchołków osiągalnych w $}}}}$ $y$ od skierowanej ścieżki tylko po ciasnych krawędziach. Można to obliczyć za pomocą przeszukiwania wszerz .

Jeśli ${\ Displaystyle R_ {T} \ cap Z}$ nie jest puste, odwróć orientację skierowanej ścieżki w ${\ displaystyle {\ overrightarrow {G_ {y}}}}$ z ${\ displaystyle R_ {S}}$ do ${\ Displaystyle R_ {T}}$ . W ten sposób rozmiar odpowiedniego dopasowania wzrasta o 1.

Jeśli jest pusty, to niech. ${\ displaystyle R_ {T} \ cap Z}$

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

$Δ jest dobrze zdefiniowane$ $,$ ponieważ co najmniej jedna taka krawędź , gdy dopasowanie nie ma jeszcze maksymalnego możliwego rozmiaru (patrz następna sekcja); $}$ $setminus$ { displaystyle . Zwiększ $y$ o $Δ$ na wierzchołkach ${\ Displaystyle Z \ cap S}$ i zmniejsz $y$ o $Δ$ na wierzchołkach ${\ Displaystyle Z \ cap T}$ . Wynikowy $y$ jest nadal potencjałem i chociaż wykres $się zmienia,$ zawiera $M ($ następne podrozdziały). Orientujemy nowe krawędzie od $S$ do $T$ . Z definicji $Δ$ zbiór $Z$ wierzchołków osiągalnych z ${\ Displaystyle R_ {S}}$ wzrasta (zauważ, że liczba ciasnych krawędzi niekoniecznie wzrasta).

Powtarzamy te kroki, aż $M$ będzie idealnym dopasowaniem, w którym to przypadku daje przypisanie minimalnego kosztu. Czas działania tej wersji metody to $najwyżej$ M $jest$ zwiększane $n$ razy, aw fazie, w której $niezmienione$ istnieje co $potencjalnych$ zmian (ponieważ $Z$ wzrasta za każdym razem). Czas wystarczający na zmianę potencjału to ${\ Displaystyle O (n ^ {2})}$ .

Dowód, że algorytm robi postępy

Musimy pokazać, że tak długo, jak dopasowanie nie osiąga maksymalnego możliwego rozmiaru, algorytm zawsze jest w stanie zrobić postęp — to znaczy albo zwiększyć liczbę dopasowanych krawędzi, albo zawęzić przynajmniej jedną krawędź. Wystarczy pokazać, że na każdym kroku zachodzi co najmniej jedno z poniższych stwierdzeń:

$M$ ma maksymalny możliwy rozmiar.
${\ Displaystyle G_ {y}}$ zawiera ścieżkę rozszerzającą.
$G$ zawiera ścieżkę o luźnym ogonie : ścieżkę od jakiegoś wierzchołka w $Displaystyle$ wierzchołka w $T \ setminus Z} , która składa$ z dowolnej liczby (prawdopodobnie zero) ciasnych krawędzie, po których następuje pojedyncza luźna krawędź. $zdefiniowane$ luźna krawędź luźnej ścieżki pochodzi zatem z , $,$ że .

Jeśli $M$ ma maksymalny możliwy rozmiar, to oczywiście jesteśmy skończeni. W przeciwnym razie, zgodnie z lematem Berge'a , musi istnieć rosnąca ścieżka $P$ w odniesieniu do $M$ w podstawowym grafie $G$ . Jednak ta ścieżka może nie istnieć w : Chociaż każda parzysta krawędź w $P$ $M$ ciasna z definicji $,$ o numerach nieparzystych mogą być luźne, a zatem nieobecne w ${\ styl wyświetlania G_{y}}$ . Jeden punkt końcowy $P$ jest w , drugi w $R_ {T}}$ $displaystyle$ ; wlog, załóżmy, że zaczyna się w ${\ displaystyle R_ {S}}$ . Jeśli każda krawędź na $P$ jest ciasna, to pozostaje ścieżką zwiększającą się w ${\ displaystyle G_ {y}}$ i gotowe. W przeciwnym razie niech $na$ luźną krawędzią $P$ . Jeśli ${\ displaystyle v \ notin Z}$ następnie znaleźliśmy luźną ścieżkę i gotowe. W przeciwnym razie $v$ jest osiągalne z innej ścieżki $Q$ ciasnych krawędzi z wierzchołka w . ${\ displaystyle R_ {S}}$ . Niech będzie ścieżką podrzędną $P$ $się$ od $v$ i trwającą do końca, i niech $P_{v}$ $ścieżką$ przez podróżowanie wzdłuż $Q$ do wierzchołka na zostanie osiągnięty, a następnie $kontynuuje$ . Zauważ $,$ że jest ścieżką zwiększającą się w $G$ co najmniej jedną luźną krawędzią mniej $P$ . $P$ można zastąpić przez i ten proces $rozumowania był iterowany (formalnie przy użyciu$ liczby luźnych krawędzi) aż do ścieżki powiększającej w sol $y}}$ ogoniasta ścieżka w $G$ jest znalezione.

Dowód, że dostosowanie potencjału y pozostawia M niezmienione

Aby pokazać, że każda krawędź w $M$ pozostaje po dostosowaniu $y$ , wystarczy pokazać, że dla dowolnej krawędzi w $M$ , albo oba jej punkty końcowe, albo żaden z nich nie leżą w $Z$ . W tym celu $krawędzią$ będzie $M$ od $T$ do $S$ . Łatwo zauważyć, że jeśli $v$ jest w $Z,$ to $u$ też musi być, ponieważ każda krawędź w $M$ jest ciasna. Załóżmy teraz, ku sprzeczności, że ${\ Displaystyle u \ w Z}$ ale ${\ Displaystyle v \ notin Z}$ . samo $u$ nie może znajdować się w $,$ ponieważ jest to punkt końcowy dopasowanej krawędzi, więc musi istnieć jakaś skierowana ścieżka ciasnych krawędzi od wierzchołka w ${\ displaystyle R_ {S}}$ do R $ty$ . Ta ścieżka musi unikać $v$ , ponieważ z założenia nie jest to w $Z$ , więc wierzchołek bezpośrednio poprzedzający $u$ na tej ścieżce jest jakiś inny wierzchołek ${\ Displaystyle v'\ in T}$ . $v'u}$ displaystyle jest ciasną krawędzią od $T$ do $S$ , a zatem jest w $M.$ Ale wtedy $M$ zawiera dwie krawędzie, które mają wspólny wierzchołek $u$ , co jest sprzeczne z faktem, że $M$ jest dopasowaniem. Zatem każda krawędź w $M$ ma albo oba punkty końcowe, albo żadnego z punktów końcowych w $Z$ .

Dowód, że $y$ pozostaje potencjałem

Aby pokazać, że $y$ pozostaje potencjałem po skorygowaniu, wystarczy pokazać, że żadna krawędź nie ma zwiększonego całkowitego potencjału ponad swój koszt. Zostało to już ustalone dla krawędzi w $M$ w poprzednim akapicie, więc rozważmy dowolną krawędź $uv$ od $S$ do $T$ . y ${\ Displaystyle y (u)}$ jest zwiększany o $Δ$ , to albo ${\ Displaystyle v \ in Z \ cap T}$ w takim przypadku ${\ Displaystyle y (v)}$ zmniejsza się o $Δ$ , pozostawiając całkowity potencjał krawędzi niezmieniony lub ${\ Displaystyle v \ in T \ setminus Z}$ , w takim przypadku definicja $Δ$ gwarantuje, że ${\ Displaystyle y (u) + y (v) + \ Delta \ równoważnik c (u, v)}$ . Zatem $y$ pozostaje potencjałem.

Interpretacja macierzy

Biorąc pod uwagę $n$ pracowników i zadań, problem jest zapisany w postaci macierzy $n$ × $n$

1 _{_}	2 _{_}	3 _{_}	4 _{_}
b1 _{_}	b2 _{_}	b3 _{_}	4 _{_}
c ₁	c ₂	c ₃	do ₄
d ₁	re ₂	re ₃	d ₄

gdzie a, b, c i d to pracownicy, którzy mają wykonać zadania 1, 2, 3 i 4. a ₁ , a ₂ , a ₃ i a ₄ oznaczają kary, jakie nalicza się, gdy pracownik „a” wykona zadanie 1, 2, odpowiednio 3 i 4.

Problem jest równoważny z przypisaniem każdemu pracownikowi unikalnego zadania w taki sposób, aby zminimalizować łączną karę. Pamiętaj, że nad każdym zadaniem może pracować tylko jeden pracownik.

Krok 1

Dla każdego wiersza jego minimalny element jest odejmowany od każdego elementu w tym wierszu. Powoduje to, że wszystkie elementy mają wartości nieujemne. Dlatego przydział z całkowitą karą równą 0 jest z definicji przydziałem minimalnym.

Prowadzi to również do co najmniej jednego zera w każdym rzędzie. W związku z tym naiwny chciwy algorytm może próbować przypisać wszystkim pracownikom zadanie z karą równą zero. Jest to zilustrowane poniżej.

0	2 _{_}	3 _{_}	4 _{_}
b1 _{_}	b2 _{_}	b3 _{_}	0
c ₁	0	c ₃	do ₄
d ₁	re ₂	0	d ₄

Zera powyżej byłyby przypisanymi zadaniami.

W najgorszym przypadku jest $n$ ! kombinacje do wypróbowania, ponieważ wiele zer może pojawić się w rzędzie, jeśli liczba elementów jest minimalna. Więc w pewnym momencie ten naiwny algorytm powinien zostać zwarty.

Krok 2

Czasami może się okazać, że matryca na tym etapie nie nadaje się do przypisania, jak ma to miejsce w przypadku poniższej matrycy.

0	2 _{_}	0	4 _{_}
b1 _{_}	0	b3 _{_}	0
0	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

Aby temu zaradzić, powtarzamy powyższą procedurę dla wszystkich kolumn (tj. minimalny element w każdej kolumnie jest odejmowany od wszystkich elementów w tej kolumnie ), a następnie sprawdzamy, czy możliwe jest przypisanie z karą 0.

W większości sytuacji da to wynik, ale jeśli nadal nie jest to możliwe, musimy iść dalej.

Krok 3

Wszystkie zera w macierzy muszą być zakryte przez zaznaczenie jak najmniejszej liczby wierszy i/lub kolumn. Kroki 3 i 4 stanowią jeden ze sposobów osiągnięcia tego celu.

Dla każdego wiersza spróbuj przypisać dowolne zero. Przypisane zadania są reprezentowane przez zero. Pamiętaj, że przypisania nie mogą znajdować się w tym samym wierszu ani w tej samej kolumnie.

Przypisujemy pierwsze zero wiersza 1. Drugie zero wiersza 1 nie może być przypisane.
Przypisujemy pierwsze zero w wierszu 2. Drugie zero w wierszu 2 nie może być przypisane.
Nie można przypisać zer w wierszu 3 i 4, ponieważ znajdują się one w tej samej kolumnie, co zero przypisane w wierszu 1.

Moglibyśmy zakończyć innym zadaniem, jeśli wybierzemy inną kolejność wierszy i kolumn.

0*	2 _{_}	0	4 _{_}
b1 _{_}	0*	b3 _{_}	0
0	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

Krok 4

Zakryj wszystkie kolumny zawierające zero (oznaczone gwiazdką).

×	×
0*	2 _{_}	0	4 _{_}
b1 _{_}	0*	b3 _{_}	0
0	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

Znajdź niepokryte zero i wypełnij je. (Jeśli wszystkie zera są zakryte, przejdź do kroku 5.)

Jeśli zero znajduje się w tym samym wierszu co zero oznaczone gwiazdką, zakryj odpowiedni wiersz i odkryj kolumnę zerem oznaczonym gwiazdką.
Następnie GOTO „Znajdź niezakryte zero i przygotuj je”.
- Tutaj drugie zero wiersza 1 jest odkryte. Ponieważ w wierszu 1 jest kolejne zero oznaczone gwiazdką, zakrywamy wiersz 1 i odkrywamy kolumnę 1.
- Następnie odkrywane jest drugie zero rzędu 2. Zakrywamy rząd 2 i odkrywamy kolumnę 2.

	×
0*	2 _{_}	0'	4 _{_}	×
b1 _{_}	0*	b3 _{_}	0
0	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄


0*	2 _{_}	0'	4 _{_}	×
b1 _{_}	0*	b3 _{_}	0'	×
0	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

W przeciwnym razie niezakryte zero nie ma przypisanego zera w swoim wierszu. Wykonujemy ścieżkę zaczynając od zera, wykonując następujące czynności:
1. Krok podrzędny 1: znajdź zero oznaczone gwiazdką w odpowiedniej kolumnie. Jeśli istnieje, przejdź do podkroku 2, w przeciwnym razie przerwij.
2. Podetap 2: Znajdź pierwsze zero w odpowiednim wierszu (zawsze powinno być jedno). Przejdź do kroku 1.

Zero w rzędzie 3 jest odkryte. Dodajemy do ścieżki pierwsze zero z wiersza 1, potem drugie zero z wiersza 1 i gotowe.


0*	2 _{_}	0'	4 _{_}	×
b1 _{_}	0*	b3 _{_}	0'	×
0'	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

(Kontynuacja gałęzi Else) Dla wszystkich zer napotkanych na ścieżce, zer oznaczonych gwiazdką i zer oznaczonych gwiazdką.
- Ponieważ ścieżka zaczyna się i kończy zerem primowanym podczas zamiany zer oznaczonych gwiazdką, przypisaliśmy jeszcze jedno zero.

0	2 _{_}	0*	4 _{_}
b1 _{_}	0*	b3 _{_}	0
0*	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

(Kontynuacja gałęzi Else) Odznacz wszystkie primowane zera i odkryj wszystkie linie.
Powtórz poprzednie kroki (kontynuuj zapętlanie, aż do osiągnięcia powyższego „przeskocz do kroku 5”).
- Zakrywamy kolumny 1, 2 i 3. Drugie zero w rzędzie 2 jest odkryte, więc zakrywamy rząd 2 i odkrywamy kolumnę 2:

×		×
0	2 _{_}	0*	4 _{_}
b1 _{_}	0*	b3 _{_}	0'	×
0*	c ₂	c ₃	do ₄
0	re ₂	re ₃	d ₄

Wszystkie zera są teraz pokryte minimalną liczbą wierszy i kolumn.

Powyższy szczegółowy opis jest tylko jednym ze sposobów narysowania minimalnej liczby linii pokrywających wszystkie zera. Inne metody też działają.

Krok 5

Znajdź najniższą odkrytą wartość. Odejmij to od każdego nieoznaczonego elementu i dodaj do każdego elementu objętego dwoma liniami.

Jest to równoważne odjęciu liczby od wszystkich wierszy, które nie są objęte, i dodaniu tej samej liczby do wszystkich kolumn, które są objęte. Te operacje nie zmieniają optymalnych przypisań.

Powtarzaj kroki 4–5, aż przypisanie będzie możliwe; dzieje się tak, gdy minimalna liczba linii użytych do pokrycia wszystkich zer jest równa min (liczba osób, liczba przydziałów), przy założeniu, że zmienne fikcyjne (zwykle koszt maksymalny) są używane do wypełnienia, gdy liczba osób jest większa niż liczba zadań.

Jeśli postępujesz zgodnie z tą konkretną wersją algorytmu, zera oznaczone gwiazdką tworzą minimalne przypisanie.

Z twierdzenia Kőniga minimalna liczba linii (minimalne pokrycie wierzchołków) wyniesie $n$ (rozmiar maksymalnego dopasowania). Tak więc, gdy $n$ wierszy, przypisanie minimalnego kosztu można znaleźć, patrząc tylko na zera w macierzy.

Bibliografia

RE Burkard, M. Dell'Amico, S. Martello: Problemy z zadaniami (poprawiony przedruk). SIAM, Filadelfia (Pensylwania) 2012. ISBN 978-1-61197-222-1
M. Fischetti, „Lezioni di Ricerca Operativa”, Edizioni Libreria Progetto Padova, Italia, 1995.
R. Ahuja , T. Magnanti , J. Orlin , „Przepływy sieciowe”, Prentice Hall, 1993.
S. Martello, „Jeno Egerváry: od początków węgierskiego algorytmu do komunikacji satelitarnej”. Central European Journal of Operational Research 18, 47–58, 2010

Linki zewnętrzne

Bruff, Derek, Problem przypisania i metoda węgierska (formalizm macierzowy).
Mordecai J. Golin, Dopasowanie dwustronne i metoda węgierska (formalizm bigraficzny), notatki z kursu, Uniwersytet Nauki i Technologii w Hongkongu .
Węgierski algorytm maksymalnego dopasowania (oba formalizmy) na stronie Brilliant.
RA Pilgrim, algorytm przypisania Munkresa. Zmodyfikowane dla macierzy prostokątnych , notatki z kursu, Murray State University .
Mike Dawes , The Optimal Assignment Problem , Notatki z kursu, University of Western Ontario .
O węgierskiej metodzie Kuhna – hołd z Węgier , András Frank , Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapeszt, Węgry.
Wykład: Podstawy Badań Operacyjnych - Zadanie Zadania - Algorytm Węgierski , prof. G. Srinivasan, Katedra Studiów nad Zarządzaniem, IIT Madras.
Rozszerzenie: Analiza wrażliwości przypisania (o złożoności czasowej O(n^4)) , Liu, Shell.
Rozwiąż dowolny problem z zadaniem online , zawiera objaśnienie krok po kroku algorytmu węgierskiego.

Implementacje

$,$ że nie wszystkie z nich spełniają tak twierdzą $mogą$ zawierać błędy, implementować wolniejszy mieć W najgorszym przypadku przykładowy kod z Wikipedii mógłby zostać później zmodyfikowany w celu uwzględnienia kodu exploita. Weryfikacja i testy porównawcze są konieczne w przypadku korzystania z takich przykładów kodu od nieznanych autorów.