QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3598|回复: 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可以转化为二分图指派问题,但我还是有兴趣学下新知识。
    3 p: I  q+ z7 W$ ^8 _4 H/ v  ~TSP是个NP完全问题,如果可以转化为二分图指派问题,岂不是变成了多项式问题?这可以图灵奖的发现呀,所以5 A7 ?5 F1 l5 o7 Z0 `" P! v/ ^7 \& ~; \
    我不信。我学习完分枝限界法求解TSP问题后,百度了,发现有个“tsp转化为指派问题的解法.doc”,但是百度云上已删除5 q' Y2 W7 q0 I" D& Z5 p. n/ x* N
    ,找不到了,不知原因。
    - a) i8 v: y$ U$ M( O  N8 B8 Q! {我发现,指派问题有点象八皇后问题,于是又百度了八皇后问题。
    1 k+ P7 U& X  z. w# i* j% U5 L' Q1 V八皇后问题,我当年是用八重循环求解的,网上是用递归解法回溯法求解的,又一事前不知。1 @0 U/ K7 R. Z% v# n
    指派问题,匈牙利解法,看得不太明,好似没有代码的,百度上的PPT讲的行列式好似只能手工操作的。+ M) k/ Q3 l! y! q4 L! }
    虽然不信TSP可以化为指派问题,但学习下新知识也不错,只是要学习的知识太多,烦。
    3 Y4 k2 ^$ l- D- E7 Y: _# d6 Q, |' O% u" [9 j: u
    / l8 D1 C0 U" w. v. e
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    16

    主题

    12

    听众

    494

    积分

    升级  64.67%

  • TA的每日心情
    奋斗
    2016-11-4 09:23
  • 签到天数: 36 天

    [LV.5]常住居民I

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

    群组2016国赛备战群组

    写的完全是日记嘛 没看懂想问什么
    3 W1 s/ }! \6 g/ N( r/ l5 O, F3 i1 d
    回复

    使用道具 举报

    2983

    主题

    142

    听众

    9762

    积分

    升级  95.24%

  • TA的每日心情
    开心
    2017-1-9 14:34
  • 签到天数: 272 天

    [LV.8]以坛为家I

    自我介绍
    吃吃吃

    社区QQ达人

    群组乐考无忧

    群组2014国赛优秀论文解析

    群组2016美赛冲刺培训

    群组2016国赛优秀论文解析

    群组2016国赛备战群组

    TSP转化为指派问题的解法.doc (1.09 MB, 下载次数: 15)
    - \) c: C9 T1 o( y
    : ^, D4 H" F: Z5 U/ Q& \
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    下载看了,感到不知所云,文字也错乱难看的,求讲解。个人认为这是图论奖的发现。6 G4 m6 g& j4 [1 Z8 \
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    终于想通想透,TSP不可能转化为指派问题,就算可也必特例没普遍意义。问题是,指派问题本身是NP问题,为何会有匈牙利算法化为P问题,这才是值得研究之处,如同最短路径算法原本也是NP问题,但有迪杰斯特拉算法等化成P问题一样。这才是值得深入之处。8 Z* J7 a7 E/ F% o- Y
    ' o' W& t2 z: F7 J  N  p
    回复

    使用道具 举报

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01
  • 签到天数: 14 天

    [LV.3]偶尔看看II

    回复

    使用道具 举报

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01
  • 签到天数: 14 天

    [LV.3]偶尔看看II


    * [7 T, E2 Y$ \) o+ e3 @% j) A9 T" ?& b. x+ o

    1 {9 R  H4 P6 n0 x1 P7 Q, Y读完收获很大!
    . |8 C3 |4 p$ v. P
    回复

    使用道具 举报

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01
  • 签到天数: 14 天

    [LV.3]偶尔看看II

    八百标兵奔北坡 发表于 2016-5-26 15:35
    $ `  _! e5 C2 R$ f% y- f  Y4 R写的完全是日记嘛 没看懂想问什么

    * j$ _3 V) Q. P/ ?读完收获很大!! h0 v4 D7 A8 u" c  x9 z
    回复

    使用道具 举报

    3

    主题

    13

    听众

    901

    积分

    升级  75.25%

  • TA的每日心情
    开心
    2017-1-21 12:01
  • 签到天数: 14 天

    [LV.3]偶尔看看II

    吃苹果的梨 发表于 2016-5-26 16:13
    , Z3 Y. d- ^& O( g. G: x* i
    读完收获很大!
      F. a5 b2 h" g" S
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2025-7-25 12:22 , Processed in 1.433981 second(s), 108 queries .

    回顶部