数学建模社区-数学中国
标题:
关于指派问题的匈牙利算法
[打印本页]
作者:
释永思
时间:
2016-5-27 08:33
标题:
关于指派问题的匈牙利算法
关于指派问题的匈牙利算法
! q4 t8 N; l2 `$ Y
% B. `, f% Q/ i$ k0 f/ I) `
指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。
4 [) K6 ]0 z8 x I0 z5 ?0 w
7 ~1 Q& O4 D: h6 {& E8 C9 a
作者:
吃苹果的梨
时间:
2016-5-27 09:20
效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。
I& g2 f/ s9 t) F
作者:
释永思
时间:
2016-5-27 10:59
八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？
: K$ S L& N u1 b
作者:
Cassiel
时间:
2016-6-28 19:17
感谢群主。
# u; k5 R# y+ D* k _% _0 z
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5