function [assignment, cost] = assignmentallpossible(distMatrix)
%ASSIGNMENTALLPOSSIBLE Compute solution of assignment problem
% ASSIGNMENTALLPOSSIBLE(DISTMATRIX) computes the optimal assignment
% (minimum overall costs) for the given rectangular distance or cost
% matrix, for example the assignment of tracks (in rows) to observations
% (in columns). The result is a column vector containing the assigned
% column number in each row (or 0 if no assignment could be done).
%
% [ASSIGNMENTALLPOSSIBLE, COST] = ASSIGNMENTALLPOSSIBLE(DISTMATRIX)
% returns the assignment vector and the overall cost.
%
% The distance matrix may contain infinite values (forbidden
% assignments). Internally, the infinite values are set to a very large
% finite number, so that the algorithm itself works on finite-number
% matrices. Before returning the assignment, all assignments with
% infinite distance are deleted (i.e. set to zero).
%
% The algorithm recursively steps over all possible assignment paths. It
% is very slow especially for large matrix dimensions. With this, it is
% only suited for computing a reference solution.
%
% <a href="assignment.html">assignment.html</a> <a href="http://www.mathworks.com/matlabcentral/fileexchange/6543">File Exchange</a> <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=EVW2A4G2HBVAU">Donate via PayPal</a>
%
% Markus Buehren
% Last modified 05.07.2011
[nOfRows, nOfColumns] = size(distMatrix);
% check for infinite values
finiteIndex = isfinite(distMatrix);
if isempty(find(~finiteIndex, 1))
% no infinite values contained in distMatrix
% initialize maxCost with suboptimal algorithm
[suboptimalassignment, maxCost] = assignmentsuboptimal2(distMatrix);
infValue = inf;
else
% distMatrix contains infinite values
originalDistMatrix = distMatrix;
finiteIndex = isfinite(distMatrix);
index = find(~finiteIndex);
if ~isempty(index)
maxFiniteValue = max(max(distMatrix(finiteIndex)));
if maxFiniteValue > 0
infValue = abs(10 * maxFiniteValue * nOfRows * nOfColumns);
else
infValue = 10;
end
if isempty(infValue)
% all elements are infinite
assignment = zeros(nOfRows, 1);
cost = 0;
return
end
distMatrix(index) = infValue;
end
maxCost = inf;
end
if nOfRows <= nOfColumns
[assignment, cost] = checksubtree(distMatrix, 0, maxCost, nOfRows, nOfColumns);
if isempty(assignment)
% suboptimal solution was equal to optimal solution
assignment = suboptimalassignment;
end
else
% use transposed matrix
[assignment, cost] = checksubtree(distMatrix.', 0, maxCost, nOfColumns, nOfRows);
if isempty(assignment)
% suboptimal solution was equal to optimal solution
assignment = suboptimalassignment;
else
% switch index
assignment = switchindex(assignment, nOfRows, nOfColumns);
end
end
if cost >= infValue
% remove invalid assignments
distMatrix = originalDistMatrix;
rowIndex = find(assignment);
costVector = distMatrix(rowIndex + nOfRows * (assignment(rowIndex)-1));
finiteIndex = isfinite(costVector);
cost = sum(costVector(finiteIndex));
assignment(rowIndex(~finiteIndex)) = 0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function newAssignment = switchindex(assignment, nOfRows, nOfColumns)
newAssignment = zeros(nOfRows, 1);
newAssignment(assignment) = (1:nOfColumns);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [newAssignment, newCost] = checksubtree(distMatrix, curCost, maxCost, nOfRows, nOfColumns)
if nOfRows > 1
newCost = maxCost;
newAssignment = [];
for n=1:nOfColumns
thisCost = distMatrix(1,n) + curCost;
if thisCost <= newCost
% recursively pass distMatrix except the current row and column
colIndex = [1:n-1,n+1:nOfColumns]';
[thisAssignment, thisCost] = checksubtree(distMatrix(2:nOfRows, colIndex), thisCost, newCost, nOfRows-1, nOfColumns-1);
if (thisCost <= newCost) && ~isempty(thisAssignment)
newAssignment = [n; colIndex(thisAssignment)];
newCost = thisCost;
end
end
end
else
[minDist, newAssignment] = min(distMatrix(1,:));
newCost = minDist + curCost;
if newCost > maxCost
newAssignment = [];
end
end