| 1 |
NAME |
| 2 |
Algorithm-Munkres : Perl extension for Munkres' solution to |
| 3 |
classical Assignment problem for square and rectangular matrices |
| 4 |
This module extends the solution of Assignment problem for square |
| 5 |
matrices to rectangular matrices by padding zeros. Thus a rectangular |
| 6 |
matrix is converted to square matrix by padding necessary zeros. |
| 7 |
|
| 8 |
SYNOPSIS |
| 9 |
use Algorithm::Munkres; |
| 10 |
|
| 11 |
@mat = ( |
| 12 |
[2, 4, 7, 9], |
| 13 |
[3, 9, 5, 1], |
| 14 |
[8, 2, 9, 7], |
| 15 |
); |
| 16 |
|
| 17 |
assign(\@mat,\@out_mat); |
| 18 |
|
| 19 |
Then the @out_mat array will have the output as: (0,3,1,2), |
| 20 |
where |
| 21 |
0th element indicates that 0th row is assigned 0th column i.e value=2 |
| 22 |
1st element indicates that 1st row is assigned 3rd column i.e.value=1 |
| 23 |
2nd element indicates that 2nd row is assigned 1st column.i.e.value=2 |
| 24 |
3rd element indicates that 3rd row is assigned 2nd column.i.e.value=0 |
| 25 |
|
| 26 |
DESCRIPTION |
| 27 |
Assignment Problem: Given N jobs, N workers and the time taken by |
| 28 |
each worker to complete a job then how should the assignment of a |
| 29 |
Worker to a Job be done, so as to minimize the time taken. |
| 30 |
|
| 31 |
Thus if we have 3 jobs p,q,r and 3 workers x,y,z such that: |
| 32 |
x y z |
| 33 |
p 2 4 7 |
| 34 |
q 3 9 5 |
| 35 |
r 8 2 9 |
| 36 |
|
| 37 |
where the cell values of the above matrix give the time required |
| 38 |
for the worker(given by column name) to complete the job(given by |
| 39 |
the row name) |
| 40 |
|
| 41 |
then possible solutions are: |
| 42 |
Total |
| 43 |
1. 2, 9, 9 20 |
| 44 |
2. 2, 2, 5 9 |
| 45 |
3. 3, 4, 9 16 |
| 46 |
4. 3, 2, 7 12 |
| 47 |
5. 8, 9, 7 24 |
| 48 |
6. 8, 4, 5 17 |
| 49 |
|
| 50 |
Thus (2) is the optimal solution for the above problem. |
| 51 |
This kind of brute-force approach of solving Assignment problem |
| 52 |
quickly becomes slow and bulky as N grows, because the number of |
| 53 |
possible solution are N! and thus the task is to evaluate each |
| 54 |
and then find the optimal solution.(If N=10, number of possible |
| 55 |
solutions: 3628800 !) |
| 56 |
Munkres' gives us a solution to this problem, which is implemented |
| 57 |
in this module. |
| 58 |
|
| 59 |
This module also solves Assignment problem for rectangular matrices |
| 60 |
(M x N) by converting them to square matrices by padding zeros. ex: |
| 61 |
If input matrix is: |
| 62 |
[2, 4, 7, 9], |
| 63 |
[3, 9, 5, 1], |
| 64 |
[8, 2, 9, 7] |
| 65 |
i.e 3 x 4 then we will convert it to 4 x 4 and the modified input |
| 66 |
matrix will be: |
| 67 |
[2, 4, 7, 9], |
| 68 |
[3, 9, 5, 1], |
| 69 |
[8, 2, 9, 7], |
| 70 |
[0, 0, 0, 0] |
| 71 |
|
| 72 |
EXPORT |
| 73 |
"assign" function by default. |
| 74 |
|
| 75 |
INPUT |
| 76 |
The input matrix should be in a two dimensional array(array of |
| 77 |
array) and the 'assign' subroutine expects a reference to this |
| 78 |
array and not the complete array. |
| 79 |
eg:assign(\@inp_mat, \@out_mat); |
| 80 |
The second argument to the assign subroutine is the reference |
| 81 |
to the output array. |
| 82 |
|
| 83 |
OUTPUT |
| 84 |
The assign subroutine expects references to two arrays as its |
| 85 |
input paramenters. The second parameter is the reference to the |
| 86 |
output array. This array is populated by assign subroutine. This |
| 87 |
array is single dimensional Nx1 matrix. |
| 88 |
For above example the output array returned will be: |
| 89 |
(0, |
| 90 |
2, |
| 91 |
1) |
| 92 |
|
| 93 |
where |
| 94 |
0th element indicates that 0th row is assigned 0th column i.e value=2 |
| 95 |
1st element indicates that 1st row is assigned 2nd column i.e.value=5 |
| 96 |
2nd element indicates that 2nd row is assigned 1st column.i.e.value=2 |
| 97 |
|
| 98 |
SEE ALSO |
| 99 |
1. http://216.249.163.93/bob.pilgrim/445/munkres.html |
| 100 |
|
| 101 |
2. Munkres, J. Algorithms for the assignment and transportation |
| 102 |
Problems. J. Siam 5 (Mar. 1957), 32-38 |
| 103 |
|
| 104 |
3. François Bourgeois and Jean-Claude Lassalle. 1971. |
| 105 |
An extension of the Munkres algorithm for the assignment |
| 106 |
problem to rectangular matrices. |
| 107 |
Communication ACM, 14(12):802-804 |
| 108 |
|
| 109 |
AUTHOR |
| 110 |
Anagha Kulkarni, University of Minnesota Duluth |
| 111 |
kulka020 <at> d.umn.edu |
| 112 |
|
| 113 |
Ted Pedersen, University of Minnesota Duluth |
| 114 |
tpederse <at> d.umn.edu |
| 115 |
|
| 116 |
COPYRIGHT AND LICENSE |
| 117 |
Copyright (C) 2007-2008, Ted Pedersen and Anagha Kulkarni |
| 118 |
|
| 119 |
This program is free software; you can redistribute it and/or modify it |
| 120 |
under the terms of the GNU General Public License as published by the |
| 121 |
Free Software Foundation; either version 2 of the License, or (at your |
| 122 |
option) any later version. This program is distributed in the hope that |
| 123 |
it will be useful, but WITHOUT ANY WARRANTY; without even the implied |
| 124 |
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 125 |
GNU General Public License for more details. |
| 126 |
|
| 127 |
You should have received a copy of the GNU General Public License along |
| 128 |
with this program; if not, write to the Free Software Foundation, Inc., |
| 129 |
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 130 |
|