3

我正在开发一款游戏，但我发现了一个问题，我必须解决这个问题来处理类似于我的包装问题的组件布局。

总结一下我需要做的事情，假设我有一个类似于以下空间的空间：

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

其中每个角落单元格是 4x4，而中央单元格是 3x3（因此剩余的单元格是 3x4 和 4x3）。然后我有一组元素放置在这些块中，这些块可以从 1x1 到 3x3 不等（我认为还不需要任何 4x4，但它不应该改变任何东西）。当然，这些元素不能越界，必须完全放在一个块内。

哪一种可能是分配它们的最佳方式？假设如果没有必要，我不希望将它们全部粘在一起（例如，如果周围有足够的空间将它们分开，则不要将两个元素放在一起）。我正在寻找一个简单的算法，也是因为情况非常有限..

奖励问题：假设除了这 9 个（可能是其他 3-4 个）之外的其他块，与新块相比，我如何优先考虑这些块？（我的意思是在达到填充阈值之前不使用附加块）..

当然我正在寻找一般的想法，没有实现:)

4

1 回答 1

7

这个 2D Bin Packing问题看起来像是NP hard。

以下是您的几个选择：

  • 蛮力或更好的分支和约束。无法扩展（根本！），但会为您找到最佳解决方案（可能不是在我们的有生之年）。

  • 确定性算法：对最大尺寸或最大边的块进行排序，并逐个遍历该列表并为其分配最佳剩余位置。这将很快完成，但解决方案可能远非最佳（或可行）。这是一张漂亮的图片，展示了一个可能出错的例子。但是，如果您想保持简单，那就是要走的路。

  • 元启发式，从确定性算法的结果开始。这将在合理的时间内给你一个非常好的结果，比人类想出的要好。根据您给它的时间和问题的难度，它可能是也可能不是最佳解决方案。那里有几个库，例如Drools Planner（开源 java）。

于 2010-12-23T16:10:11.273 回答