algorithm - 具有多种尺寸箱的 2D 箱装箱

Question

假设我们有多个由长度 x 宽度定义的箱子尺寸，这些尺寸可以称为“原 Material ”尺寸。

我需要从原 Material 中切割出一定数量的 table (矩形，断头台形式)，以便最大限度地减少原 Material 的数量。

由于垃圾箱的大小不同，因此应该以某种方式考虑或优先考虑它们以反射(reflect)它们的值(value) - 因此更大的垃圾箱显然“更贵”。

我知道这是一个 NP 完全问题，我不希望在多项式时间内使用确定性算法。

我需要一个解决问题的算法。

任何建议都会有帮助!

谢谢

Answer 1

嗯，基础知识是:您首先需要定义良好的函数。只有在那之后你的问题才能被考虑清楚。让我们将 Material 板上的任何矩形布局称为“排列”。 goodnes 函数应该从 Arrangements 域映射到实数域，比方说，越大越好。该函数应随着给定 Arrangement 中“浪费”的 Material 量而减少，并随着 Arranegement 满足的矩形的数量和值而增加。我再说一遍，您是必须定义善函数的人，即 Material 的相对值(value)和各个矩形的值(value)，正如您所说，这符合“越大越好”的说法。你必须量化它。

执行此操作后，将为您打开大量算法，第一个是随机算法:您在 Material 板上随机分布一个非重叠排列或矩形，评估其优度并将其存储在内存中。重复多次后，您会选择最好的一个。该算法的改进将是尝试选择已经很好的安排并稍微“插入”矩形以获得更多小矩形的空间。这就是迪伦使用模拟退火的意思。顺便说一句。不要阅读关于模拟退火的维基百科页面，它只会让你的头脑困惑。

---

评论回复:

尼克，显然，你必须从一开始就使用各种垃圾箱。假设您定义了起始 Material 表(作为位图或矢量)。您将执行以下操作:1.随机选取一个点2.随机挑选一个矩形类型3.随机选择旋转4. 如果矩形不适合，回到第 1 点。5. 如果矩形合适，将其放在 Material 片上， 尝试用同样的方法放置第二个矩形。6. 然后第三次，第四次等等，直到你遇到太多的失败并得出结论 你走进了死胡同。7.计算结果安排的优劣8.继续下一个安排

现在我想到，也许您的切割机只允许一个方向(2 轴没有工具旋转)，因此不必考虑矩形的旋转。在这种情况下，您不仅会在任何地方随机选择点，还会在 Material 的一侧随机选择点工作表或已经在工作表上的另一个矩形的一侧，您将放置此点的下一个矩形，使其与工作表的边相邻或与另一个矩形。在这种情况下(没有旋转)你可以随机选择一个方向并沿所选方向移动新矩形，直到它碰到任何垂直方向墙。这样，您将节省计算工作并从一开始就做出更好的安排去。最后一步仍然是计算优度函数并选择最好的。