数学建模社区-数学中国

标题: 关于TSP可以转化为二分图指派问题 [打印本页]
作者: 释永思    时间: 2016-5-26 15:25
标题: 关于TSP可以转化为二分图指派问题
虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。* z1 ]3 T  m& D; C) L' F; \
TSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以
1 Z- Y- z! H! u9 O: C我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除
, A" |; o4 f  r5 A，找不到了，不知原因。
1 e' {- e% S% D/ {* d7 n; S. t9 {我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。
! b, {$ L; m# E0 e6 S2 R1 S9 w八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。. m! u3 C1 q' F" f! F+ _) @
指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
# f1 b+ d1 ?: ?+ q" A% k  m2 ?; ^9 O虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。) I' n+ b. _' ?# N

9 O" O8 u* B3 n$ {; @
6 t& C$ M$ b  d% C5 T) @2 G
作者: 八百标兵奔北坡    时间: 2016-5-26 15:35
写的完全是日记嘛 没看懂想问什么
! {. J3 F/ a% z) m- R
作者: 吃苹果的梨    时间: 2016-5-26 16:13
TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15)
! X8 b5 o! S: S! T2 n3 Q; b2 {' B/ m  a
作者: 释永思    时间: 2016-5-26 16:47
下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。
% [6 _4 H3 V7 ~& d
作者: 释永思    时间: 2016-5-26 16:48
个人认为这是图灵奖的发现8 m4 R$ c2 Z6 O% Z5 `- F( i
作者: 释永思    时间: 2016-5-27 08:30
终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。
' B% i8 B- H( s
2 p% f( W8 W; B  Y+ E
作者: 怀尔斯22    时间: 2016-5-29 14:11
读完收获很大！9 c+ i- J" H" r* A: {. j
作者: 怀尔斯22    时间: 2016-5-29 14:11

% a  o0 \# s% p& V$ ^- j+ }; n$ `9 N* Y1 V3 n
$ _/ z& g) m& c; v# |
读完收获很大！
$ c( v4 J8 o6 \1 K# R$ J) |+ ]
作者: 怀尔斯22    时间: 2016-5-29 14:11
八百标兵奔北坡 发表于 2016-5-26 15:35
: O7 {; j8 B* [. A* c写的完全是日记嘛 没看懂想问什么
: x/ P/ O+ ]/ j! c
读完收获很大！( n$ E4 q  O8 `! D
作者: 怀尔斯22    时间: 2016-5-29 14:12
吃苹果的梨 发表于 2016-5-26 16:13
" B2 z& A  J- T+ K
读完收获很大！2 N; x) _0 ~9 D




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