匈牙利算法指派问题的matlab代码

匈牙利算法（也称为Kuhn-Munkres算法）是用于求解二分图最大匹配问题的一种经典算法。它的核心思想是通过寻找增广路径的方式不断扩大匹配，直到找不到增广路径为止。

下面是使用Matlab实现匈牙利算法解决指派问题的代码：

function [assignment, cost] = hungarianAlgorithm(costMatrix)
    n = size(costMatrix, 1);
    
    % 转换为最大权重匹配问题
    costMatrix = -costMatrix;
    
    % 初始化标记矩阵
    rowCover = zeros(1, n);
    colCover = zeros(1, n);
    
    % 计算初始标记
    for i = 1:n
        minVal = min(costMatrix(i, :));
        costMatrix(i, :) = costMatrix(i, :) - minVal;
        rowCover(i) = rowCover(i) + minVal;
    end
    
    % 开始增广路径寻找
    for k = 1:n
        while true
            % 初始化
            zeroM = find(rowCover == 0);  % 未标记的行
            zeroN = find(colCover == 0);  % 未标记的列
            
            % 判断结束条件
            if length(zeroN) >= n
                break;
            end
            
            % 寻找增广路径
            row = zeroM(1);
            stack = [row];
            markedM = ones(1, n);
            markedN = zeros(1, n);
            foundAugPath = false;
            
            while ~foundAugPath && ~isempty(stack)
                i = stack(end);
                col = find(costMatrix(i, zeroN) == 0, 1);
                
                if isempty(col)
                    stack(end) = [];
                else
                    j = zeroN(col);
                    
                    if markedN(j) == 1
                        stack(end) = [];
                    else
                        markedN(j) = 1;
                        row = find(costMatrix(:, j) == 0);
                        
                        if markedM(row) == 0
                            stack = [stack, row];
                        else
                            markedM(row) = 1;
                            zIdx = find(costMatrix(row, :) == 0);
                            stack = [stack, row, zeroN(zIdx)];
                        end
                        
                        if isempty(row)
                            foundAugPath = true;
                        end
                    end
                end
            end
            
            % 更新标记
            if foundAugPath
                for idx = 1:length(stack)
                    if mod(idx, 2) == 1
                        costMatrix(stack(idx), stack(idx+1)) = 1;
                    else
                        costMatrix(stack(idx), stack(idx-1)) = 0;
                    end
                end
                
                rowCover(markedM == 0) = rowCover(markedM == 0) + 1;
                colCover(markedN == 1) = colCover(markedN == 1) + 1;
            else
                minVal = min(costMatrix(zeroM, zeroN), [], 'all');
                costMatrix(zeroM, zeroN) = costMatrix(zeroM, zeroN) - minVal;
                rowCover(zeroM) = rowCover(zeroM) + minVal;
                colCover(zeroN) = colCover(zeroN) - minVal;
            end
        end
    end
    
    % 获取指派结果和总成本
    assignment = [];
    for i = 1:n
        col = find(costMatrix(i, :) == 1, 1);
        if ~isempty(col)
            assignment = [assignment; [i, col]];
        end
    end
    cost = -sum(costMatrix(assignment(:, 1), assignment(:, 2)));
end

使用该代码可以求解指派问题，其中输入参数`costMatrix`是一个`n×n`的二维矩阵，表示指派问题的成本矩阵。返回值`assignment`是一个`m×2`的二维矩阵，每一行表示一个指派结果，第一列为行索引，第二列为列索引。返回值`cost`为指派的总成本。

希望以上内容能帮助到您！