在工业中，通常存在一个问题，您需要计算材料的最有效使用，无论是织物、木材、金属等。所以起点是给定尺寸的 X 数量的形状，由多边形和/或弯曲制成线，目标是给定尺寸的另一个多边形。
我假设许多当前的 CAM 套件都实现了这一点，但是没有使用它们或其内部的经验，使用什么样的计算算法来找到最有效的空间使用？有人可以指点我讨论这个话题的书或其他参考资料吗？
问问题
8948 次
2 回答
19
在 Andrew 在他的回答中为我指出了正确的方向并为我命名了问题之后，我决定将我的研究结果放到一个单独的答案中。
这确实是一个打包问题，更准确地说，是一个嵌套问题。这个问题在数学上是 NP-hard，因此目前使用的算法是启发式方法。除了琐碎的问题集外，似乎没有任何解决方案可以在线性时间内解决问题。如果您想获得具有良好材料利用率的解决方案，则使用当前硬件解决复杂问题需要几分钟到几小时的时间。有数十种提供形状嵌套的商业软件解决方案，但我找不到任何开源解决方案，因此没有可以看到算法实际实现的真实示例。
可以在哥本哈根大学 ( Nielsen )的 Benny Kjær Nielsen 撰写的论文中找到关于嵌套和条形嵌套问题的出色描述以及历史解决方案。
一般方法似乎是混合和使用多种已知算法以找到最佳嵌套解决方案。这些算法包括（引导/迭代）局部搜索、基于No-Fit Polygon的快速邻域搜索和Jostling Heuristics。我找到了一篇关于这个主题的精彩论文，其中包含算法如何工作的图片。到目前为止，它还具有不同软件实现的基准。这篇论文由 S. Umetani 等人 ( Umetani ) 在 2006 年国际调度研讨会上发表。
一种相对较新且可能是迄今为止最好的方法是基于混合遗传算法（HGA），这是一种由模拟退火和遗传算法组成的混合算法，由武汉大学的吴庆明等人（泉明）描述。他们通过在 MatLab 中使用 Visual Studio、SQL 数据库和遗传算法优化工具箱 (GAOT) 实现了这一点。
于 2010-04-21T19:15:06.520 回答
6
您指的是一个众所周知的包装计算机科学领域，针对 2 维空间和 3 维空间，定义了各种问题并进行了研究。
网上有大量可用于定义问题的材料，但要找到它，您必须知道要搜索的问题的名称。
有些软件包很可能采用启发式方法（我怀疑他们会这样做），有些可能会竭尽全力计算所有可能性以获得绝对正确的答案。
于 2010-04-20T12:47:44.737 回答