Munkres Yi Cao.m: Unterschied zwischen den Versionen
(Die Seite wurde neu angelegt: „function [assignment,cost] = Munkres_Yi_Cao(costMat) % MUNKRES Munkres (Hungarian) Algorithm for Linear Assignment Problem. % % [ASSIGN,COST] = munkres(COST…“) |
Keine Bearbeitungszusammenfassung |
||
Zeile 1: | Zeile 1: | ||
function [assignment,cost] = Munkres_Yi_Cao(costMat) | function [assignment,cost] = Munkres_Yi_Cao(costMat) | ||
% MUNKRES Munkres (Hungarian) Algorithm for Linear Assignment Problem. | % MUNKRES Munkres (Hungarian) Algorithm for Linear Assignment Problem. | ||
% | % | ||
% [ASSIGN,COST] = munkres(COSTMAT) returns the optimal column indices, | % [ASSIGN,COST] = munkres(COSTMAT) returns the optimal column indices, | ||
% ASSIGN assigned to each row and the minimum COST based on the assignment | % ASSIGN assigned to each row and 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 | % problem represented by the COSTMAT, where the (i,j)th element represents the cost to assign the jth | ||
% job to the ith worker. | % job to the ith worker. | ||
% | % | ||
% Partial assignment: This code can identify a partial assignment is a full | % Partial assignment: This code can identify a partial assignment is a full | ||
% assignment is not feasible. For a partial assignment, there are some | % assignment is not feasible. For a partial assignment, there are some | ||
% zero elements in the returning assignment vector, which indicate | % zero elements in the returning assignment vector, which indicate | ||
% un-assigned tasks. The cost returned only contains the cost of partially | % un-assigned tasks. The cost returned only contains the cost of partially | ||
% assigned tasks. | % assigned tasks. | ||
% This is vectorized implementation of the algorithm. It is the fastest | % This is vectorized implementation of the algorithm. It is the fastest | ||
% among all Matlab implementations of the algorithm. | % among all Matlab implementations of the algorithm. | ||
% Examples | % Examples | ||
% Example 1: a 5 x 5 example | % Example 1: a 5 x 5 example | ||
%{ | %{ | ||
[assignment,cost] = munkres(magic(5)); | [assignment,cost] = munkres(magic(5)); | ||
disp(assignment); % 3 2 1 5 4 | disp(assignment); % 3 2 1 5 4 | ||
disp(cost); %15 | disp(cost); %15 | ||
%} | %} | ||
% Example 2: 400 x 400 random data | % Example 2: 400 x 400 random data | ||
%{ | %{ | ||
n=400; | n=400; | ||
A=rand(n); | A=rand(n); | ||
tic | tic | ||
[a,b]=munkres(A); | [a,b]=munkres(A); | ||
toc % about 2 seconds | toc % about 2 seconds | ||
%} | %} | ||
% Example 3: rectangular assignment with inf costs | % Example 3: rectangular assignment with inf costs | ||
%{ | %{ | ||
A=rand(10,7); | A=rand(10,7); | ||
A(A>0.7)=Inf; | A(A>0.7)=Inf; | ||
[a,b]=munkres(A); | [a,b]=munkres(A); | ||
%} | %} | ||
% Example 4: an example of partial assignment | % Example 4: an example of partial assignment | ||
%{ | %{ | ||
A = [1 3 Inf; Inf Inf 5; Inf Inf 0.5]; | A = [1 3 Inf; Inf Inf 5; Inf Inf 0.5]; | ||
[a,b]=munkres(A) | [a,b]=munkres(A) | ||
%} | %} | ||
% a = [1 0 3] | % a = [1 0 3] | ||
% b = 1.5 | % b = 1.5 | ||
% Reference: | % Reference: | ||
% "Munkres' Assignment Algorithm, Modified for Rectangular Matrices", | % "Munkres' Assignment Algorithm, Modified for Rectangular Matrices", | ||
% http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html | % http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html | ||
% version 2.3 by Yi Cao at Cranfield University on 11th September 2011 | % version 2.3 by Yi Cao at Cranfield University on 11th September 2011 |
Version vom 9. Oktober 2021, 11:45 Uhr
function [assignment,cost] = Munkres_Yi_Cao(costMat) % MUNKRES Munkres (Hungarian) Algorithm for Linear Assignment Problem. % % [ASSIGN,COST] = munkres(COSTMAT) returns the optimal column indices, % ASSIGN assigned to each row and 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. % % Partial assignment: This code can identify a partial assignment is a full % assignment is not feasible. For a partial assignment, there are some % zero elements in the returning assignment vector, which indicate % un-assigned tasks. The cost returned only contains the cost of partially % assigned tasks.
% 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)); disp(assignment); % 3 2 1 5 4 disp(cost); %15 %} % Example 2: 400 x 400 random data %{ n=400; A=rand(n); tic [a,b]=munkres(A); toc % about 2 seconds %} % Example 3: rectangular assignment with inf costs %{ A=rand(10,7); A(A>0.7)=Inf; [a,b]=munkres(A); %} % Example 4: an example of partial assignment %{ A = [1 3 Inf; Inf Inf 5; Inf Inf 0.5]; [a,b]=munkres(A) %} % a = [1 0 3] % b = 1.5 % Reference: % "Munkres' Assignment Algorithm, Modified for Rectangular Matrices", % http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
% version 2.3 by Yi Cao at Cranfield University on 11th September 2011