[Python知识库]2021-08-09

2021/8/9(匈牙利算法)

指派问题：假设有三位工人A, B和C，需要分配他们每人完成一件工作；对于不同的工作他们索要不同的工钱，问题是要找到一套开销最小的指派方案，匈牙利算法可用于处理这类问题。
调用匈牙利算法可用api：scipy.optimize.linear_sum_assignment

#!/usr/bin/env python
from scipy.optimize import linear_sum_assignment
import numpy as np

cost =np.array([[4,1,3,2],[2,0,5,3],[3,2,2,1]])
row_ind,col_ind = linear_sum_assignment(cost)
print(row_ind)# 消费矩阵对应的行索引
print(col_ind)# 对应行索引的最优指派的列索引
print(cost[row_ind,col_ind])# 提取每个行索引的最优指派列索引所在的元素，形成数组
print(cost[row_ind,col_ind].sum())# 数组求和

运行结果

[0 1 2]
[3 1 2]
[2 0 2]
4```