Location : Home > Languages > Perl > Package Title : Algorithm::Munkres

名称

　Algorithm::Munkres - 正方または非正方行列に対する古典的な割り当て問題の Munkres 解法

　本モジュールでは正方行列に対する割り当て問題の解法を、非正方行列をゼロで埋めることで拡張している。

概要

use Algorithm::Munkres;

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

assign(\@mat,\@out_mat);

　このとき @out_mat 配列は出力として (0,3,1,2) を保持している。
ただし
　０番目の要素は、０番目の行が０番目の列に充てられていることを示す。すなわち value = 2、
　１番目の要素は、１番目の行が１番目の列に充てられていることを示す。すなわち value = 1、
　２番目の要素は、２番目の行が２番目の列に充てられていることを示す。すなわち value = 2、
　３番目の要素は、３番目の行が３番目の列に充てられていることを示す。すなわち value = 0
である。

説明

　割り当て問題（Assignment Problem）とは N 種類の業務と N 人の労働者と、各労働者がそれぞれの仕事を完遂するのに必要な時間が与えられたときに、誰にどの仕事を割り当てればかかる時間を最小化できるかという問題である。
　p, q, r ３種類の仕事と x, y, z の３人の労働者が以下のように与えられたとする。

    x  y  z		
 p  2  4  7
 q  3  9  5
 r  8  2  9

　ただし上の行列の各セルの値はそれぞれの労働者（列名で特定）がそれぞれの仕事（行名で特定）を完遂するのに必要な労働時間である。
　このとき可能な解は以下のとおりである。

	 	 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

　こうして、(2) が上記の問題の最適解となる。
　割り当て問題に対する総当り法（brute-force approach）は、N が大きくなるにつれて遅く大きな問題となる。なぜなら取りうる解の組み合わせ数が N! 通りで、このそれぞれについて評価し、最適解を求めねばならないからである。（もし N = 10 でも組み合わせ数は 3628800 である！）
　本モジュールで実装している Munkres 法はこの問題に対する解法を提供している。

　本モジュールでは正方でない行列 (M x N) に対する割り当て問題にも、ゼロで埋めることで正方行列にして解いている。たとえば入力行列が

 [2, 4, 7, 9],
 [3, 9, 5, 1],
 [8, 2, 9, 7]

　すなわち 3 x 4 であれば以下のようにこれを 4 x 4 に変換する。

 [2, 4, 7, 9],
 [3, 9, 5, 1],
 [8, 2, 9, 7],
 [0, 0, 0, 0]

エクスポート

　デフォルトでは "assign" 関数のみ。

入力

　入力号列は２次元配列（配列の配列）でなければならず、assign サブルーチンは、完全な配列ではなく、この配列への参照が渡されることを想定している。

assign(\@inp_mat, \@out_mat);

　assign サブルーチンへの２つめの引数は出力配列への参照である。

出力

　assign サブルーチンは入力パラメータとして２つの配列への参照を想定している。２つめのパラメータは出力配列への参照である。この配列は assign サブルーチンで設定される。この配列は Nx1 行列である。
　上述の例に対しては以下の出力配列を返す。

 (0,
  2,
  1)

ただし
　０番目の要素は、０番目の行が０番目の列に充てられていることを示す。すなわち value = 2、
　１番目の要素は、１番目の行が２番目の列に充てられていることを示す。すなわち value = 5、
　２番目の要素は、２番目の行が１番目の列に充てられていることを示す。すなわち value = 2、
である。

参考資料

1. http://216.249.163.93/bob.pilgrim/445/munkres.html
2. Munkres, J. Algorithms for the assignment and transportation Problems. J. Siam 5 (Mar. 1957), 32-38
3. Francois Bourgeois and Jean-Claude Lassalle. 1971.
   An extension of the Munkres algorithm for the assignment problem to rectangular matrices.
   Communication ACM, 14(12):802-804
   

著者

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

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

著作権とライセンス

　Copyright (C) 2005-2006, Ted Pedersen and Anagha Kulkarni

本プログラムはフリーソフトウェアであり、Free Software Foundation により公開された GNU General Public License （version 2 またはユーザの考えに基づきそれ以降のバージョン）の条件の下で修正／再配布してもよい。 　本プログラムは有用であると考え配布されているが、 MERCHANTABILITY または FITNESS FOR A PARTICULAR PURPOSE で保証されていたとしても無保証である。詳しくは GNU General Public License を参照のこと。
　本プログラムに関しては GNU General Public License のコピーを入手すべきである。もし手元になければ the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. まで連絡を。

Updated : 2007/06/13