明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
楼主: chlh_jd

点集最短回路(TSP问题)讨论

    [复制链接]
发表于 2013-1-5 19:56:53 | 显示全部楼层
chlh_jd 发表于 2013-1-4 00:55
@zdqwy19
感谢您的测试,希望能有更好的建议。

对于点优先按直线排序是否会使图形更理想,只能提个想法。
发表于 2013-1-5 22:11:34 | 显示全部楼层

RE: 点集最短回路(TSP问题)讨论

chlh_jd 发表于 2012-10-9 11:49
贴出用 ElpanovEvgeniy 的方法改进 纯VLISP 版本 , 比较适用于不规则离散点集

是否可以做一个指定起点的最短不交叉连线,不需要闭合,只要最短。
 楼主| 发表于 2013-1-6 03:38:49 | 显示全部楼层
本帖最后由 chlh_jd 于 2013-1-6 03:41 编辑

@zdqwy19
      我提供的TSP函数带有一定的遗传特性,并不一定能得到最优解,尤其对于规则点阵;该算法可能还需要进一步做更大的改进,目前我也在研究中;参照直线法也是可以考虑的。
    不闭合的应该属于另一类问题了,与旅行商问题有所区别;不闭合的解法是否可以这么考虑,先求最远距离点对,然后再求最短路径(未经论证)。实际问题可能更接近这种问题,出差或旅游出发时都是乘车或搭火车的,遍历各城市后累了最后一站乘飞机回家。
发表于 2013-1-6 10:29:13 来自手机 | 显示全部楼层
chlh_jd 发表于 2013-1-6 03:38
@zdqwy19
      我提供的TSP函数带有一定的遗传特性,并不一定能得到最优解,尤其对于规则点阵;该算法可能 ...

我在网上搜了一下不闭合情况叫单源点最短路径问题,不过网上提供的基本上是C代码,我是看不懂。我个人认为不闭合情况在CAD作图中用途更大,希望楼主研究一下,改为lisp。
发表于 2013-11-2 11:05:34 | 显示全部楼层
很高深哦,慢慢学
发表于 2014-3-1 14:40:50 | 显示全部楼层
不知道什么用途。很强大。
发表于 2014-5-13 16:47:19 | 显示全部楼层
楼主的程序挺厉害的,我想请教楼主能不能用LISP实现最短路径算法中的Dijkstra算法和Floyd算法吗
发表于 2015-10-9 21:10:26 | 显示全部楼层
这个东西得留名!!!!
发表于 2015-10-24 12:32:43 | 显示全部楼层
发表于 2015-12-8 15:42:29 | 显示全部楼层
zdqwy19 发表于 2013-1-5 22:11
是否可以做一个指定起点的最短不交叉连线,不需要闭合,只要最短。

是否可以按chlh_jd 的程序最后把最长的那个线段弄掉?
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2024-11-25 12:04 , Processed in 0.148923 second(s), 17 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

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