Uogólnienie węgierskiego algorytmu na ogólne niekierowane wykresy?

14

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.

Dai Le
źródło
2
A co z algorytmem dopasowania Edmondsa? en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
Arman
1
@Arman - Tak też myślałem. Dzięki za link, Wikipedia ma zaskakująco szczegółową prezentację algorytmu kwitnienia Edmonda.
Abraham Flaxman
2
Nawiasem mówiąc, algorytm dopasowywania Edmondsa jest również oparty na metodzie Primal-Dual.
Arman
1
Dzięki Arman. Link do Wikipedii wskazuje także na książkę „Lovász, László; Plummer, Michael (1986). Teoria dopasowywania” do ważonej wersji algorytmu Edmondsa. Naprawdę powinnam sprawdzić tę książkę. Dziękuję Wam bardzo za wasze komentarze! Być może, jeśli ktoś z was potrafi na wysokim poziomie wyjaśnić, w jaki sposób algorytm uogólnia algorytm węgierski, z pewnością można udzielić odpowiedzi.
Dai Le
1
Myślę, że to całkiem niezła odpowiedź :). Arman, powinieneś to dodać
Suresh Venkat,

Odpowiedzi:

16

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

Arman
źródło
9

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ć.

Stan Wagon
źródło
Mam też wersje demonstracyjne, które każdy może obejrzeć przy pomocy darmowego oprogramowania: pierwszy pokazuje ładnie kwitnący .... < demonstrations.wolfram.com/... > < demonstrations.wolfram.com/TheHungarianMaximumMatchingAl algorytm > < demonstrations.wolfram.com/ PlatingDominoesOnACheckerboard >
Stan Wagon
Właśnie zaprogramowałem nieważony kwiat, jak podano w Korte / Vygen. Widzę, że jego kod może przyspieszać (np. Zacząć od maksymalnego dopasowania, a nie nic), ale fajną rzeczą jest to, że jego kod proceduralny jest podany w formie, którą można łatwo przetłumaczyć na działający kod. Dalej: ważony kwiat, który jest znacznie trudniejszy.
Stan Wagon