关于线路最短的解法

msconfig98 · 发表于 2011-10-23 05:26

灰袍法师发表于 2011-10-22 15:38
是可以转化为TSP
不过你看上面的示意图，也没什么特别蠢的走线，应该用什么方法都优化不了多少了。。。楼 ...

法师说的是。受教了

Moneky · 发表于 2011-10-23 10:40

还是法师大牛。评估一下我想的一个类似的做法有没有可能取得好的结果。
想法也是用贪婪算法，只是因为单纯算法本身是一种短视行为，所以我打算每步贪婪的时候预贪婪几步（比如说3步），就像棋类算法那样。从起点开始，按贪婪算法，求出距离较短的前三个点，再次按这三个点的结果计算下一步的三个点，再……，最后比较后选择这三个点中后继 3步空走距离和最小的那个点作为下一个点，如此往复……

sunsoncheng · 发表于 2011-10-23 12:56

谢谢大家了,再学习

灰袍法师 · 发表于 2011-10-23 15:44

本帖最后由灰袍法师于 2011-10-23 18:16 编辑

Moneky 发表于 2011-10-23 10:40
还是法师大牛。评估一下我想的一个类似的做法有没有可能取得好的结果。
想法也是用贪婪算法，只是因为单纯 ...

这个想法当然可以，而且应该会比只看一步要快
n条线段贪婪法
最简单的贪婪方式，只看一步只取最短的话，搜索空间是 1，只在一种可能性里面找
我和楼主的带点随机的贪婪方式，只看一步只取前m个短线的话，搜索空间是 m^n
你的想法，搜索空间应该是 9^(n/3)
所以你的搜索空间会少很多，速度应该会快得多
你这个算法有“分治”的思想在里面了，分成3个动作的小块去做。

目前最困扰我的是：究竟还能好多少？
楼主和你的程序测试上千万次，我自己也测试了上亿次（花了2000秒）
貌似最终结果也没有好多少
要么是因为好的结果本身就极其稀少，随机数十亿次也绝对找不到一个。
要么是因为根本不存在比现在结果好10%以上的解（我比较相信这一点）
对付TSP问题，目前最好的算法应该是蚁群算法，不过这个东东的参数调试起来就跟遗传算法一样，麻烦。

Moneky · 发表于 2011-10-23 20:11

本帖最后由 Moneky 于 2011-10-23 21:05 编辑

NC文件查看器源代码及更新

现在可以拖动文件到查看器界面来打开了，不需要通过打开文件对话框。另外工具支持命令行了，可以在VBA中调用工具来打开指定文件，命令行只有一个参数，就是需要打开的NC文件带路径全名。

究竟还能好多少？真难想象，不过现在明白世界为何需要超级计算机了{:soso_e100:}

有时间了我也把上面的那个想法变成现实，看看结果到底如何。

sunsoncheng · 发表于 2011-10-24 23:37

这个贴的最大意义使我学会了一些算法, 也使我真正体会到VB处理数组的速度的快捷

同时重复使用到的数据必须先将结果算出后,再进行调用,对运算速度提高的极大帮助!

再次对各位参与者表示感谢!

灰袍法师 · 发表于 2011-10-26 00:00

闲着无聊之下，把这个问题转化为旅行商问题，用Lingo去求解
1 用VBA代码转数据格式为 Lingo求解模型要用到的距离矩阵，连接状态矩阵，强迫连接的矩阵
2 写一个好。。复。。杂。。的Lingo求解模型，主要是把每个 X-Y 坐标当作一个城市节点，这样每个动作等于两个城市
要求每个城市出入一次，要求城市之间的连接必须符合强迫连接矩阵的约束，也就是同一个动作的两个城市必须连接

3 OLE方式调用Lingo求解
4 求解结果是一个遍历城市的顺序表，用VBA把这个顺序表翻译回雕刻动作的数据表示，这样就可以用 ViewData 去看结果了

果然不出我之所料，两点都料中了
1 Lingo可以找到比随机＋贪婪算法更好的解，但是只能好一丁点，不到3%。
2 Lingo的求解时间非常长，在10秒到几百秒不等，对于动作很多的求解，是得不偿失。

结论：解决优化问题，自己写VBA其实比Lingo更好。
附件包括
可以独立运行的 .xls，直接用 VBA 调用 Lingo ，但这个方法在求解时间很长的时候，会导致OLE等待超时，求解结果无法自动写回EXCEL工作表
更好的做法是：打开 .xls，然后用 Lingo 打开 .lg4 文件，这样就可以无限时地求解，而且还不会导致EXCEL繁忙

Lingo求解带限制连接的TSP问题.rar (122.71 KB, 下载次数: 56)

测试的nc格式文件，查看nc文件的 viewdata程序在之前回帖下载，不再打包在一起了。

v111v111v · 发表于 2018-12-5 01:15

聪明的很

		自动登录	找回密码
密码			免费注册

[求助] 关于线路最短的解法