一尘不染

重新包装问题

algorithm

我正在开发游戏,但发现一个必须解决的问题,该问题类似于包装问题。

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

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

其中每个角落单元格为4x4,而中央每个单元格为3x3(因此其余单元格分别为3x4和4x3)。然后,我在这些块中放置了一组元素,它们的范围可以从1x1到3x3不等(我认为还不需要任何4x4,但它不应更改任何内容)。当然,这些元素不能越界,必须完全位于一个块内。

哪一种是分配它们的最佳方法?假设如果不需要,我不想将它们全部粘在一起(例如,如果周围有足够的空间将它们分开,则不要将两个元素放在一起)。我正在寻找一种简单的算法,也是因为情况非常有限。

额外的问题:假设除了这9个区块外(也许还有其他3-4个),与新区块相比,我该如何优先考虑这些区块?(我的意思是直到达到填充阈值才使用附加块)。

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


阅读 161

收藏
2020-07-28

共1个答案

一尘不染

这个2D
装箱问题看起来像是NP难题

这是您的几个选择:

  • 蛮力或更好的分支和约束。(根本不扩展),但是会找到最佳的解决方案(也许不是我们的一生)。

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

  • 从确定性算法的结果开始的元启发式。这将在合理的时间内为您提供非常好的结果,比人类想像的要好。根据您给它多少时间以及问题的难度,它可能是最佳解决方案,也可能不是。这里有几个库,例如Drools Planner(开源Java)。

2020-07-28