数学建模社区-数学中国
标题:
关于指派问题的匈牙利算法
[打印本页]
作者:
释永思
时间:
2016-5-27 08:33
标题:
关于指派问题的匈牙利算法
关于指派问题的匈牙利算法
/ \$ Q. c0 [+ W% [( N' [
( ]) R" i' Y. f$ z% U
指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。
* W T `* a# H! v5 R2 i3 l- E
+ _% S5 h9 ?/ K i, W
作者:
吃苹果的梨
时间:
2016-5-27 09:20
效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。
# k( l& V! M% O! h" W
作者:
释永思
时间:
2016-5-27 10:59
八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？
8 o/ J1 P3 H G% n( D, @
作者:
Cassiel
时间:
2016-6-28 19:17
感谢群主。
& K1 t7 o& [6 Q L- K
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5