数学建模社区-数学中国

标题: 关于TSP可以转化为二分图指派问题 [打印本页]
作者: 释永思    时间: 2016-5-26 15:25
标题: 关于TSP可以转化为二分图指派问题
虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。  d( i* S) d' q/ n' v
TSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以
  {. ^$ Y* b! I( r9 n我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除
- `- ^) E1 _" n，找不到了，不知原因。
4 a$ R* z* _; I. x3 ~, Q我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。
. k: G; f, C" o9 S. J! S八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。
$ B' ~/ S0 r( F3 ^9 ^/ r* A8 Y指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
5 P* |7 s* m7 H" v虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。: |7 D* |! [/ |& A4 y6 d
$ p4 W- ~; Z; l- F! K  a
( G7 E3 Z" N; {+ i+ n8 f
作者: 八百标兵奔北坡    时间: 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么
  }) D8 R# ]: n; T/ S1 k
作者: 吃苹果的梨    时间: 2016-5-26 16:13
TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15)
/ g) S5 P2 ~& Y3 Z+ N: L% I/ L) b2 g7 }5 M' ?9 L
作者: 释永思    时间: 2016-5-26 16:47
下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。) A( b+ O7 g; g' w/ W! @3 U& E! N
作者: 释永思    时间: 2016-5-26 16:48
个人认为这是图灵奖的发现
/ l7 F2 e# w1 K8 n7 I: v2 l3 w
作者: 释永思    时间: 2016-5-27 08:30
终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。$ r- P9 u" }& L  v; a  X  G, U& z& L
# v$ v5 x( r) v4 i# A+ z+ r
作者: 怀尔斯22    时间: 2016-5-29 14:11
读完收获很大！
; d2 E. z2 M! Q4 c1 h; h
作者: 怀尔斯22    时间: 2016-5-29 14:11

' [2 E+ i9 J. T4 v9 P: h8 c$ c* ~8 S9 A; F8 j# N! [9 ]

3 ~7 f, d& j: z5 Y0 T  o7 Q% _读完收获很大！
8 e2 w6 ^% ~! d
作者: 怀尔斯22    时间: 2016-5-29 14:11
八百标兵奔北坡 发表于 2016-5-26 15:35 0 c" r5 }( b2 A2 ]- x( S+ n- C
写的完全是日记嘛 没看懂想问什么
! _6 R# {2 t; z1 N  L+ |
读完收获很大！7 X$ g, P0 i' D9 Y5 C. i, P2 n+ [
作者: 怀尔斯22    时间: 2016-5-29 14:12
吃苹果的梨 发表于 2016-5-26 16:13
* D  T6 H3 G7 g( {
读完收获很大！
" B0 j, d% r$ T" Z; U9 a



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