/ 
Algorithm-Munkres
River stage one • 2 direct dependents • 2 total dependents
/ Algorithm::Munkres

NAME

Algorithm::Munkres - Perl extension for Munkres' solution to classical Assignment problem

SYNOPSIS

use Algorithm::Munkres;

    @mat = (
        [ 12, 3, 7, 4, 10],
	[ 5, 10, 6, 2, 4],
	[ 8, 5, 1, 4, 9],
	[ 15, 2, 7, 8, 10],
	[ 7, 2, 8, 1, 12],
	);

assign(\@mat);

DESCRIPTION

This module implements the Munkres' solution to classical Assignment problem. If we have a MxN matrix of Workers and the Jobs to be assigned, then this module assigns one job to each worker in such a way that overall/sum of the cost of jobs is the lowest possible value. eg: MxN = [12 3 7 4 10 5 10 6 2 4 8 5 1 4 9 15 2 7 8 10 7 2 8 1 12]

is the input matrix, then this module will return a matrix of Mx1 dimensions, like: solution = [3 4 2 1 0]

where value '3' says that 4th column in the input matrix is the assigned column/solution for the 1st row. value '4' says that 5th column in the input matrix is the assigned column/solution for the 2st row and so on. Thus for the given input matrix, the optimal assignment i.e. the assignment which minimizes the sum of all job costs is: eg: MxN = [0 0 0 4 0 0 0 0 0 4 0 0 1 0 0 0 2 0 0 0 7 0 0 0 0]

Note: The 'assign' subroutine expects the input array's reference and not the complete array. eg:assign(\@mat);

EXPORT

"assign" function by default.

SEE ALSO

http://216.249.163.93/bob.pilgrim/445/munkres.html

AUTHOR

Anagha Kulkarni, University of Minnesota, Duluth kulka020@d.umn.edu

Ted Pedersen, University of Minnesota, Duluth tpederse@d.umn.edu

COPYRIGHT AND LICENSE

Copyright (C) 2000-2004, Ted Pedersen and Anagha Kulkarni

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.