数学建模社区-数学中国

标题: 关于TSP可以转化为二分图指派问题 [打印本页]
作者: 释永思    时间: 2016-5-26 15:25
标题: 关于TSP可以转化为二分图指派问题
虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。7 [( x! \. ^: {* x2 K# o& y
TSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以  k0 W/ Z$ p6 q% ^" p
我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除* l. @) g1 U1 s/ t
，找不到了，不知原因。
8 F8 u. Q* k0 {/ m+ D我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。
% W' D  Z, D& t4 d* U5 W. v八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。, F6 g, q2 F  n$ I8 w1 N6 h* Q
指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
/ X; ~+ q/ w( C" t4 b虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。, q! q- b, d7 ]: m) P
- \# `$ ?# g9 c. d- X1 T! ?% A
/ F, t2 z& x0 a1 X: M7 ~- i$ o$ K
作者: 八百标兵奔北坡    时间: 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么0 j( d4 Z0 ?  `% q
作者: 吃苹果的梨    时间: 2016-5-26 16:13
TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15) & E) |4 k9 Y) S0 z

8 e% `" m5 i7 f  h3 G
作者: 释永思    时间: 2016-5-26 16:47
下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。( C% R' X, ?( K! w7 E( h
作者: 释永思    时间: 2016-5-26 16:48
个人认为这是图灵奖的发现: [, r* d& d2 U& C3 O( E' U
作者: 释永思    时间: 2016-5-27 08:30
终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。. V* T+ o5 L: @. t: f2 F
1 U* E- ~7 j' A- o. C
作者: 怀尔斯22    时间: 2016-5-29 14:11
读完收获很大！
$ I  h# z. y. z  D8 q% Y
作者: 怀尔斯22    时间: 2016-5-29 14:11
) B9 ~% m; D% O5 a' d8 D6 F
  d/ ^4 \: C: ?6 `5 A' _

0 Z) J7 D* F) r' v) N+ N" J读完收获很大！
. r* ]8 Y. B$ H( Q5 g
作者: 怀尔斯22    时间: 2016-5-29 14:11
八百标兵奔北坡 发表于 2016-5-26 15:35   z, Y( v' z- @4 j
写的完全是日记嘛 没看懂想问什么
! s9 }( Q! F" [+ m( f# R7 a; B: S
读完收获很大！
* D4 Q0 g# V7 D$ _7 H6 x
作者: 怀尔斯22    时间: 2016-5-29 14:12
吃苹果的梨 发表于 2016-5-26 16:13
4 g" u4 g2 n- M, P0 y
读完收获很大！7 Y3 O5 i- ?0 i2 H- f; b6 j$ Z




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