Metoda węgierska

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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.

  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.

Teraz parę słów wyjaśnienia.

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.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]