数学建模社区-数学中国
标题:
关于指派问题的匈牙利算法
[打印本页]
作者:
释永思
时间:
2016-5-27 08:33
标题:
关于指派问题的匈牙利算法
关于指派问题的匈牙利算法
5 V) T9 G% z# v/ D% [
) P0 a" N* _ n1 Z/ S
指派问题，我总觉得和八皇后问题相似，但八皇后问题要用回溯法递归算法，但是指派问题居然有个匈牙利算法，把NP问题简化成了P问题，我一直不知其原理，想不明白其原理，不知何解。
% O. i1 `7 Y) ]: L) O5 F9 U" D5 i
% l; D+ } J2 v
作者:
吃苹果的梨
时间:
2016-5-27 09:20
效率矩阵乘以（-1），变换成求最小问题。再应用同行（或列）加一个常数，不改变指派问题最优解的定理，将效率矩阵变成非负的，再应用匈牙利算法求解。
( L9 M8 p. V& \4 y8 _- }
作者:
释永思
时间:
2016-5-27 10:59
八皇后问题可以用此匈牙利算法吗，为什么指派问题可以八皇后问题不可以？
7 C! A6 ~: f$ d" e& e
作者:
Cassiel
时间:
2016-6-28 19:17
感谢群主。
* ?+ a& C) r1 \* c
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5