匈牙利算法求解指派问题的python代码

以下是使用匈牙利算法求解指派问题的 Python 代码：

import numpy as np

def hungarian_algorithm(cost_matrix):
    # 转换为最大权完美匹配问题
    cost_matrix = np.max(cost_matrix) - cost_matrix
    
    # 初始化标记向量
    n = cost_matrix.shape[0]
    u = np.zeros(n)
    v = np.zeros(n)
    match = [-1] * n
    
    # 寻找增广路径
    for i in range(n):
        # 初始化辅助结构
        path = [-1] * n
        used = [False] * n
        cur = i
        
        while cur != -1:
            # 标记该点已使用
            used[cur] = True
            
            # 查找可行边
            j = -1
            for k in range(n):
                if not used[k] and cost_matrix[cur, k] == u[cur] + v[k]:
                    j = k
                    break
            
            if j != -1:
                # 更新路径
                path[j] = cur
                
                # 继续寻找增广路径
                cur = match[j]
            else:
                # 调整标记向量
                d = np.inf
                for k in range(n):
                    if used[k]:
                        for l in range(n):
                            if not used[l]:
                                d = min(d, u[k] + v[l] - cost_matrix[k, l])
                
                for k in range(n):
                    if used[k]:
                        u[k] -= d
                    if not used[k] and path[k] != -1:
                        v[k] += d
                    else:
                        v[k] = np.inf
                
                cur = path.index(-1)
        
        # 调整增广路上的匹配
        while cur != i:
            match[cur], match[path[cur]] = path[cur], cur
            cur = path[cur]
    
    # 计算最小权和
    cost = sum(cost_matrix[match[i], i] for i in range(n))
    
    return cost, match

其中，`cost_matrix` 是一个 $n \times n$ 的二维数组，表示指派问题的代价矩阵。函数返回值为一个二元组 `(cost, match)`，其中 `cost` 表示最小权和，`match` 是一个长度为 $n$ 的列表，表示每个任务指派给了哪个人（如果没有指派，则为 -1）。