关于TSP可以转化为二分图指派问题

释永思

虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。
# {+ R" |" n- m- l* CTSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以
4 ^9 I2 I5 H% ~我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除
，找不到了，不知原因。
我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。
) ?2 m9 n1 }6 N- I  Y八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。
3 ~/ f' D( F8 m指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
) |0 _+ h+ d0 b( V7 o虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。
% X+ \+ {$ Y/ C0 G+ b
1 J' Y* {; I$ \; R, [$ I

八百标兵奔北坡

写的完全是日记嘛 没看懂想问什么

吃苹果的梨

TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15)

2016-5-26 16:13 上传

点击文件名下载附件
下载积分: 体力 -2 点

3 ~6 W6 C2 _/ k2 V2 B  j
! R3 P( k) R" j9 a3 [& f: ]

释永思

下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。

释永思

个人认为这是图灵奖的发现

释永思

终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。
' ?' A* ^7 V/ m$ x% M% K/ T. ?* C

怀尔斯22

读完收获很大！
1 {7 l7 g5 N) l. r0 `# H% T' N3 t) G

怀尔斯22

0 w9 j' H. z/ [! s' @

. }  n/ s/ i, ?读完收获很大！
4 x8 T0 P( r; Z8 ~7 P- V/ l% K; S4 t

怀尔斯22

八百标兵奔北坡 发表于 2016-5-26 15:35
, Z0 T5 \" P" B' ]) n% q3 c写的完全是日记嘛 没看懂想问什么

. Q: G0 L# J% H0 {读完收获很大！

怀尔斯22

吃苹果的梨 发表于 2016-5-26 16:13

8 l6 r" r5 @+ l8 i读完收获很大！
. a5 H% e" E: {9 a( S+ L