Metoda węgierska
 |
Ten artykuł od 2016-02 zawiera treści, przy których brakuje odnośników do źródeł. |
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.
Opis algorytmu[edytuj | edytuj kod]
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.
- 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ń.
- 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.