《算法的乐趣》第二十二节

本节给出Kuhn-Munkres算法的实现代码说明：Kuhn_Munkres_Match()函数依次完成顶标初始化、匈牙利算法求完美匹配、顶标调整三个步骤……

本节给出Kuhn-Munkres算法的实现代码说明：Kuhn_Munkres_Match()函数依次完成顶标初始化、匈牙利算法求完美匹配、顶标调整三个步骤；FindAugmentPath()与匈牙利算法版本类似，改用sub_map并记录x_on_path标识；另有ResetMatchPath()和ClearOnPathSign()负责清除临时路径与集合标识。按表7-1数据调用该函数得到最佳匹配：工人1至5分别对应工作3、1、2、5、4，权重和为14；最大权匹配可能不唯一，算法只能求出其中一个。

总结部分指出匹配问题的现实应用：美国1950年代启动“国家住院医生匹配项目”（NRMP）解决实习机会过早配对的问题，罗思1984年发现其算法与Gale-Shapley原理类似，1997年NRMP采纳他设计的新算法，每年为两万多医生匹配岗位。罗思与沙普利因此获2012年诺贝尔经济学奖。Gale-Shapley算法中，主动“求婚”一方总能获得最佳的稳定匹配，被动方则得到最差的稳定匹配，主动权决定结果优劣。