algorithm - 对象定位算法

Question

我想知道这个问题是否有“最佳”解决方案：

我有一个anxm（像素）大小的空间，上面有p个预先存在的矩形 - 上面有各种大小的对象。现在我想在这个空间中放置 q 个（相同大小的）新对象而没有任何重叠。

我想出的算法：

1. 创建数组 A[][] 的大小[(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. 迭代 p 和每个元素的所有元素：

   mark all fields in A[][] as occupied, where the element "lies"

3. 将 q 中的所有元素放在未标记 A[][] 中的字段的相应位置

（男孩，我希望我能理解这一点......）

有没有更好的方法来做到这一点？任何帮助将不胜感激！

Answer 1

如果我理解这个问题，听起来您正在寻找一种“最佳”装箱算法（又名背包问题）。这是一个 NP-Complete 问题，尽管您的描述听起来像是您可能会蛮力找到最佳解决方案。

Answer 2

从互联网上的简短搜索来看，最佳矩形包装似乎是一个NP-hard问题。我猜想学术界的聪明人为此找到了一些近似算法，因此它是谷歌搜索的一个选择。

但我会尝试先让这个简单的方法起作用：

1. 根据对象的宽度将对象分成大小
2. 尝试将它们从最大到最小逐行放置。

我的猜测是，在许多情况下，这种天真的解决方案会奏效。

Answer 3

我知道这不是您问题的具体答案，但它可能对研究和/或深入研究graphviz源代码很有用。graphviz 提供了许多布局模型，包括尝试最小化全局能量函数的neato。

维基百科有一些基于力的算法的伪代码。