匈牙利算法指派问题 怎么适用长方形方阵 python代码

匈牙利算法，也称为Munkres算法，是一种经典的线性规划方法，用于解决分配或匹配问题，特别适用于求解最小成本的配对问题。在长方形矩阵中，它常被用来寻找最佳的工人任务分配，使得每项任务的成本（矩阵中的值）和每个工人的效率（通常为1/成本）之积最小化。

在一个简单的应用场景中，你可以有一个二维数组，表示每个任务的优先级（值越小代表优先级越高），以及一组工人的能力（即他们完成相应任务的能力值）。算法的目标是找到一个最优分配，使得所有工人都尽可能地完成任务，同时总成本最低。

以下是使用Python实现的简化版匈牙利算法示例：

from scipy.optimize import linear_sum_assignment

def hungarian_algorithm(cost_matrix):
    # 使用scipy库中的linear_sum_assignment函数，该函数实现了匈牙利算法
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    
    # 返回最优的行索引(row_ind)和列索引(col_ind)，这对应于最小成本的配对
    optimal_assignments = [(row_ind[i], col_ind[i]) for i in range(len(row_ind))]
    
    return optimal_assignments

# 示例矩阵，假设0是最优匹配
cost_matrix = [[8, 2, 6],
               [5, 4, 9],
               [7, 1, 3]]

optimal_pairs = hungarian_algorithm(cost_matrix)
print("Optimal assignments:", optimal_pairs)