关于线路最短的解法

sunsoncheng · 发表于 2011-10-19 20:23

法师的理解里面,是固定了划线的方向了,

估计原文件的就是最优的方案了

现在想的是能否反方向作功,才有可能产生新的最优解

明天我会作一次对比的:)

灰袍法师 · 发表于 2011-10-19 21:42

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

sunsoncheng 发表于 2011-10-19 20:23
法师的理解里面,是固定了划线的方向了,

估计原文件的就是最优的方案了

哦，如果也允许反方向的话
那么在选择下一个雕刻动作的时候， G0-G1 和 G1-G0 都可选，而且只能选一个就是了。
不会对算法有什么影响的
写个随机算法的VBA很容易，增加遗传算法和对其优化则比较麻烦，主要是因为遗传算法本身就是个麻烦的算法（不是难）。
我倒是没想好如何用Lingo去做。。。

Lingo要优化一个排序的话，约束条件写起来好麻烦。
也可以按9楼的图，把问题看做一个旅行商问题，但是多一个约束条件，即：每一个雕刻动作的G0-G1必须连通。

Moneky · 发表于 2011-10-20 00:05

看了一下算法的文章，原来9楼的算法是一种贪婪算法，绝大多数时候得不到最优方案，只是一个近似的解。

看了法师链接的帖子，专门找了遗传算法的资料，很有趣。这个地址的解说非常好 http://songshuhui.net/archives/10462

sunsoncheng · 发表于 2011-10-20 08:27

Moneky的9楼中的方式是我的能力可以达到的,而,再后面的算法,我只在论坛上听过,但如何真的写一个出来,可能不是易事

如果各位有兴趣而不啬指教的话,可以写个样办来看看?

谢谢

彭希仁 · 发表于 2011-10-20 08:48

这种东西能否用上动态规划来求？

hanna518 · 发表于 2011-10-20 09:44

有意思，学习

sunsoncheng · 发表于 2011-10-20 12:43

本帖最后由 sunsoncheng 于 2011-10-20 14:02 编辑

用法师的随机5000次的算法，每次用时0.5S

多个测试后,原文件就是最好的顺序了,

连续上述的运行50次，会有四次出现的结果较前述结果为优

总体与感觉不相同，所以还是想求一个程序
谢谢

sunsoncheng · 发表于 2011-10-20 16:09

Moneky 发表于 2011-10-19 18:04
有一个想法，但估计不是最优的【已经证实不优】。如下图：（基于7楼的理解）

我按这个做法,对同一个文件,相对于原来的起点不变的情况

现在改变它运动的方向,可以回头切的话路程少了1/3

不知道版主认为不优的原因是如何,是否我的计算出错了?

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

sunsoncheng 发表于 2011-10-20 16:09
我按这个做法,对同一个文件,相对于原来的起点不变的情况

现在改变它运动的方向,可以回头切的话路程少了 ...

不是版主

我说【已经证实不忧】其实应该是不一定优，我原来是构造了一种情况，如下图所示。
其中左边是按在9楼的方式处理的结果【手工做的】，右边是根据常识手工处理的结果。可以看出左边不如右边有效。

昨天看了一些算法，已经确定，9楼的那种算法绝大多数时候得到的不是最优解，但可能近似于最优解。

sunsoncheng · 发表于 2011-10-20 19:34

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

请各位高手来看下我做的算法比较如何?

旧的附件有点问题已更新,

主要是少了最后回刀的长度

新的附件在后面重传

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

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