数学建模社区-数学中国

标题: 关于TSP可以转化为二分图指派问题 [打印本页]
作者: 释永思    时间: 2016-5-26 15:25
标题: 关于TSP可以转化为二分图指派问题
虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。+ w' }) L  X3 |# Z9 e6 S
TSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以$ A6 ~1 F5 o" k
我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除
; S0 Z' Z+ }7 j: \1 Z，找不到了，不知原因。
3 \$ O, k, x) t* I我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。+ J& z" p3 b  T
八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。
* z- r* G$ Y; a  n指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。3 E% ?4 @- n% m
虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。/ f' v% u" W1 x* ?  j+ e
! s( F, C* z; h/ Q4 l3 F1 W

3 T( Y, B4 k' i' ~( G
作者: 八百标兵奔北坡    时间: 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么
7 B5 J/ ]4 W% o8 W5 y
作者: 吃苹果的梨    时间: 2016-5-26 16:13
TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15) 4 q7 Y8 E% W1 a5 d
/ {  M4 V( ], V% N
作者: 释永思    时间: 2016-5-26 16:47
下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。
* v! F+ P2 r- L4 V) z3 |8 Y
作者: 释永思    时间: 2016-5-26 16:48
个人认为这是图灵奖的发现
; J, q" Z8 d! K' n- j0 @) C
作者: 释永思    时间: 2016-5-27 08:30
终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。( T& }% w; c5 ]# d! l
1 w2 J3 L$ |3 \! G9 w
作者: 怀尔斯22    时间: 2016-5-29 14:11
读完收获很大！
+ u2 Y, H: h0 ~3 @3 r
作者: 怀尔斯22    时间: 2016-5-29 14:11
' f* X, q& `3 N3 a! h+ I

: d9 [6 E6 U0 z) K3 y. K+ M. N3 R, R& L2 X. z+ R
读完收获很大！7 m# F/ Y. i2 \9 J& ?# ]8 X0 Q' t3 M
作者: 怀尔斯22    时间: 2016-5-29 14:11
八百标兵奔北坡 发表于 2016-5-26 15:35 1 J8 G4 f. T9 \$ c1 e2 S) M! K
写的完全是日记嘛 没看懂想问什么
0 j0 m- F7 T; M$ g
读完收获很大！6 t* R( @  M, O0 @1 K; o: c& ?
作者: 怀尔斯22    时间: 2016-5-29 14:12
吃苹果的梨 发表于 2016-5-26 16:13
3 G8 O3 e2 [: ^( }( L0 \$ m" A7 R
读完收获很大！( F1 W6 V, V# j2 b/ o




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