带权二分图的最佳匹配(KM算法)

关注
带权二分图的最佳匹配(KM算法)www.shan-machinery.com

该算法的思路写得太多了,懒得复述,直接贴链接了: https://blog.csdn.net/x_y_q_/article/details/51927054

重点是心得体会:

1.图论算法的精髓在于其本身是抽象的数学模型,通过模型转化可以解决众多表象不一的问题,帮助我们发现问题的本质;

2.二分图是图论中不可分割的一部分,在于其通过对一般图增加限制得到了很多优美的特性,也衍生出一堆复杂度很好看的算法,这种进一步简化模型的思路值得寻味;

3.说回二分图匹配问题,二分图最大匹配算是搜索问题,增广路经为搜索指引了方向,降低了搜索成本;

4.而二分图最佳匹配问题的KM(Kuhn-Munkres )算法就归结到贪心上了,而且可以归结为一种很好的贪心思想解决问题的范式了。贪心算法最难处在于如何从局部最优上升到全局最优。KM算法指了一条明路。在问题有诸多限制条件时,比如二分图最佳匹配问题,限制条件是边不交叉(边上顶点不重复)。KM算法初始先不考虑这一层限制,找到全局最优解,然后逐步增加限制,以最小代价的方式向目标约束靠近,最后得到满足约束条件的最优解;

5.KM算法也算一种逆向思维,贪心可以每次选最多,最后得到总数最多;贪心也可以一开始任性地拿到全部,然后一次次花费最小代价得到最优。

6.最后还是需要面对为何最优的问题,KM算法正好在逐步约束过程中,步步为营,保证每一步都最优,所以最后也是最优。

7.补充:https://blog.csdn.net/u014754127/article/details/78086014 匈牙利算法,另一种解释该算法的逻辑,我认为是殊途同归的,不过在算法平均效率上有提升,值得称道,充分利用一些特性让算法直接结束迭代。

https://www.shan-machinery.com