ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 12179|回复: 47

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

[复制链接]

TA的精华主题

TA的得分主题

发表于 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点开始,最后又要走回原点

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

谢谢

TA的精华主题

TA的得分主题

 楼主| 发表于 2011-10-19 14:58 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
发一个实际的文件给各位参详一下

1.rar

210 Bytes, 下载次数: 146

TA的精华主题

TA的得分主题

发表于 2011-10-19 15:00 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2011-10-19 17:13 | 显示全部楼层
suwenkai  你好:
未知你讲的撞刀是什么回事,我现在面对的只有一把刀的情况

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

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

谢谢了!

TA的精华主题

TA的得分主题

发表于 2011-10-19 16:58 | 显示全部楼层
最短线路?要不要考虑是不是要撞刀了?感觉没有最短的,合理就可以了。

TA的精华主题

TA的得分主题

 楼主| 发表于 2011-10-19 17:29 | 显示全部楼层
这里的文件有一个可见的事就是:

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

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

TA的精华主题

TA的得分主题

发表于 2011-10-19 17:44 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 Moneky 于 2011-10-19 17:47 编辑

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

TA的精华主题

TA的得分主题

发表于 2011-10-19 17:49 | 显示全部楼层
本帖最后由 灰袍法师 于 2011-10-19 18:47 编辑

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

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

TA的精华主题

TA的得分主题

发表于 2011-10-19 18:04 | 显示全部楼层
本帖最后由 Moneky 于 2011-10-19 18:31 编辑

有一个想法,但估计不是最优的【已经证实不优】。如下图:(基于7楼的理解)
2011-10-19_175318.jpg

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

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

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

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

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

TA的精华主题

TA的得分主题

 楼主| 发表于 2011-10-19 20:18 | 显示全部楼层
我的初步想法也是如9楼的

法师的贴子还没看,

多谢各位的支持
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-29 08:18 , Processed in 0.034118 second(s), 10 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表