matlab 实现 匈牙利算法

匈牙利算法是一种用于求解最大权匹配问题的算法，它可以在多项式时间内求解。下面是 Matlab 实现匈牙利算法的基本步骤：

1. 构造二分图并将其表示为邻接矩阵形式；
2. 从左侧节点集合开始，依次遍历每一个节点，并进行增广路搜索；
3. 在每次增广路搜索中，首先从当前节点开始寻找未匹配的右侧节点，并将其加入交替路径中；
4. 如果找到了未匹配的右侧节点，则匹配该节点并返回上一层递归；
5. 如果没有找到未匹配的右侧节点，则继续向下一层递归；
6. 重复以上步骤，直到所有左侧节点均被匹配为止。

以下是一个简单的 Matlab 实现：

function [matching, cost] = hungarian_algorithm(cost_matrix)
% cost_matrix: 邻接矩阵
% matching: 匹配结果，每个元素表示对应节点所匹配的节点编号
% cost: 匹配权值之和

n = size(cost_matrix, 1);
m = size(cost_matrix, 2);
matching = zeros(1, n);
cost = 0;

for i = 1:n
    label = zeros(1, n);
    slack = Inf(1, n);
    slack_node = zeros(1, n);
    vis_x = zeros(1, n);
    vis_y = zeros(1, m);
    
    label(i) = 1;
    while true
        min_slack = Inf;
        for j = 1:m
            if ~vis_y(j)
                min_slack = min(min_slack, slack(j));
            end
        end
        for j = 1:n
            if vis_x(j)
                continue;
            end
            if label(j) == 1
                slack(j) = min(slack(j), min_slack);
            end
            if slack(j) == min_slack
                slack_node(j) = i;
                if matching(j) == 0
                    augment_path(j, matching, vis_x, vis_y, label);
                    return;
                else
                    vis_y(matching(j)) = true;
                    augment_path(matching(j), matching, vis_x, vis_y, label);
                    return;
                end
            end
        end
    end
end

function augment_path(u, matching, vis_x, vis_y, label)
    vis_x(u) = true;
    for v = 1:length(matching)
        if vis_y(v)
            continue;
        end
        t = cost_matrix(u, v) - label(u) - label(v);
        if t == 0
            vis_y(v) = true;
            if matching(v) == 0 || augment_path(matching(v), matching, vis_x, vis_y, label)
                matching(v) = u;
                return;
            end
        elseif slack(v) > t
            slack(v) = t;
            slack_node(v) = u;
        end
    end
end

for i = 1:length(matching)
    cost = cost + cost_matrix(matching(i), i);
end

end