目标定位算法

Question

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

我有一个n×m(像素)大小的空间，上面有p个预先存在的矩形物体。现在，我想在这个空间中放置q(相同大小的)新对象，而不需要任何重叠。

我想出的算法：

1. 创建大小为[(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]的数组A
2. 迭代p中的所有元素，并针对每个元素： mark all fields in A[][] as occupied, where the element "lies"
3. 将Q中的所有元素放置在A中字段未标记的相应位置

(孩子，我希望我能让你理解.)

有什么更好的方法吗？任何帮助都是非常感谢的！

Answer 1

从互联网上的简单搜索来看，最优矩形包装似乎是一个NP-硬问题。我猜学术界的聪明人找到了一些近似算法，所以这是谷歌搜索的一种选择。

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

1. 根据对象的宽度将其划分为大小。
2. 试着把它们从最大到最小逐行放置。

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

Answer 2

如果我理解这个问题，听起来你在寻找一种“最优”的垃圾桶包装算法(也就是背包问题)。这是一个NP完全的问题，尽管你的描述听起来像是你可以用暴力强迫你的方式找到一个最优的解决方案。

Answer 3

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

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