假设我们有多个由 Length x Width 定义的箱尺寸，这些可以称为“原材料”尺寸。
我需要从该原材料中切出一定数量的表格（矩形，断头台形式），以最大限度地减少原材料的数量。
由于垃圾箱的大小不同，它们应该以某种方式考虑或优先考虑以反映它们的价值 - 所以更大的垃圾箱显然“更贵”。
我知道这是一个 NP 完全问题，我不希望在多项式时间内出现确定性算法。
我需要一个解决问题的算法。
任何的意见都将会有帮助！
谢谢
问问题
1214 次
1 回答
1
嗯，基础是：你首先需要定义一个好的函数。只有在那之后，你的问题才能被认为是明确的。让我们将材料板上的任何矩形布局称为“排列”。goodnes 函数应该从 Arrangements 域映射到实数域，比方说越大越好。该函数应随着给定布置中“浪费”的材料量而减小，并随着布置所满足的矩形的数量和值而增加。我再说一遍，你是必须定义善良函数的人，即材料的相对价值和各个矩形的价值，正如你所说，这符合“越大越好”的说法。你必须量化它。
一旦你这样做了，大量的算法就会为你打开，第一个是随机算法：你在你的材料片上随机分布一个不重叠的排列或矩形，评估它的好坏并将它存储在内存中。在你这样做足够多次之后，你会选择最好的一个。该算法的改进是尝试选择已经很好的排列并稍微“轻推”矩形以获得更多小矩形的空间。这就是 Dylan 使用模拟退火的意思。顺便说一句。不要阅读关于模拟退火的维基百科页面，它只会让你头疼。
回复评论：
尼克，很明显，你必须从一开始就使用各种垃圾箱。假设您定义了起始材料表（作为位图或通过矢量）。您将执行以下操作： 1. 随机选取一个点 2. 随机选取一个矩形类型 3. 随机选取旋转 4. 如果矩形不适合，请返回点 1。 5. 如果矩形适合，放置它在材料表上并尝试通过相同的方法放置第二个矩形。6、然后是第三、第四等，直到遇到太多失败，得出死胡同。7. 计算结果排列的好坏 8. 继续下一个排列
现在我突然想到，也许您的切割机只允许一个方向（2 轴没有工具旋转），因此不必考虑矩形的旋转。在这种情况下，您不仅会在任何地方随机选择该点，还会在材料片的一侧或已经在片材上的另一个矩形的一侧选择该点，然后将下一个矩形放置到该点，使其具有相邻的边纸张的一侧或另一个矩形。在这种情况下（无旋转），您可以随机选择一个方向并沿所选方向移动新矩形，直到它碰到任何垂直的墙壁。这样，您将节省计算工作并从一开始就创建更好的安排。最后一步仍然是计算优度函数并选择最好的。
于 2012-07-20T05:21:47.247 回答