关于线路最短的解法

sunsoncheng · 发表于 2011-10-21 19:22

本帖最后由 sunsoncheng 于 2011-10-21 19:24 编辑

刚才已证实我面对的机子是可以反向做功(其实就是画直线而已)的了

而原来的路径只从一个方向走目的是安全考虑的更多(我的思考结果)

也有了防止安全问题的方案了,

所以求一个好的优化方案已是必然的结果了,即使用了现在我懂的算法

保守估计也会至少减少10%的总路径

感谢各位的支持与帮助,尤其是法师与Moneky

再次致谢

Moneky · 发表于 2011-10-21 20:32

恭喜啊！知识就是第一生产力。

sunsoncheng · 发表于 2011-10-21 23:02

硬着头皮再来求助一次:
按这几天所学的做了一个所谓的贪婪算法
单个时可以接受,但想进行多次的随机查找,再找一个更优的方案时,时间不能接受.

下面是我自己做的觉得时间最好的算法了,
先用一次每次最近点的贪婪算法,

之后循环1W次贪婪算法,这时的贪婪法则是以最近的两个点的随机一个作为下一个线的开始点
总共用时会到9秒

而我试过用100W次计后面的方式计算时,还找到更优的结果,不过耗时就太长了
而100W次后也只比第一次的提高了3%不到

我想,是否我的算法还有改进的地方?法师讲的遗传算法,看来看去都没有看懂
一天这样的方案过200,每批处理一般在50个以内时间长了接受不了

请教各位老大,还有没有更好的更快的算法
谢谢

我的最终确定的算法见:

Moneky · 发表于 2011-10-22 00:09

本帖最后由 Moneky 于 2011-10-22 00:12 编辑

建议：可以试试，在处理前先把任意两点的距离一次性计算出来，放入一个2维数组中，然后在需要用到的时候直接查数组就是了，避免每次用到距离时就去求一次。因为求一次距离设计到乘法与乘方运算，而像前面那样处理，整个程序只需要计算一次，应该对速度有所提升。另外，程序也可以只求空走的距离和就行了，应该对于特定的数据文件来说，实际做功的距离是个常数（没有仔细看楼主代码，或许已经这样了）
我在27楼中的代码是采用的字典来储存的两点间的距离，感觉可能数组应该快一些，因为字典的key是字符型的，而数组的下标是数值型。

27楼中，我是对原数据文件的点编了号，用字典来储存两点间的距离，字典的key格式为    点1编号+空格+点2编号。如果用数组的话，可以定义一个二维数组
例如： L(0 to pointcount,0 to pointcount) as single    其中pointcount为原数据文件中点的个数
      然后可以用L(m,n)表示点m到点n的距离，在后面的过程中如果需要求这两个点的距离，可以直接 L(m,n) 即可。
ps：用27楼自己写的那一段代码随机了9999999次，对于22.NC或33.NC中的某个文件得到了一个小于40000的结果

灰袍法师 · 发表于 2011-10-22 04:48

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

人手做的求解结果，11_best.nc
总长度是37958

人手结果.rar (64.36 KB, 下载次数: 27)
楼主最后发表的程序比人手做的还要好一点，不过楼主的附件貌似没有输出结果。
这么有规律的横竖图案，好的方案都只能是从最高的竖线开始，只走竖线， S形往下
然后从最低的横线开始，只走横线，S形往上，回到接近于原点的地方
诸如此类，变化实在不大。
我觉得即使用遗传算法也不大可能做得更好了。。。
毕竟最大的X坐标＋最大的Y坐标＋所有做工的线段长度，加起来已经是 32936了。
不管你怎么优化，都不大可能比这个低
也就是说撑死了再比 37958 好 10% 左右（还不一定有这样的解。。。）

sunsoncheng · 发表于 2011-10-22 09:19

Moneky 发表于 2011-10-22 00:09
建议：可以试试，在处理前先把任意两点的距离一次性计算出来，放入一个2维数组中，然后在需要用到的时候直接 ...

我也用KW级算过一次,是40000以下的,不过,那时间可花不起!

按你的提示做了更改,速度又提高了1/3,要再看看还有没有更好的办法,可能就是那个寻找最近点的内容要更改了解

如果再没有更好的办法,现在的方式其实也是可以接受的!

:)

灰袍法师 · 发表于 2011-10-22 17:47

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

sunsoncheng 发表于 2011-10-22 09:19
我也用KW级算过一次,是40000以下的,不过,那时间可花不起!

按你的提示做了更改,速度又提高了1/3,要再看 ...

要多用几个数据文件测试
附件带了一个简单的无空走路程的图案，貌似随机算法可以找出这个完美的路线
动作更多的优化问题就不清楚了，估计动作组合越多，随机算法找出好解的耗时就会越长，解的质量会越低。

附件是最新的附件，导入，导出，优化，画图都齐了，同时附上Moneky的ViewData和该程序要用到的控件。

算法是：
随机起步，然后每一步选择后续动作都加上了贪婪算法
我的做法是先算好每一个动作的优先列表（也就是先算出这个动作后面跟的动作1，动作2。。。。。。所有动作的空走长度，并且排序）
这样在随机选择的时候可以从前面开始取，速度大大提高了。
遗传算法肯定比随机＋贪婪强，因为遗传算法本身就建立在随机＋贪婪的基础上，但是能强多少？我对此不甚乐观，因为这样的图案实在太有规律，贪婪法的效果也是很好的了，楼主最好上传几个动作很多的nc文件。
根据我的四个测试文件，貌似对于很复杂的图案，也很难大幅度击败最简单的贪婪算法。

算法.rar (115.34 KB, 下载次数: 79)

附件再次更新，速度更快，而且几乎必定比最简单的贪婪算法强，总算没有白忙一场。
算法是：采用一定概率决定用当前最优/次优/第三优，也就是说，每一步都不一定是最贪婪的，效果非常好！！！
下图是50个动作，随机坐标的求解结果示意图。
随机坐标的求解结果.jpg

msconfig98 · 发表于 2011-10-23 03:33

灰袍法师发表于 2011-10-22 04:47
要多用几个数据文件测试
附件带了一个简单的无空走路程的图案，貌似随机算法可以找出这个完美的路线
动 ...

感觉像是一个改版的 “中国邮路问题”。
即，做功的路线至少需要经过一次，不做功的路线不一定需要经过。
不知道是不是可以转化成邮路问题来求解

灰袍法师 · 发表于 2011-10-23 04:38

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

msconfig98 发表于 2011-10-23 03:33
感觉像是一个改版的 “中国邮路问题”。
即，做功的路线至少需要经过一次，不做功的路线不一定需要经过 ...

是可以转化为TSP
不过你看上面的示意图，也没什么特别蠢的走线，应该用什么方法都优化不了多少了。。。楼主又不是生产航天飞机，优化结果差个10%没啥问题。
而且根据我的经验，运筹学软件如Lingo之流，未必就比自己写的VBA好。。。。。。

灰袍法师 · 发表于 2011-10-23 09:03

再次更新了37楼附件
速度和性能都有提高，尤其是对于复杂图案，几乎可以肯定比最简单的贪婪算法强。

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

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