matlab实例：munkres指派算法-尊龙凯时

作者：凯鲁嘎吉 - 博客园 http://www.cnblogs.com/kailugaji/

1. 指派问题陈述

指派问题涉及将机器分配给任务，将工人分配给工作，将足球运动员分配给职位等。目标是确定最佳分配，例如，使总成本最小化或使团队效率最大化。指派问题是组合优化领域中的一个基本问题。

例如，假设我们有四个工作需要由四个工作人员执行。因为每个工人都有不同的技能，所以执行工作所需的时间取决于分配给该工人的工人。

下面的矩阵显示了工人和工作的每种组合所需的时间（以分钟为单位）。作业用j1，j2，j3和j4表示，工人用w1，w2，w3和w4表示。

	j1	j2	j3	j4
w1	82	83	69	92
w2	77	37	49	92
w3	11	69	5	86
w4	8	9	98	23

每个工人应仅执行一项工作，目标是最大程度地减少执行所有工作所需的总时间。

事实证明，将工人1分配给作业3，将工人2分配给作业2，将工人3分配给作业1，将工人4分配给作业4是最佳选择。那么，总时间为69 37 11 23 = 140分钟。所有其他任务导致需要更多时间。

2. munkres指派算法matlab程序

munkres.m

function [assignment,cost] = munkres(costmat)
% munkres   munkres assign algorithm 
%
% [assign,cost] = munkres(costmat) returns the optimal assignment in assign
% with the minimum cost based on the assignment problem represented by the
% costmat, where the (i,j)th element represents the cost to assign the jth
% job to the ith worker.
%
% this is vectorized implementation of the algorithm. it is the fastest
% among all matlab implementations of the algorithm.
% examples
% example 1: a 5 x 5 example
%{
[assignment,cost] = munkres(magic(5));
[assignedrows,dum]=find(assignment);
disp(assignedrows'); % 3 2 1 5 4
disp(cost); 
%}
% example 2: 400 x 400 random data
%{
n=5;
a=rand(n);
tic
[a,b]=munkres(a);
toc                 
%}
% reference:
% "munkres' assignment algorithm, modified for rectangular matrices", 
% http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
% version 1.0 by yi cao at cranfield university on 17th june 2008
assignment = false(size(costmat));
cost = 0;
costmat(costmat~=costmat)=inf;
validmat = costmat

demo_munkres.m

a=[82,83,69,92;77,37,49,92;11,69,5,86;8,9,98,23];
[assignment,cost]=munkres(a)  
[assignedrows,dum]=find(assignment);
order=assignedrows'

3. 指派结果

>> demo_munkres
assignment =
  4×4 logical 数组
   0   0   1   0
   0   1   0   0
   1   0   0   0
   0   0   0   1
cost =
   140
order =
     3     2     1     4

4. 参考文献

[1] munkres' assignment algorithm modified for rectangular matrices

[2] munkres assignment algorithm

[3] hungarian algorithm：the assignment problem

原文链接：http://www.cnblogs.com/kailugaji/p/11765596.html