Fuu*_*Fuu 19 algorithm geometry computational-geometry
在工业中,通常存在一个问题,您需要计算材料的最有效使用,无论是织物,木材,金属等.因此起点是给定尺寸的X形状,由多边形和/或弯曲制成lines和target是给定尺寸的另一个多边形.
我假设许多当前的CAM套件实现了这一点,但没有使用它们或内部的经验,使用什么样的计算算法来找到最有效的空间利用？有人能指出我讨论这个主题的书或其他参考书吗？
Fuu*_*Fuu 16
安德鲁在他的回答中指出了正确的方向,并为我指出了问题,我决定将我的研究结果放在一个单独的答案中.
这确实是一个包装问题,更准确地说,这是一个嵌套问题.问题在数学上是NP难的,因此当前使用的算法是启发式方法.除了琐碎的问题集之外,似乎没有任何解决方案能够在线性时间内解决问题.如果要实现具有良好材料利用率的解决方案,使用当前硬件解决复杂问题需要几分钟到几小时.有数十种商业软件解决方案提供形状嵌套,但我无法找到任何开源解决方案,因此没有真正的例子可以看到实际实现的算法.
哥本哈根大学(Nielsen)的BennyKjærNielsen撰写的论文中可以找到关于历史解决方案的嵌套和条带嵌套问题的优秀描述.
一般方法似乎是混合和使用多种已知算法,以便找到最佳嵌套解决方案.这些算法包括(引导/迭代)本地搜索,基于No-Fit Polygon的快速邻域搜索和Jostling Heuristics.我在这个主题上发现了一篇很好的论文,上面有关于算法如何工作的图片 到目前为止,它还具有不同软件实现的基准.本文由S. Umetani等人(Umetani)在2006年国际调度研讨会上发表.
迄今为止,一种相对较新且可能是最好的方法是基于混合遗传算法(HGA),这是一种由模拟退火和遗传算法组成的混合算法,武汉大学的吴庆明等人(全明)对此进行了描述.他们通过在MatLab中使用Visual Studio,SQL数据库和遗传算法优化工具箱(GAOT)来实现这一点.
你指的是一个众所周知的计算机科学包装领域,对于二维空间和三维空间都存在着各种各样的问题和研究.
网络上有相当多的材料可用于定义的问题,但要找到它,你必须知道要搜索的问题的名称.
有些软件包可能会采用启发式appraoch(我怀疑它们会这样),有些软件包可能会花费很多时间来计算所有可能性以获得绝对正确的答案.
http://en.wikipedia.org/wiki/Packing_problem