匈牙利算法的matlab代码实现

匈牙利算法是一种解决二分图最大匹配问题的算法。下面是匈牙利算法的MATLAB实现代码[^1]：

function [matching] = hungarian_algorithm(matrix)
    m = length(matrix);
    n = length(matrix(1,:));
    
    % 初始化标记数组
    marked_rows = zeros(1, m);
    marked_columns = zeros(1, n);
    
    % 在每一行中找到最小值并减去
    for i = 1:m
        min_value = min(matrix(i,:));
        matrix(i,:) = matrix(i,:) - min_value;
    end
    
    % 在每一列中找到最小值并减去
    for i = 1:n
        min_value = min(matrix(:,i));
        matrix(:,i) = matrix(:,i) - min_value;
    end
    
    % 标记数组初始化为0
    marked_rows = zeros(1, m);
    marked_columns = zeros(1, n);
    
    % 开始匈牙利算法
    matching = zeros(1, m);
    for i = 1:m
        while true
            % 找到一个未标记的0元素
            [row, column] = find(matrix == 0 & ~marked_rows' & ~marked_columns);
            
            if isempty(row)
                break;
            end
            
            % 标记行和列
            marked_rows(row(1)) = 1;
            marked_columns(column(1)) = 1;
            
            % 检查是否存在增广路径
            if find_augmenting_path(matrix, row(1), matching, marked_rows, marked_columns)
                break;
            end
            
            % 如果不存在增广路径，则取消标记
            marked_rows(row(1)) = 0;
            marked_columns(column(1)) = 0;
            
            % 将未标记的行和已标记的列中的元素减去1
            unmarked_rows = find(~marked_rows);
            marked_columns = marked_columns - 1;
            matrix(unmarked_rows, marked_columns == 0) = matrix(unmarked_rows, marked_columns == 0) - 1;
        end
    end
end

function [found] = find_augmenting_path(matrix, row, matching, marked_rows, marked_columns)
    n = length(matrix(1,:));
    
    for column = 1:n
        if matrix(row, column) == 0 && ~marked_columns(column)
            marked_columns(column) = 1;
            
            % 如果列未匹配，则找到增广路径
            if matching(column) == 0
                matching(column) = row;
                found = true;
                return;
            end
            
            % 否则，继续寻找增广路径
            next_row = matching(column);
            marked_rows(row) = 1;
            if find_augmenting_path(matrix, next_row, matching, marked_rows, marked_columns)
                matching(column) = row;
                found = true;
                return;
            end
        end
    end
    
    found = false;
end

这段代码实现了匈牙利算法，用于解决二分图最大匹配问题。它首先对输入的矩阵进行预处理，然后使用循环和递归的方式找到增广路径，直到无法找到更多的增广路径为止。最终返回一个匹配结果。