关于线路最短的解法

mschenshan · 发表于 2011-10-20 20:00

本帖最后由 mschenshan 于 2011-10-20 20:05 编辑

题目很有意思。
不过机器并不是大家想象的那样以最短距离运动的。
工件安装台面：
左右、前后运动，
刻刀（实际是头部为三棱形状）上下运动。
比如刻一个字母 A ，有两种方法：
1。先刻完外面，再刻里面的△；
2。先刻完里面的△，再刻外面。
即：尽量减少刀的上下动作。原因：雕刻时并不是戳，而是靠高速旋转的三棱边来切削。

sunsoncheng · 发表于 2011-10-20 20:02

重新上传新的附件

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

mschenshan 发表于 2011-10-20 20:00
题目很有意思。
不过机器并不是大家想象的那样以最短距离运动的。
工件安装台面：

如何做不是我们的讨论范围,这个应该有程序设定了它的做法

如果用我的语言就是,做功的过程,不必理会

这里只讨论,从一个地方到另一个地方做功时,空走的时间是否可以省下来!

而且我的机子,只需要简单地画直线

所以才有了这个问题!

sunsoncheng · 发表于 2011-10-20 20:15

当然现在讨论的只是在理论的层面

如果那刀不允许反向做功(画线) 的话,这一切都成了空谈

看来楼上 mschenshan 是有实际工作经验的人

maditate · 发表于 2011-10-20 20:18

机绣。呵呵。

灰袍法师 · 发表于 2011-10-20 23:45

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

mschenshan 发表于 2011-10-20 20:00
题目很有意思。
不过机器并不是大家想象的那样以最短距离运动的。
工件安装台面：

这位的质疑非常好，其实我也有很多对实际问题的疑问
不过据我所知，楼主是个相当有经验的好筒子，所以就相信他吧。
我本来想问：
1 水平移动跟垂直移动是不是一样速度，后来想一下，这个处理起来很简单。
2 优化能够提升多少，是不是足够避免成为流水线上的瓶颈了，不然再怎么优化还是要另买机器那就没意思了。然后看9楼Moneky以及后续的图示，觉得优化余地还是相当大的。
3 对程序的速度有什么要求，如会不会机器数秒钟就可以完成一批动作，所以程序必须在数秒之内完成优化。
4 要优化的一批动作最多有多少个

楼主的附件为什么没有做随机排序的时候也可以反向动作呢？另外建议增大随机次数，1万次通常都远远不够的，100万次差不多。。。
另外，程序的结果还是要做成 Moneky 的图示，才方便人去判断，这又是一个程序了。。。
附件读取 test.NC 数据
并且在windows的画图里面画出图案（需要先人手在画图里面设置图像属性为 500x500）
貌似楼主的机器都只是在画水平线和垂直线。

用test.NC的数据画图.rar (19.5 KB, 下载次数: 36)

Moneky · 发表于 2011-10-21 05:11

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

用VB做了一个读NC文件的工具，可以用来读取NC文件，并作简单演示。（获取文件数据到数组直接用的楼主的代码）说明：图中的蓝色点为起点（0，0）
      实线为需要做功的线段
      虚线为不做功的线段（空走还是空刀不懂）
      最后统计的线段数为  做功的线段数
      总长度为：当没有选择【不绘制空走】为所有线段（空走+不空走）的长度和
                        当选择【不绘制空走】为所有不空走线段的长度和

另外我写了一个随机的算法过程，算出来的比楼主的那个要短一些。同时楼主的随机化算法算出的结果似乎是固定的，怎么回事？

下面的附件中，表格文件是在楼主的代码中改的，注释为'=============================之间的代码是我添加的随机化算法，另外添加了一个MakeFile过程，用来将随机化算法的结果保存为*.nc文件的。

法师也是个夜猫子啊！

灰袍法师 · 发表于 2011-10-21 05:54

本帖最后由灰袍法师于 2011-10-21 21:29 编辑

27楼 moneky 的 viewdata 程序做得非常好，强烈建议下载，不过64位windows打不开，要复制COMDLG32.OCX文件到当前目录，或者用32位windows才行。
现在可以把精力放在优化 NC 文件上面了，咔咔咔。
怪不得楼主一直念叨来回下刀，原来都是在画横横横。。。竖竖竖。。。
楼主在代码中提到，随机＋贪婪，这也是一个很常用的方法，把两者的优点结合了。
比方说，不要固定贪婪算法的起点，而是从比较接近0,0的几个点随机挑选，
每一步的贪婪过程，都不一定选择当前最短的那一个，而是从当前较短的几个里面随机选
这样重复N次，就可以得到比单纯贪婪和单纯随机都好的结果。

sunsoncheng · 发表于 2011-10-21 08:41

非常感谢两位的支持！

sunsoncheng · 发表于 2011-10-21 09:26

本帖最后由 sunsoncheng 于 2011-10-21 09:27 编辑

Moneky 发表于 2011-10-21 05:11
用VB做了一个读NC文件的工具，可以用来读取NC文件，并作简单演示。（获取文件数据到数组直接用的楼主的代码 ...

楼主的随机化算法算出的结果似乎是固定的

关于这个问题作下解释吧：

我的随机算法里没有进行反方向的操作，做了很多对比，与我们想的最开始点作为做功开始点的结果基本相同

测算了几个文件N次，会有几次结果产生了变动

在我这里验证了几个事实：
1、原文件是经过优化的，
2、它的优化是前提必须是固定方向的（这个我还要查机器的原因）
3、它优化所用的算法就是最近的的开始点计算的
4、经多次多文件测试，现在文件的排列基本已接近最优解（只按上述条件的情况下）

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

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

评分