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

释永思

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

# e. u" {; f6 D; S/ k3 M% X  D指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。
* U! v! Y- _3 B5 ], i/ p
  X- k/ S, S5 Z- V

吃苹果的梨

效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。
0 C4 A" A: W* A# ~! t0 {+ h2 A

释永思

八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？
" x# |1 O6 I, A( v0 n: N2 O

Cassiel

感谢群主。
& a7 a5 m7 N9 B0 J4 w  x