Munkres Yi Cao.m: Unterschied zwischen den Versionen

Aus HSHL Mechatronik
Zur Navigation springen Zur Suche springen
(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