快捷通道

QQ登录

只需要一步，快速开始

  注册地址  找回密码

数学建模社区-数学中国

留学>>
返回列表 发新帖
查看: 3606|回复: 9
打印 上一主题 下一主题

[问题求助] 关于TSP可以转化为二分图指派问题

[复制链接]
字体大小: 正常 放大
释永思        

23

主题

13

听众

146

积分

升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04

    • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    跳转到指定楼层
    1#
    发表于 2016-5-26 15:25 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    虽然我不信网友说的TSP可以转化为二分图指派问题，但我还是有兴趣学下新知识。( j- e6 M5 |6 |% D
    TSP是个NP完全问题，如果可以转化为二分图指派问题，岂不是变成了多项式问题？这可以图灵奖的发现呀，所以  A5 m7 h, T. @" s# y- Y
    我不信。我学习完分枝限界法求解TSP问题后，百度了，发现有个“tsp转化为指派问题的解法.doc”，但是百度云上已删除  a1 ?& V9 j4 d3 a' w
    ，找不到了，不知原因。
    8 Y& W& v6 e6 X0 K2 I/ l5 O" K0 d; g我发现，指派问题有点象八皇后问题，于是又百度了八皇后问题。
    1 w1 p2 B- X, }) ?八皇后问题，我当年是用八重循环求解的，网上是用递归解法回溯法求解的，又一事前不知。0 K8 |5 X5 W+ x6 o2 T. I( }
    指派问题，匈牙利解法，看得不太明，好似没有代码的，百度上的PPT讲的行列式好似只能手工操作的。
    8 h0 Y! H8 j0 n$ K: Z& T) H5 Q虽然不信TSP可以化为指派问题，但学习下新知识也不错，只是要学习的知识太多，烦。
    ' M1 T9 I  @3 K  ]+ n, P/ n9 G* O& h. p; ~: |9 `! `

    $ b5 ~9 d5 k  y$ H4 S" O
    zan
    匈牙利, 百度, 多项式, 行列式, 手工
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    相关帖子
    回复

    使用道具 举报

    八百标兵奔北坡        

    16

    主题

    12

    听众

    494

    积分

    升级  64.67%

  • TA的每日心情
    奋斗
    2016-11-4 09:23

    • 签到天数: 36 天

    [LV.5]常住居民I

    自我介绍
    是我 就是我 你们的英雄 小哪吒

    群组: 2016国赛备战群组
    2#
    发表于 2016-5-26 15:35 |只看该作者 |招呼Ta 关注Ta
    写的完全是日记嘛 没看懂想问什么9 @* x; q, @) D% v& ~+ z" }
    回复

    使用道具 举报

    吃苹果的梨        

    2983

    主题

    142

    听众

    9762

    积分

    升级  95.24%

  • TA的每日心情
    开心
    2017-1-9 14:34

    • 签到天数: 272 天

    [LV.8]以坛为家I

    自我介绍
    吃吃吃

    社区QQ达人

    群组: 乐考无忧

    群组: 2014国赛优秀论文解析

    群组: 2016美赛冲刺培训

    群组: 2016国赛优秀论文解析

    群组: 2016国赛备战群组
    3#
    发表于 2016-5-26 16:13 |只看该作者 |招呼Ta 关注Ta
    TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15) + _# @7 S0 H+ o( K4 @9 Y) K$ a" v8 z! g

    3 v+ y' ]# q9 k+ }
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04

    • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    4#
    发表于 2016-5-26 16:47 |只看该作者 |招呼Ta 关注Ta
    下载看了，感到不知所云，文字也错乱难看的，求讲解。个人认为这是图论奖的发现。! b4 a5 D: ]3 D: y1 j
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04

    • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    5#
    发表于 2016-5-26 16:48 |只看该作者 |招呼Ta 关注Ta
    个人认为这是图灵奖的发现
    ) D, n4 X1 O: X$ d! g
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04

    • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    6#
    发表于 2016-5-27 08:30 |只看该作者 |招呼Ta 关注Ta
    终于想通想透，TSP不可能转化为指派问题，就算可也必特例没普遍意义。问题是，指派问题本身是NP问题，为何会有匈牙利算法化为P问题，这才是值得研究之处，如同最短路径算法原本也是NP问题，但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。
    9 p. D9 M# ~1 P2 m7 v; d
    5 ~5 |. ~9 p: n" V0 L5 v  z+ R4 F2 X
    回复

    使用道具 举报

    怀尔斯22        

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01

    • 签到天数: 14 天

    [LV.3]偶尔看看II
    7#
    发表于 2016-5-29 14:11 |只看该作者 |招呼Ta 关注Ta
    读完收获很大！) n' L- N- e9 ?- a2 V2 H3 S
    回复

    使用道具 举报

    怀尔斯22        

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01

    • 签到天数: 14 天

    [LV.3]偶尔看看II
    8#
    发表于 2016-5-29 14:11 |只看该作者 |招呼Ta 关注Ta

    . E+ R$ z2 t* |* l# o5 x/ s  Y2 \. N) O9 W6 F0 T  f

    6 t7 W+ W3 e: O" p7 H" Y4 Z& v  D读完收获很大！  ]7 N- O1 U" t2 f
    回复

    使用道具 举报

    怀尔斯22        

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01

    • 签到天数: 14 天

    [LV.3]偶尔看看II
    9#
    发表于 2016-5-29 14:11 |只看该作者 |招呼Ta 关注Ta
    八百标兵奔北坡 发表于 2016-5-26 15:35
    3 X% e/ k4 n2 X& j4 M. V: ]写的完全是日记嘛 没看懂想问什么
    & n5 G  e; X  w
    读完收获很大！& D9 z) L  U  }: X8 I+ Q) {
    回复

    使用道具 举报

    怀尔斯22        

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01

    • 签到天数: 14 天

    [LV.3]偶尔看看II
    10#
    发表于 2016-5-29 14:12 |只看该作者 |招呼Ta 关注Ta
    吃苹果的梨 发表于 2016-5-26 16:13

    * `) ?( V+ v& z9 U: O$ N读完收获很大！
    ; f$ U( ^7 h2 E! h/ m/ p
    回复

    使用道具 举报

    返回列表 发新帖
    高级模式
    B Color Image Link Quote Code Smilies
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩

    • 电话咨询

    • 04714969085

    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问：王兆丰

    GMT+8, 2025-7-26 14:53 , Processed in 0.908910 second(s), 108 queries .

    回顶部