Moduł Algorithm::Munkres
Uniwersytet Gdański - Instytut Matematyki - Zakład Informatyki - Strona domowaSpis treści
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.