数学建模社区-数学中国

标题: 关于指派问题的匈牙利算法 [打印本页]
作者: 释永思    时间: 2016-5-27 08:33
标题: 关于指派问题的匈牙利算法
关于指派问题的匈牙利算法
) K0 I' C* b9 g) R0 ?5 O6 L9 c* a/ \- V1 _# I
指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。4 D7 j8 n) U( q# j- B6 d
; d0 q9 ]3 B7 }. _$ U6 Y
作者: 吃苹果的梨    时间: 2016-5-27 09:20
效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。
/ O$ z  c6 i9 I" h) G$ U+ Q
作者: 释永思    时间: 2016-5-27 10:59
八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？
6 |8 k0 G! Q4 U# u
作者: Cassiel    时间: 2016-6-28 19:17
感谢群主。5 z' A9 c2 _, b, v; `




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5