重新审视包装问题

Question

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

总结一下我需要做的事情,假设我有一个类似于下面的空间:

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

其中每个角单元为4x4,而中心单元为3x3(因此其余角单元为3x4和4x3).然后我有一组元素放在这些块中,可以从1x1到3x3不等(我认为还不需要任何4x4,但它不应该改变任何东西).当然,这些元素不能跨越线条,必须完全位于一个块内.

哪个可能是分配它们的最佳方式？如果没有必要,我宁愿不让它们全部粘在一起(例如,如果周围有足够的空间将它们分开,则不要将两个元素放在一起).我正在寻找一个简单的算法,也因为情况非常有限..

奖金问题:假设除了这9个(可能是其他3-4个)之外的其他区块我怎么能比新的区块优先考虑这些区块？(我的意思是在达到填充阈值之前不使用附加块)

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

Answer 1

这个2D Bin Packing问题看起来很像NP.

以下是您的几个选择:

• 蛮力或更好的分支和约束.不缩放(根本没有!),但会找到最佳解决方案(不是在我们的生命中).

• 确定性算法:对最大尺寸或最大边的块进行排序,逐个浏览该列表,并为其分配最佳剩余点.这将很快完成,但解决方案可能远非最佳(或可行).这是一张很好的图片,展示了一个可能出错的例子.但如果你想保持简单,那就是要走的路.

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