数学建模社区-数学中国

标题: 关于指派问题的匈牙利算法 [打印本页]
作者: 释永思    时间: 2016-5-27 08:33
标题: 关于指派问题的匈牙利算法
关于指派问题的匈牙利算法
  g' g3 Z  x1 J. T3 z
6 c7 P0 n& g' g! t" ^1 E8 Z指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。$ f) N: @) R: {% l1 s4 N! I& E, v4 D. d
6 _" s2 ^4 V. T- z
作者: 吃苹果的梨    时间: 2016-5-27 09:20
效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。  r6 I# j7 ~1 W! N8 J$ T! e
作者: 释永思    时间: 2016-5-27 10:59
八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？! T8 w( [( C7 @, \8 O
作者: Cassiel    时间: 2016-6-28 19:17
感谢群主。
/ p, x6 Z8 t8 i, `1 m! S/ `



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