Python解决指派问题（匈牙利算法）

您所在的位置：网站首页 › 求解指派问题的匈牙利算法 › Python解决指派问题（匈牙利算法）

Python解决指派问题（匈牙利算法）

2024-07-16 16:17| 来源: 网络整理| 查看: 265

指派问题也是0-1规划，线性规划用的也是scipy.optimize的库函数，查看scipy.optimize官网linear_sum_assignment。

示例：

开销矩阵 [ 4 1 3 2 0 5 3 2 2 ] \begin{bmatrix} 4 & 1 & 3\\ 2 & 0 & 5\\ 3 & 2 & 2 \end{bmatrix} ⎣⎡423102352⎦⎤ 选每行最小开销并求和，第一行[4 1 3]就选第二列的1，第二行[2 0 5]就选第一列的2，第三行[3 2 2]就选第三列的2，那么开销的和就是5。

上代码：

from scipy.optimize import linear_sum_assignment cost =np.array([[4,1,3],[2,0,5],[3,2,2]]) 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] [1 0 2] [1 2 2] 5

【本文地址】

Python解决指派问题（匈牙利算法）

Python解决指派问题（匈牙利算法）

今日新闻

推荐新闻