关于线路最短的解法

sunsoncheng · 发表于 2011-10-19 14:57

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

雕刻机的行走文件如下:
G0 X0.000 Y420.000
G01 X1092.000 Y420.000
G0 X1092.000 Y0.000
G01 X1092.000 Y3360.000

X Y分别代表的是坐标,
G0表示是机器空走
G1表示是的真正做功,

上面四句的意思是:空走到 X0.000 Y420.000 处开始做功到X1092.000 Y420.000 ,
再由本点空走到 X1092.000 Y0.000 ,再由X1092.000 Y0.000开始做功到X1092.000 Y3360.000

默认是帅0,0点开始,最后又要走回原点

文件里,感觉走的路径是没有优化过的,
想对其进行下优化,不知那位朋友做个示例,或给个思路?

谢谢

sunsoncheng · 发表于 2011-10-19 14:58

发一个实际的文件给各位参详一下

hjj0451 · 发表于 2011-10-19 15:00

来学习一下，很有意思~~

sunsoncheng · 发表于 2011-10-19 17:13

suwenkai 你好:
未知你讲的撞刀是什么回事,我现在面对的只有一把刀的情况

现实中的问题是:
这样走来走去的速度太慢了,成了瓶颈项,后工序及前工序全部都做好了,就等它完成,

如果能快一点的话,至少空刀走的时间少一点,也是好的

谢谢了!

suwenkai · 发表于 2011-10-19 16:58

最短线路？要不要考虑是不是要撞刀了？感觉没有最短的，合理就可以了。

sunsoncheng · 发表于 2011-10-19 17:29

这里的文件有一个可见的事就是:

所有运行的方向都是坐标由小到大的,

可以假设它由大到小回头也可能工作的情况来重新处理
是我的其中一个想法!

Moneky · 发表于 2011-10-19 17:44

本帖最后由 Moneky 于 2011-10-19 17:47 编辑

有意思，留个脚印关注一下。也想了一下，有些复杂。个人理解的实质是：需要在一个平面上按要求作一系列线段，求笔尖运动距离最短的方案。不知是否正确

灰袍法师 · 发表于 2011-10-19 17:49

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

看过了
初步的理解是，问题的实质是减少空走的总长度
把每一对 G0-G1 看作一次雕刻动作
问题就变成：对若干个雕刻动作排序，使上一个G1 到下一个G0 的总长度最少
简单的处理可以用随机算法，随机排序若干次，找出最优的一次排序结果即可
更复杂的可以随机再加上贪婪算法，遗传算法等启发式算法。
单用规划求解或者Lingo之类的求解软件应该不如自己写程序高效。
楼主的问题应该跟这个帖差不多，都是要求排序一组数据，使计算结果最佳
http://club.excelhome.net/thread-702132-1-1.html

楼下的算法是简单的贪婪法，通常求解效果都比较差的。。。

Moneky · 发表于 2011-10-19 18:04

本帖最后由 Moneky 于 2011-10-19 18:31 编辑

有一个想法，但估计不是最优的【已经证实不优】。如下图：（基于7楼的理解）

蓝色的点为初始点
粗线条为需要画的线
虚线为提笔空走的路线
关联点：同一条线段的端点相关联，把这两个点称为一对关联点（互为关联点）
当前点：当前笔所在的点
目标点：笔需要到达的点

算法是这样：
先以蓝色起点为  当前点
计算当前点与其他所有点的距离（所有没有标记为1的点，如何标记在下面有）
设定目标点为与当前点距离最小的点  （此时这个点是一条线段的端点）
运动到目标点（此时当前点=目标点）
设定新的目标点为当前点的关联点
运动到目标点（画线段）
运动到目标点后给刚刚所画线段的两个端点做个标记（假设标记为  1）

然后再以现在的目标点为当前点，重复刚刚上面的操作（计算与其他点的距离，求出最小距离点，再移动到最小距离点，划线到那个点的关联点，……）

说明：
可以根据标记为1的点的个数来判断是否完成了所有的操作

==============================================
数据量小的话，可以穷举出来。假设N条线段，不同的做法有2^N×N！种，把这么多穷举出来，再求出最小值，就肯定是最优的方案了

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

我的初步想法也是如9楼的

法师的贴子还没看,

多谢各位的支持

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

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