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.