开启辅助访问勋章商城切换到宽版

o(￣ヘ￣o＃) 任务菌(`へ´*)ノ懒人通道_(:3」∠)_签到领奖官方微博紧急反馈中心

有爱，有技术，有你^_^)y

快捷导航

技术宅社区 | Z站有爱，有技术，有你 ^_^)y»论坛 › 技术区 › 地下研究所 › 数学研究室 › 旅行商问题的求解

发新帖

查看: 571|回复: 4

收起左侧

[学术研究] 旅行商问题的求解

该用户从未签到

258 主题	314 好友	3万积分

积分: 35715

发表于 2013-8-10 15:00:02 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

x

本帖最后由轻舟过于 2013-8-10 15:00 编辑

最近在上Coursera的公开课组合优化，其中的一个作业就是编程求解旅行商问题（TSP），于是编程解决之，顺便把优化过程制作成了一个GIF动画

旅行商问题就是求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本（也就是整个路程的距离）。目前旅行商问题的精确求解还没有高效的算法，不过如果只是找一个比较优的解得话还是有很多启发式搜索的方法可以用的，我使用的就是其中一种叫模拟退火的方法

登录/注册后可看大图

评分

参与人数 1	宅币 +5	贡献 +3	收起理由
小随	+ 5	+ 3	o(￣▽￣)ブ发糖

查看全部评分

博客什么的求人气 http://bimania.org

回复

使用道具举报

该用户从未签到

9 主题	36 好友	2780 积分

积分: 2780

发表于 2013-8-18 09:59:39 | 显示全部楼层

TSP最优解的高效算法估计没戏..

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

该用户从未签到

258 主题	314 好友	3万积分

积分: 35715

楼主| 发表于 2013-8-18 12:48:23 | 显示全部楼层

dchneric 发表于 2013-8-18 09:59

登录/注册后可看大图

TSP最优解的高效算法估计没戏..

嗯，虽然还没证明，不过业界一般认为是没戏的

博客什么的求人气 http://bimania.org

回复支持反对

使用道具举报

该用户从未签到

1 主题	9 好友	1682 积分

积分: 1682

发表于 2013-8-21 13:17:44 | 显示全部楼层

本帖最后由 z652392868 于 2013-8-21 13:19 编辑

让我想起我科一次讲座上新加坡佬写的“进化算法”。。。有兴趣自己戳IEEE找evolution arithmetic
PS:他留的作业就是要用进化算法找旅行商问题优解

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

该用户从未签到

258 主题	314 好友	3万积分

积分: 35715

楼主| 发表于 2013-9-5 09:26:15 | 显示全部楼层

z652392868 发表于 2013-8-21 13:17

登录/注册后可看大图

让我想起我科一次讲座上新加坡佬写的“进化算法”。。。有兴趣自己戳IEEE找evolution arithmetic
PS:他留的 ...

这个倒没有听说过，只听说过遗传算法

博客什么的求人气 http://bimania.org

回复支持反对

使用道具举报

发新帖

小黑屋|手机版|技术宅(Z站|基宅) ( 粤ICP备18082987号-1 )

GMT+8, 2025-6-16 20:18 , Processed in 0.083816 second(s), 25 queries , Redis On.

Copyright © 2018 技术宅社区

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表