包装问题重新 [英] Packing problem revisited

问题描述

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

I'm developing a game and I found a problem that I have to solve to handle the layout of a component which resembles me a packing problem.

要总结一下我需要做的假设我有类似以下内容的空间：

To summarize what I need to do suppose I've got a space similar to the following one:

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

在其中的每一个角落细胞是四轮驱动，而中央一台是3×3（使剩下的是3×4和4×3）。然后，我有一组元素将这些模块可以从1x1的变化到3×3（我不认为任何四轮驱动是必要的，不过也它不应该改变任何东西）内。当然，这些元素不能越过线，而且必须一个单一的块内全部铺设。

in which every corner cell is 4x4 while central one is 3x3 (so that remaining ones are 3x4 and 4x3). Then I have a set of elements to place inside these blocks that can vary from 1x1 to 3x3 (I don't think any 4x4 is needed yet but it shouldn't change anything). Of course these elements cannot cross the lines and must lay entirely within one single block.

这可能是分配他们的最好方法是什么？假设我preFER不要把它们都stickied在一起，如果不是必要（例如，不要把两个元素结合在一起，如果有足够的空间周围放置它们分开）。我在找一个简单的算法，也因为这种情况是相当有限的。

Which could be the best way to allocate them? Assuming that I prefer not to have them all stickied together if is not necessary (eg. do not place two elements together if there's enough room around to place them apart). I'm looking for a simple algorithm, also because the situation is quite limited..

奖金的问题：假设除了其它模块这9个（也许其他3-4）我怎么能优先考虑这些较新的？ （我的意思只是不使用附加块，直到填充门槛已经达到）。

Bonus question: assuming other blocks in addition to these 9 (maybe other 3-4) how could I prioritize these compared to the new ones? (I mean just doesn't use the additional block until a fill threshold has been reached)..

当然，我在寻找的总体思路，没有实现：）

Of course I'm looking for the general idea, no implementation :)

推荐答案

这2D 装箱问题看起来像它的 NP难。

This 2D Bin Packing problem looks like it's NP hard.

下面是几个你的选择：

• 蛮力或更好的分支定界。没有规模（在所有！），但一定会找到你的最佳解决方案（而不是在我们的有生之年可能）。

• Brute force or better yet branch and bound. Doesn't scale (at all!), but will find you the optimal solution (not in our lifetime maybe).

确定算法：在最大尺寸或最大侧块进行排序，并通过该列表一个接一个，并为其分配剩余的当场最佳。这将结束非常快，但是该解决方案可以远离最优（或不可行）。 <一href="https://raw.githubusercontent.com/droolsjbpm/optaplanner/master/optaplanner-docs/src/main/docbook/en-US/images/Chapter-Use_cases_and_examples/binPackingIsNpComplete1.png"相对=nofollow>这是一个不错的画面显示的一个例子可以出现什么问题。但是，如果你要保持它的简单，这是要走的路。

Deterministic algorithm: sort the blocks on largest size or largest side and go through that list one by one and assign it the best remaining spot. That will finish very fast, but the solution can be far from optimal (or feasible). Here's a nice picture showing an example what can go wrong. But if you want to keep it simple, that's the way to go.

元启发式，从确定性算法的结果开始。这会给你一个非常好的结果在合理的时间内，比人类把拿出更好。根据你有多少时间给它的问题，它可能是也可能不是最佳的解决方案的难度。有一对夫妇图书馆在那里，如 Drools的规划师（开源Java）。

Meta-heuristics, starting from the result of a deterministic algorithm. This will give you a very good result in reasonable time, better than what humans come up with. Depending on how much time you give it and the difficulty of the problem it might or might not be the optimal solution. There are a couple of libraries out there, such as Drools Planner (open source java).

这篇关于包装问题重新的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！