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

释永思

虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。
+ R- f& l" K- [8 a0 RTSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以
; i/ P* u4 w; U1 C' L+ K- {我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除
' B+ B( w% k) `4 H/ A+ C  W，找不到了，不知原因。
我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。
3 W; E. N2 f  _6 N. ~5 x八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。
" R) d, P8 }7 s指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
0 `$ t$ U; J: ]) z' ]虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。

  p+ w7 N& I  e4 F/ e

八百标兵奔北坡

写的完全是日记嘛 没看懂想问什么
0 I& l, s: u( O; p8 }$ u

吃苹果的梨

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

2016-5-26 16:13 上传

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

* l- x* \% x9 \# M

释永思

下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。
9 _, [1 N% d% B# m3 Z( {8 k! H

释永思

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

释永思

终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。
+ [$ ]1 V- [5 S) s) g; }
# z+ r4 Z  v: |& c) L

怀尔斯22

读完收获很大！
) q5 P& ?# E0 B, w, z' l

怀尔斯22

1 i9 `! t' D2 y+ e5 S
读完收获很大！
# j" V0 z/ v; _* U8 t

怀尔斯22

八百标兵奔北坡 发表于 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么

6 i- E8 n* h% I8 X8 D3 f& b读完收获很大！
3 ^/ D! p0 G+ X- }; q

怀尔斯22

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

& S5 L9 v+ H( k3 ]读完收获很大！