algorithm - 此几何(木工相关)程序的最佳算法

Question

如标题所述，我的问题是寻找最佳算法来解决我正在处理的问题。我只是在寻找见解/建议。

这个问题是我叔叔向我提出的，他认为如果我能在移动平台上实现它，这对我来说既是一个很好的挑战，也可能是一个有用的软件。在这里:

“我正在使用已知标准尺寸(4' x 8' 或 5' x 5')的板材做一些木工工作。我有一个“切割 list ”，包含各种已知的木片我需要的尺寸。我想做的是快速弄清楚如何将薄片商品分解成有用的碎片，并尽可能减少浪费。

另一个需要考虑的因素是锯片切口(或宽度)。例如，您只能从一张 4' x 8' 的板材中得到三个 2' x 4' 的部件(而不是四个)，因为在进行三个切割时会损失 Material 。

我设想的是一个程序，我可以在其中输入纸张尺寸、我正在使用的 Blade 的切口(它是可变的)、我想要的成品尺寸，并且该程序会生成一张粗略的图纸切割最有效地减少浪费的图案。”

目前，我只是致力于编写一种算法，以找到一种浪费最少的解决方案。改天我会在 Android 上实现它。

就实际算法而言，到目前为止，这是我的想法:

• 按照区域降序排列“cut-list”
• 将此列表中的第一项放在工作表上，使其占据最左上角的可用位置
• 如果列表中的当前项目无法放在工作表上，则尝试放置下一个最大的
• 如果切割列表中的任何部分都不能适合当前工作表，则开始填充新工作表
• 重复直到切割列表为空

我(目前)还不熟悉算法世界，因此非常感谢这里的任何见解!

如果有什么不清楚的，请告诉我。

谢谢，夸尔

Answer 1

假设截缝为 k 个单位。然后将每 block 的每条边向外移动k/2 个单位，同时将纸张的每条边向外移动k/2 个单位。这将问题简化为古老的 2D 下料问题，正如评论者所指出的那样，它是 NP 完全问题。但是，如果您乐于将自己限制在少量零件或接受近似值，there're a whole pile of algorithms that'll suit your needs .

如果我是你，我会先实现一个愚蠢的贪婪算法，然后围绕它构建应用程序。如果后来发现它太慢或产生的结果不佳，请返回并用更复杂的东西代替它。