上传者: 18822147
|
上传时间: 2021-11-24 17:25:13
|
文件大小: 90KB
|
文件类型: -
这种问题被称为带权二分图的最优匹配问题,可由KM算法解决。
比如上图,A做工作a的效率为3,做工作c的效率为4......以此类推。
不了解KM算法的人如何解决这个问题?我们只需要用匈牙利算法找到所有的最大匹配,比较每个最大匹配的权重,再选出最大权重的最优匹配即可。这不失为一个解决方案,但是,如果公司员工的数量越来越多,此种算法的实行难度也就越来越大,我们必须另辟蹊径:KM算法。