在cad上求解tsp问题

zdqwy19 · 发表于 2013-8-8 07:17:37

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

各位有在cad上求解tsp问题，就是求最短路径的，可以交流一下吗？

newer · 发表于 2013-8-8 08:54:34

主要是算法了，算法成熟，什么语言实现到是次要的了。

zdqwy19 · 发表于 2013-8-8 10:30:11

newer 发表于 2013-8-8 08:54
主要是算法了，算法成熟，什么语言实现到是次要的了。

这倒是，我在网上搜了不少时间，公开的是有；我觉得解算10000个点超过10分钟就没有实际意义了，有好的介绍一下！

newer · 发表于 2013-8-8 10:38:21

zdqwy19 发表于 2013-8-8 10:30
这倒是，我在网上搜了不少时间，公开的是有；我觉得解算10000个点超过10分钟就没有实际意义了，有好的介 ...

楼主，你不如抛砖引玉下，给大家先介绍下什么是TSP，什么是最短路径，模型是什么，输入什么样的数据，得到什么样的结果。

有图介绍是最好的。

zdqwy19 · 发表于 2013-8-8 12:30:27

newer 发表于 2013-8-8 10:38
楼主，你不如抛砖引玉下，给大家先介绍下什么是TSP，什么是最短路径，模型是什么，输入什么样的数据，得 ...

其实什么是tsp问题、最短路径我也搞不懂，在机械加工、物流运输、服装制作等方面都有运用，在我这只为寻找下一个相同的图形方便，算了，直接上图

以下是测试图形

请点击此处下载

查看状态：需购买或无权限

您的用户组是：游客

文件名称:测试图形.zip
下载次数:2 文件大小:130.37 KB
下载权限: 不限以上 [免费赚D豆]

zdqwy19 · 发表于 2013-8-12 13:58:56

看样子只有自己写了，上万行的代码

st788796 · 发表于 2013-8-12 22:21:59

zdqwy19 发表于 8 小时前

 登录/注册后可看大图

看样子只有自己写了，上万行的代码

有这么复杂？你把规则没有说明白来自: Android客户端

newer · 发表于 2013-8-12 23:09:59

zdqwy19 发表于 2013-8-12 13:58
看样子只有自己写了，上万行的代码

算法很重要的，如果有算法，不可能要上万行代码的，这种东西有规律的，这种东西树论，图论什么的有算法的，楼主找找？

st788796 · 发表于 2013-8-13 16:30:13

TSP没有唯一解，估计程序算出来的没有LZ画的漂亮来自: Android客户端

zdqwy19 · 发表于 2013-8-13 21:30:00

st788796 发表于 2013-8-13 16:30
TSP没有唯一解，估计程序算出来的没有LZ画的漂亮

那也是程序生成的，不过不是在cad中生成

newer · 发表于 2013-8-13 22:57:35

zdqwy19 发表于 2013-8-13 21:30
那也是程序生成的，不过不是在cad中生成

给你找了10几篇论文，找个好的算法吧，然后才是考虑程序怎么写。

下载地址：晓东文库

newer · 发表于 2013-8-13 22:58:47

下载地址：晓东文库

下载地址：晓东文库

下载地址：晓东文库

下载地址：晓东文库

一直到137，其他的去文档文库里面看吧。

zdqwy19 · 发表于 2013-8-14 11:38:28

我有concorde和aco的代码，不是双精度的，原生c的，运行速度满快的，就是得修改才能在cad中使用；前段时间修改了一个凸包法寻找最短路径的代码，在点稠度均匀的情况下图形还理想，在点稀疏度较大就不行了。
第一图和第二图就是那个代码生成的，第三图是用贪心算法生成的，时间都不是太理想，用时在5秒左右。

账号		自动登录	找回密码
密码			立即注册

[求助] 在cad上求解tsp问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评

点评

点评

点评

点评