Algorytm węgierski jest kombinatorycznym algorytmem optymalizacyjnym, który rozwiązuje problem dwustronnego dopasowania maksymalnej masy w czasie wielomianowym i przewidywał późniejszy rozwój ważnej metody pierwotnej podwójnej . Algorytm został opracowany i opublikowany przez Harolda Kuhna w 1955 r., Który nadał mu nazwę „algorytm węgierski”, ponieważ algorytm był oparty na wcześniejszych pracach dwóch węgierskich matematyków: Dénesa Kőniga i Jenő Egerváry. Munkres dokonał przeglądu algorytmu w 1957 r. I zauważył, że rzeczywiście jest to czas polityczny. Od tego czasu algorytm znany jest również jako algorytm Kuhna-Munkresa.
Chociaż węgierski zawiera podstawową ideę metody pierwotnej podwójnej, rozwiązuje on problem maksymalnego dopasowania dwustronnego maksymalnego ciężaru bezpośrednio bez użycia żadnych maszyn programowania liniowego (LP). Tak więc w odpowiedzi na następujące pytanie Jukka Suomela skomentował
Oczywiście możesz rozwiązać dowolny LP za pomocą uniwersalnego solwera LP, ale wyspecjalizowane algorytmy zazwyczaj mają znacznie lepszą wydajność. [...] Często można również uniknąć problemów takich jak używanie dokładnych liczb wymiernych vs. liczb zmiennoprzecinkowych; wszystko można łatwo zrobić za pomocą liczb całkowitych.
Innymi słowy, nie musisz się martwić, jak zaokrąglić rozwiązanie racjonalne / zmiennoprzecinkowe z solwera LP, aby uzyskać maksymalne idealne dopasowanie idealnego danego wykresu dwustronnego.
Moje pytanie jest następujące:
Czy istnieje uogólnienie węgierskiego algorytmu, który działa na ogólny niekierowany wykres bez użycia maszyn LP podobnie do ducha oryginalnego węgierskiego algorytmu?
Wolałbym nowoczesną i łatwą do odczytania ekspozycję zamiast oryginalnego, skomplikowanego papieru. Ale każdy wskaźnik będzie bardzo mile widziany!
Wielkie dzięki z góry i Wesołych Świąt !!!
Aktualizacja: Arman poniżej ładnie odpowiada na pytanie. Chciałbym tylko zauważyć , że innym dobrym źródłem do badania algorytmu Blossom Edmondsa (dla przypadku ważonego) jest Rozdział 11 Optymalizacji kombinatorycznej autorstwa Korte i Vygen . Książka Google faktycznie pokazuje prawie wszystkie części potrzebne do zrozumienia algorytmu.
Odpowiedzi:
Algorytm dopasowania Edmondsa (zwany również algorytmem Blossom) rozwiązuje maksymalne dopasowanie na ogólnych wykresach. W rzeczywistości jest to metoda uogólnienia ścieżek przemiennych. (Nie jestem pewien nazwy tej metody, ale powinna to być metoda Königa-Halla). W zasadzie znajduje ścieżki do rozszerzania (patrz strona wikipedia: http://en.wikipedia.org/wiki/Edmonds%27s_matching_alameterm ) bieżące dopasowanie i zatrzymuje się, jeśli nie ma już ścieżek rozszerzających. Na ogólnych wykresach jedyny problem występuje w cyklach nieparzystych. W algorytmie dopasowywania Edmondsa cykle nieparzyste są kurczone (kwiaty) i zużywane z powrotem w celu znalezienia rozwiązania.
Istnieje również zgodność między algorytmem Blossom a metodą Primal Dual. Cykle nieparzyste powodują ułamkowe skrajne punkty. Dlatego dodajemy tak zwane nierówności kwitnienia dla każdego nieparzystego cyklu.
Dzięki temu podejściu można również rozwiązywać problemy z idealnym dopasowaniem minimalnej wagi i maksymalnym dopasowaniem wagi.
Aby uzyskać szczegółowe informacje na temat algorytmu, patrz http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
Aby sformułować matematyczne i odpowiadającą im metodę pierwotną podwójną, zobacz http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf
źródło
Dwa lata temu, badając (nieważony) algorytm kwitnienia, znalazłem dwa świetne zestawy notatek, jeden autorstwa Tarjana i jeden autorstwa Zwicka. Sprawili, że nieważona sprawa wydawała się dość prosta i mogłem ją zaimplementować w Mathematica za pomocą rekurencji. Działa całkiem dobrze.
Notatki, które uznałem za przydatne, są
http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf i http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ tarjan-blossom.pdf
Wydzielają wszystko na bardzo proste terminy, które pozwalają myśleć rekurencyjnie, a następnie, jak zauważono, programować rekurencyjnie.
Myślę, że wszystko powinno działać w ważonej sprawie, którą próbuję teraz zaimplementować.
źródło