数学建模社区-数学中国

标题: 关于TSP可以转化为二分图指派问题 [打印本页]
作者: 释永思    时间: 2016-5-26 15:25
标题: 关于TSP可以转化为二分图指派问题
虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。1 ?8 L3 Y0 o. C8 V0 ?6 C- N
TSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以2 n+ H: T( g" s4 A0 ~# A0 p# D% T
我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除3 D4 C* j0 ]* i0 r
，找不到了，不知原因。; _, X" W: t. d
我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。* N( B. E4 @3 }$ k2 J2 E% s7 H
八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。
; W2 Z0 |  P% Z  r2 I7 B1 k指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
/ T2 k/ P2 X7 G虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。, i; k' K9 y0 R2 i; c+ v: }

) ]9 k  ?3 s3 O
* F. T5 m: s4 b6 o! |# }4 ~- o
作者: 八百标兵奔北坡    时间: 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么. X+ y; @8 ~( j2 k: S! k1 y; R
作者: 吃苹果的梨    时间: 2016-5-26 16:13
TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15)
+ E! q" F& [# l! G7 D
# g, @; W" ?% Q. d8 c% e
作者: 释永思    时间: 2016-5-26 16:47
下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。6 m+ R, V  b9 `0 Q" G
作者: 释永思    时间: 2016-5-26 16:48
个人认为这是图灵奖的发现
: H( Z- t2 Q' d( _6 f
作者: 释永思    时间: 2016-5-27 08:30
终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。
/ }- O) Q# Y7 Y( C' [6 ^* U
4 H: z* K# E/ z6 Q7 V
作者: 怀尔斯22    时间: 2016-5-29 14:11
读完收获很大！0 `$ y; {- x- d! C
作者: 怀尔斯22    时间: 2016-5-29 14:11

) K1 d4 G# i3 m' ~9 \) p& e$ ~* u2 C" s4 J( g' u8 Q* M$ h
$ f+ j/ h4 d3 k3 G
读完收获很大！
) ]) H/ F$ z+ G# B' v' u3 R
作者: 怀尔斯22    时间: 2016-5-29 14:11
八百标兵奔北坡 发表于 2016-5-26 15:35 : o$ ?$ U' w! z5 s/ P! m+ f
写的完全是日记嘛 没看懂想问什么
- ?( d# G4 q1 [5 e/ K, j& }
读完收获很大！' _* a) ?- l0 F& v. N  z" e2 x4 u
作者: 怀尔斯22    时间: 2016-5-29 14:12
吃苹果的梨 发表于 2016-5-26 16:13

& @! n8 x$ @8 Q# k/ u1 A' t, z读完收获很大！/ @" \" g6 O: h/ X" N% |+ g




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