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

梦里梦外; 2022-06-01 08:43 158阅读 0赞

前言：最近在备战数模，看到了指派问题，饶有兴趣，百度上找了很多关于指派问题的解法，很明显用的是匈牙利算法，手工的计算，各种各种的博客都很详尽，大概都了解了具体原理（不懂的人可以自行百度），但是基本找不到算法实现，有了也很难去验证对不对。可能为了省时间吧（不想重新造轮子，懒），就想找找python有没有什么库函数可以实现，找了很多博客什么的，还是找不到。想着指派问题也是0-1规划，线性规划用的也是scipy.optimize的库函数，一气之下，直接去翻scipy.optimize的官网。还是官网无敌啊。废话不多说了，先看个示例的开销矩阵：

![SouthEast][]

那么肉眼看的话就很简单了，第一行\[4 1 3\]就选第二列的1，第二行\[2 0 5\]就选第一列的2，第三行\[3 2 2\]就选第三列的2，那么开销的和就是5。那么用python解的话，用到scipy.optimize.linear\_sum\_assignment(cost\_matrix)这个函数了。直接贴代码：

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

索引从0开始就不多说了，还是多嘴一句，官网才是无敌的！那么就贴下这个函数的官网吧 [https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear\_sum\_assignment.html\#scipy.optimize.linear\_sum\_assignment][https_docs.scipy.org_doc_scipy_reference_generated_scipy.optimize.linear_sum_assignment.html_scipy.optimize.linear_sum_assignment]

以上。

[SouthEast]: /images/20220601/541ef805d3e3485b851828f38e6c31b0.png
[https_docs.scipy.org_doc_scipy_reference_generated_scipy.optimize.linear_sum_assignment.html_scipy.optimize.linear_sum_assignment]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html#scipy.optimize.linear_sum_assignment