点集最短回路（TSP问题）讨论

zdqwy19 · 发表于 2013-1-5 19:56

chlh_jd 发表于 2013-1-4 00:55
@zdqwy19
感谢您的测试，希望能有更好的建议。

对于点优先按直线排序是否会使图形更理想，只能提个想法。

zdqwy19 · 发表于 2013-1-5 22:11

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

是否可以做一个指定起点的最短不交叉连线，不需要闭合，只要最短。

chlh_jd · 发表于 2013-1-6 03:38

本帖最后由 chlh_jd 于 2013-1-6 03:41 编辑

@zdqwy19
我提供的TSP函数带有一定的遗传特性，并不一定能得到最优解，尤其对于规则点阵；该算法可能还需要进一步做更大的改进，目前我也在研究中；参照直线法也是可以考虑的。
不闭合的应该属于另一类问题了，与旅行商问题有所区别；不闭合的解法是否可以这么考虑，先求最远距离点对，然后再求最短路径（未经论证）。实际问题可能更接近这种问题，出差或旅游出发时都是乘车或搭火车的，遍历各城市后累了最后一站乘飞机回家。

zdqwy19 · 发表于 2013-1-6 10:29

chlh_jd 发表于 2013-1-6 03:38
@zdqwy19
我提供的TSP函数带有一定的遗传特性，并不一定能得到最优解，尤其对于规则点阵；该算法可能 ...

我在网上搜了一下不闭合情况叫单源点最短路径问题，不过网上提供的基本上是C代码，我是看不懂。我个人认为不闭合情况在CAD作图中用途更大，希望楼主研究一下，改为lisp。

tender138 · 发表于 2013-11-2 11:05

很高深哦，慢慢学

434939575 · 发表于 2014-3-1 14:40

不知道什么用途。很强大。

hxl2854913857 · 发表于 2014-5-13 16:47

楼主的程序挺厉害的，我想请教楼主能不能用LISP实现最短路径算法中的Dijkstra算法和Floyd算法吗

lionguns · 发表于 2015-10-9 21:10

这个东西得留名！！！！

czcxxx · 发表于 2015-10-24 12:32

llsheng_73 · 发表于 2015-12-8 15:42

zdqwy19 发表于 2013-1-5 22:11
是否可以做一个指定起点的最短不交叉连线，不需要闭合，只要最短。

是否可以按chlh_jd 的程序最后把最长的那个线段弄掉？

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

点集最短回路（TSP问题）讨论

RE: 点集最短回路（TSP问题）讨论