MATLAB实例：Munkres指派算法

催微不带悲伤

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

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

下面的矩阵显示了工人和工作的每种组合所需的时间（以分钟为单位）。作业用J1，J2，J3和J4表示，工人用W1，W2，W3和W4表示。

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

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


2. Munkres指派算法MATLAB程序
munkres.m

1. function [assignment,cost] = munkres(costMat)
   
2. % MUNKRES   Munkres Assign Algorithm
   
3. %
   
4. % [ASSIGN,COST] = munkres(COSTMAT) returns the optimal assignment in ASSIGN
   
5. % with the minimum COST based on the assignment problem represented by the
   
6. % COSTMAT, where the (i,j)th element represents the cost to assign the jth
   
7. % job to the ith worker.
   
8. %
   
9. 
   
10. % This is vectorized implementation of the algorithm. It is the fastest
    
11. % among all Matlab implementations of the algorithm.
    
12. 
    
13. % Examples
    
14. % Example 1: a 5 x 5 example
    
15. %{
    
16. [assignment,cost] = munkres(magic(5));
    
17. [assignedrows,dum]=find(assignment);
    
18. disp(assignedrows'); % 3 2 1 5 4
    
19. disp(cost); %15
    
20. %}
    
21. % Example 2: 400 x 400 random data
    
22. %{
    
23. n=5;
    
24. A=rand(n);
    
25. tic
    
26. [a,b]=munkres(A);
    
27. toc               
    
28. %}
    
29. 
    
30. % Reference:
    
31. % "Munkres' Assignment Algorithm, Modified for Rectangular Matrices",
    
32. % http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
    
33. 
    
34. % version 1.0 by Yi Cao at Cranfield University on 17th June 2008
    
35. 
    
36. assignment = false(size(costMat));
    
37. cost = 0;
    
38. 
    
39. costMat(costMat~=costMat)=Inf;
    
40. validMat = costMat<Inf;
    
41. validCol = any(validMat);
    
42. validRow = any(validMat,2);
    
43. 
    
44. nRows = sum(validRow);
    
45. nCols = sum(validCol);
    
46. n = max(nRows,nCols);
    
47. if ~n
    
48.     return
    
49. end
    
50.      
    
51. dMat = zeros(n);
    
52. dMat(1:nRows,1:nCols) = costMat(validRow,validCol);
    
53. 
    
54. %*************************************************
    
55. % Munkres' Assignment Algorithm starts here
    
56. %*************************************************
    
57. 
    
58. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
59. %   STEP 1: Subtract the row minimum from each row.
    
60. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
61. dMat = bsxfun(@minus, dMat, min(dMat,[],2));
    
62. 
    
63. %**************************************************************************
    
64. %   STEP 2: Find a zero of dMat. If there are no starred zeros in its
    
65. %           column or row start the zero. Repeat for each zero
    
66. %**************************************************************************
    
67. zP = ~dMat;
    
68. starZ = false(n);
    
69. while any(zP(:))
    
70.     [r,c]=find(zP,1);
    
71.     starZ(r,c)=true;
    
72.     zP(r,:)=false;
    
73.     zP(:,c)=false;
    
74. end
    
75. 
    
76. while 1
    
77. %**************************************************************************
    
78. %   STEP 3: Cover each column with a starred zero. If all the columns are
    
79. %           covered then the matching is maximum
    
80. %**************************************************************************
    
81.     primeZ = false(n);
    
82.     coverColumn = any(starZ);
    
83.     if ~any(~coverColumn)
    
84.         break
    
85.     end
    
86.     coverRow = false(n,1);
    
87.     while 1
    
88.         %**************************************************************************
    
89.         %   STEP 4: Find a noncovered zero and prime it.  If there is no starred
    
90.         %           zero in the row containing this primed zero, Go to Step 5.
    
91.         %           Otherwise, cover this row and uncover the column containing
    
92.         %           the starred zero. Continue in this manner until there are no
    
93.         %           uncovered zeros left. Save the smallest uncovered value and
    
94.         %           Go to Step 6.
    
95.         %**************************************************************************
    
96.         zP(:) = false;
    
97.         zP(~coverRow,~coverColumn) = ~dMat(~coverRow,~coverColumn);
    
98.         Step = 6;
    
99.         while any(any(zP(~coverRow,~coverColumn)))
    
100.             [uZr,uZc] = find(zP,1);
     
101.             primeZ(uZr,uZc) = true;
     
102.             stz = starZ(uZr,:);
     
103.             if ~any(stz)
     
104.                 Step = 5;
     
105.                 break;
     
106.             end
     
107.             coverRow(uZr) = true;
     
108.             coverColumn(stz) = false;
     
109.             zP(uZr,:) = false;
     
110.             zP(~coverRow,stz) = ~dMat(~coverRow,stz);
     
111.         end
     
112.         if Step == 6
     
113.             % *************************************************************************
     
114.             % STEP 6: Add the minimum uncovered value to every element of each covered
     
115.             %         row, and subtract it from every element of each uncovered column.
     
116.             %         Return to Step 4 without altering any stars, primes, or covered lines.
     
117.             %**************************************************************************
     
118.             M=dMat(~coverRow,~coverColumn);
     
119.             minval=min(min(M));
     
120.             if minval==inf
     
121.                 return
     
122.             end
     
123.             dMat(coverRow,coverColumn)=dMat(coverRow,coverColumn)+minval;
     
124.             dMat(~coverRow,~coverColumn)=M-minval;
     
125.         else
     
126.             break
     
127.         end
     
128.     end
     
129.     %**************************************************************************
     
130.     % STEP 5:
     
131.     %  Construct a series of alternating primed and starred zeros as
     
132.     %  follows:
     
133.     %  Let Z0 represent the uncovered primed zero found in Step 4.
     
134.     %  Let Z1 denote the starred zero in the column of Z0 (if any).
     
135.     %  Let Z2 denote the primed zero in the row of Z1 (there will always
     
136.     %  be one).  Continue until the series terminates at a primed zero
     
137.     %  that has no starred zero in its column.  Unstar each starred
     
138.     %  zero of the series, star each primed zero of the series, erase
     
139.     %  all primes and uncover every line in the matrix.  Return to Step 3.
     
140.     %**************************************************************************
     
141.     rowZ1 = starZ(:,uZc);
     
142.     starZ(uZr,uZc)=true;
     
143.     while any(rowZ1)
     
144.         starZ(rowZ1,uZc)=false;
     
145.         uZc = primeZ(rowZ1,:);
     
146.         uZr = rowZ1;
     
147.         rowZ1 = starZ(:,uZc);
     
148.         starZ(uZr,uZc)=true;
     
149.     end
     
150. end
     
151. 
     
152. % Cost of assignment
     
153. assignment(validRow,validCol) = starZ(1:nRows,1:nCols);
     
154. cost = sum(costMat(assignment));

复制代码

demo_munkres.m

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

复制代码

3. 指派结果

1. >> demo_munkres
   
2. 
   
3. assignment =
   
4. 
   
5.   4×4 logical 数组
   
6. 
   
7.    0   0   1   0
   
8.    0   1   0   0
   
9.    1   0   0   0
   
10.    0   0   0   1
    
11. 
    
12. 
    
13. cost =
    
14. 
    
15.    140
    
16. 
    
17. 
    
18. order =
    
19. 
    
20.      3     2     1     4
    

复制代码