释永思 发表于 2016-5-27 08:33

关于指派问题的匈牙利算法

关于指派问题的匈牙利算法

指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。

吃苹果的梨 发表于 2016-5-27 09:20

效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。

释永思 发表于 2016-5-27 10:59

八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？

Cassiel 发表于 2016-6-28 19:17

感谢群主。
页: [1]
查看完整版本: 关于指派问题的匈牙利算法