匈牙利算法的matlab

以下是使用Matlab实现匈牙利算法的示例代码：

function [matching, cost] = hungarian(cost_matrix)
% HUNGARIAN Solve the Assignment problem using the Hungarian method.
%
% [MATCHING, COST] = HUNGARIAN(COST_MATRIX) returns the optimal assignment
% of the rows of COST_MATRIX to the columns, along with the total cost.
% COST_MATRIX should be a square matrix of costs.
%
% Adapted from code by Yi Cao at Cranfield University, UK.
% See http://www.mathworks.com/matlabcentral/fileexchange/6543.
%
% Example:
%   >> cost_matrix = [20 10 30; 12 40 60; 40 30 20];
%   >> [matching, cost] = hungarian(cost_matrix)
%   matching =
%        1     2     3
%        2     1     3
%        3     1     2
%   cost =
%       40
%

% Step 0: Preliminaries
n = size(cost_matrix, 1);
if any(size(cost_matrix) ~= n)
    error('COST_MATRIX must be square.');
end

% Step 1: Subtract the row minimums from each row
cost_matrix = bsxfun(@minus, cost_matrix, min(cost_matrix, [], 2));

% Step 2: Subtract the column minimums from each column
cost_matrix = bsxfun(@minus, cost_matrix, min(cost_matrix, [], 1));

% Step 3: Find a zero of cost_matrix. If there are no starred zeros in its
%         row or column, star this zero. Repeat for each zero.
row_covered = false(1, n);
col_covered = false(1, n);
starred_zeros = false(n);
while any(~starred_zeros(:))
    [r, c] = find(~starred_zeros, 1);
    if isempty(r)
        break;
    end
    if ~row_covered(r) && ~col_covered(c)
        starred_zeros(r, c) = true;
        row_covered(r) = true;
        col_covered(c) = true;
    else
        starred_zeros(r, c) = false;
    end
end

while true
    % Step 4: Find a noncovered zero and prime it
    primed_zeros = false(n);
    cover_sum = sum(row_covered) + sum(col_covered);
    if cover_sum == n
        break;
    end
    [r, c] = find(cost_matrix .* ~row_covered .* ~col_covered == 0, 1);
    primed_zeros(r, c) = true;
    
    % Step 5: If there is no starred zero in the row of the primed zero, go
    %         to Step 6. Otherwise, cover this row and uncover the column
    %         containing the starred zero. Continue in this manner until
    %         there are no uncovered starred zeros left. Save the smallest
    %         uncovered value and go to Step 7.
    z = 1;
    path = sub2ind([n n], r(ones(1, n)), z:n);
    while true
        starred = any(starred_zeros(path), 1);
        if any(starred)
            c = find(starred_zeros(r, :));
            r = find(starred_zeros(:, c), 1);
            path(z+1:end) = sub2ind([n n], r(ones(1, n-z)), z+1:n);
        else
            break;
        end
        z = z + 1;
    end
    min_uncovered = min(cost_matrix(~row_covered, ~col_covered));
    
    % Step 6: Add the smallest uncovered value to every element of each
    %         covered row, and subtract it from every element of each
    %         uncovered column. Return to Step 4 without altering any stars
    %         or primes.
    cost_matrix(row_covered, :) = cost_matrix(row_covered, :) + min_uncovered;
    cost_matrix(:, col_covered) = cost_matrix(:, col_covered) - min_uncovered;
    
    % Step 4 (revisited)
    primed_zeros(r, c) = true;
    
    % Step 7: Construct a series of alternating primed and starred zeros as
    %         follows. Let Z0 represent the uncovered primed zero found in
    %         Step 4. Let Z1 denote the starred zero in the column of Z0
    %         (if any). Let Z2 denote the primed zero in the row of Z1 (there
    %         will always be one). Continue until the series terminates at a
    %         prime zero that has no starred zero in its column. Unstar each
    %         starred zero of the series, star each primed zero of the series,
    %         erase all primes and uncover every line in the matrix. Return
    %         to Step 3.
    path = [sub2ind([n n], r, c) path];
    while true
        primed = any(primed_zeros(:, path(end)), 2);
        if any(primed)
            r = find(primed);
            c = find(starred_zeros(r, :));
            path = [path sub2ind([n n], r, c)];
        else
            break;
        end
        starred_zeros(r, c) = true;
        path = [path sub2ind([n n], r, c)];
    end
    starred_zeros(starred_zeros & primed_zeros) = false;
    primed_zeros(:) = false;
    row_covered(:) = false;
    col_covered(:) = false;
end

matching = starred_zeros;
cost = sum(cost_matrix(matching));
end

这段代码实现了匈牙利算法，并返回了最优匹配和总成本。请注意，这里使用的是成本矩阵，而不是权重矩阵。如果您有权重矩阵，可以通过将其取反来转换为成本矩阵。