Moduł Algorithm::Munkres

Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowa

Obsługa modułu Algorithm::Munkres

use Algorithm::Munkres @mat = ( [2, 4, 7, 9], [3, 9, 5, 1], [8, 2, 9, 7], ); assign(\@mat,\@out_mat); # tablica @out_mat zawierać będzie (0,3,1,2) # i-ty element tablicy wyjściowej wskazuje, który rząd we wierszu i-tym został wybrany

Co to jest?

Moduł ten zawiera implementację algorytmu węgierskiego, który rozwiązuje w czasie wielomianowym problem przydziału. Moduł rozszerza algorytm węgierski z macierzy kwadratowych do prostokątnych przez uzupełnienie brakującymi zerami.

Szczegóły

Problem przydziału: Mamy N zadań, N pracowników i czasy jakie są potrzebne na wykonanie każdego zadania przez każdego z pracowników (macierz NxN)). Należy tak dobrać zadania do pracowników by czas na wykonanie wszystkich zadań był jak najmniejszy.

Na przyklad dla N=3 i następującej macierzy z czasami: x y z p 2 4 7 q 3 9 5 r 8 2 9 , gdzie p,q,r to zadania a x,y,z to pracownicy.

Możliwe rozwiązania to: Total 1. 2, 9, 9 20 2. 2, 2, 5 9 3. 3, 4, 9 16 4. 3, 2, 7 12 5. 8, 9, 7 24 6. 8, 4, 5 17 Optymalnym rozwiązaniem jest rozwiązanie drugie. Tego typu (brute-force) rozwiązanie, jest efektywne tylko dla małych N, ponieważ ilość wszystkich rozwiązań to N! (dla N=10 mamy 3628800 rozwiązań).

Wejście

Macierz wejściowa powinna być dwu-wymiarowa, procedura assign oczekuje referencji do tej macierzy. Na przyklad: assign(\@inp_mat, \@out_mat);.

Wyjście

Drugim argumentem procedury assign jest referencja do tablicy wyjściowej (jedno-wymiarowej Nx1).

Dla powyższego przykladu macierz wyjściowa będzie równa: (0,2,1), gdzie 0-wy element oznacza, że 0-we zadanie jest przypisane do 0-wego pracownika (czas=2) 1-wszy element oznacza, że 1-wsze zadanie jest przypisane do 2-giego pracownika (czas=5) 2-gi element oznacza, że 2-gie zadanie jest przypisany do 1-wszego pracownika (czas=2)

Dodatkowe informacje

Więcej ta temat algorytmu węgierskiego znajduje się tu. Bardzo ładną prezentację on-line algorytmu mozna znaleźć tu.

Dołączam własną implementację algorytmu węgierskiego w języku Java:
Hungary.java
Matrix.java

Cała dokumentacja modułu znajduje się na http://search.cpan.org/~anaghakk/Algorithm-Munkres-0.06/lib/Algorithm/Munkres.pm

Autor opracowania

P.B.

Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowa - Perl - Wyklady
[c] Piotr Arłukowicz, materiały z tej strony udostępnione są na licencji GNU.