Metoda węgierska

Ten artykuł od 2016-02 zawiera treści, przy których brakuje odnośników do źródeł.

Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Metoda węgierska – algorytm pozwalający rozwiązać problem przypisania w czasie wielomianowym. Została ona dopracowana oraz opublikowana przez Harolda Kuhna w roku 1955. Została ona nazwana „metodą węgierską” z uwagi na fakt, że została ona wyprowadzona na podstawie wcześniejszych prac dwóch węgierskich matematyków: Dénesa Kőniga i Jenő Egerváry'ego.

W roku 1957 profesor matematyki James Raymond Munkres zauważył, że algorytm węgierski jest silnie wielomianowy. Od tamtej pory metoda węgierska jest również znana jako algorytm Kuhna-Munkersa.

Założenie: mamy 'N' zadań do wykonania oraz 'N' maszyn, które mogą wykonywać zadania

Dane przedstawiamy w postaci macierzy NxN takiej, że indeksami wierszy będą np. maszyny a kolumn zadania. Każda maszyna będzie posiadała swój indywidualny koszt wykonania danego zadania.

Posiadając tak zdefiniowaną macierz możemy przystąpić do wykonywania algorytmu

• Krok 1: Dla każdego wiersza odejmujemy od niego jego minimum
• Krok 2: Dla każdej kolumny odejmujemy od niej jej minimum
• Krok 3: Zakreślamy wszystkie 'zera' występujące w macierzy jak najmniejszą liczbą linii.

UWAGA! Nie ma jednej jasno zdefiniowanej metody zakreślania, można przykładowo stosować:

• metoda rogu północno – zachodniego,
• minimum w wierszu,
• minimum w kolumnie,
• minimum w tabeli.

Ważne natomiast jest, aby po wybraniu określonej metody wybierania, stosować ją do samego końca.

Załóżmy, że udało się nam zakreślić wszystkie 'zera' przy użyciu k linii.

1. Jeżeli k < N znajdujemy minimum ze wszystkich niezakreślonych elementów. Załóżmy, że jest to m. Odejmujemy m od każdego niezakreślonego elementu oraz dodajemy m do wszystkich elementów, które leżą na przecięciu linii zakreśleń.
2. Jeżeli k = N to idziemy do kroku 4.

• Krok 4: Startując od pierwszego wiersza i idąc w dół dokonujemy przypisań 'maszyna - zadanie'. Po wykonaniu danego przypisania kasujemy dany wiersz i kolumnę z macierzy i idziemy dalej.

Przypisanie może być jednoznaczne tylko wtedy, jeżeli w danym wierszu występuje dokładnie jedno zero. Pozycja tego zera definiuje nam przypisanie np.: jeżeli jakieś 'zero' ma współrzędne (2,3) i jest jedynym zerem w wierszu drugim to znaczy, że do 3 zadania została przypisana 2 maszyna. Jeżeli po przejściu wszystkich wierszy nie byliśmy w stanie dokonać wszystkich N przypisań to przechodzimy na kolumny. Startujemy z kolumny pierwszej i idziemy w prawo.

Może wystąpić taka sytuacja, że będziemy mieli więcej zer w danym wierszu. Wtedy należy arbitralnie wybrać przypisanie.

• algorytm Dijkstry

• http://www.sbg.bio.ic.ac.uk/phunkee/html/hungarian.html