数学建模社区-数学中国

标题: 关于TSP可以转化为二分图指派问题 [打印本页]
作者: 释永思    时间: 2016-5-26 15:25
标题: 关于TSP可以转化为二分图指派问题
虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。
' G: z: n! v7 h* OTSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以5 O# Y6 V  s( S7 o9 G
我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除
; z2 L5 {8 k# f- L，找不到了，不知原因。
1 U, a* S' k, H% Y! Z& Y' f5 h我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。5 D9 c( e7 Q9 G; h( y
八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。# u' F9 y: _4 m# k- r4 J) k  v5 `9 s
指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。" s! s+ |6 H  e
虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。5 s  T  b& k& c5 J

7 ]& C  n' c) Z: s+ Y/ M+ A+ d
& t  i+ g8 [' ]/ C3 u4 I2 p
作者: 八百标兵奔北坡    时间: 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么! o! r* q6 ?. F- m  q/ E
作者: 吃苹果的梨    时间: 2016-5-26 16:13
TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15) 8 _5 K4 f! Y5 U1 \7 Z
/ }% e3 Y& b% |" b
作者: 释永思    时间: 2016-5-26 16:47
下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。
3 I% W" e* R5 E9 Q0 F
作者: 释永思    时间: 2016-5-26 16:48
个人认为这是图灵奖的发现
. b( Y3 c2 b# m& w6 T1 j
作者: 释永思    时间: 2016-5-27 08:30
终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。
+ b( c0 O( U; T# x1 y: _0 g; |  b  I1 W' b$ w  X
作者: 怀尔斯22    时间: 2016-5-29 14:11
读完收获很大！
6 b% t6 k9 W; ^7 m$ J( q
作者: 怀尔斯22    时间: 2016-5-29 14:11
* j" t8 x' `5 P) i* U8 Q
( Y( o1 h9 l$ o: \& h

7 f. ~9 I5 E8 u: m+ p读完收获很大！( K" S, _& r; @) S; @/ A
作者: 怀尔斯22    时间: 2016-5-29 14:11
八百标兵奔北坡 发表于 2016-5-26 15:35
6 [2 V' J# G7 P& w- A写的完全是日记嘛 没看懂想问什么

! p7 o4 [% G) R8 W$ J% {读完收获很大！* _2 T$ z+ f2 C* s! Q
作者: 怀尔斯22    时间: 2016-5-29 14:12
吃苹果的梨 发表于 2016-5-26 16:13
' S: t0 y( B) [/ A
读完收获很大！" ^; J. r, U+ Y1 _




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