在2d中用n个其他对象覆盖一个形状的算法

Question

您好我正在寻找一个给定形状与其他n个对象的算法。我看到了一些装箱算法，但他们试图将所有物体完美地放在给定容器内。在我的情况就像

如果有人可以帮助我，或引导我，我可以得到有关这个问题的信息将是伟大的。

Answer 1

要回答这个问题的部分原因，问题是NP -complete，因为它是Partition问题的几何概括。给定一个列表整数{a_1,...,a_n}的 和taget总和

S := (a_1 + ... + a_n)/2 

可以通过使用尺寸

1 * a_i 

的n矩形在{1,...,n}每个i和目标来生成在问题的问题的一个实例面积大小

2 * S. 

较小的矩形可以覆盖（其中这种情况与适合进入）较大的矩形相同当且仅当分割的实例允许分割成两个总数相等的子集。

Answer 2

这个问题可以很容易地减少设置覆盖问题。 link

考虑一个假想的网格平面上绘制这些数字。现在从大图中构建一个网格广场集合U。

现在对于n个小图中的每一个构造类似的集合，这些集合是U的子集。从这些套件中删除不在U中的多余元素。

现在，您只需要使用刚创建的n个子集的U的集合封面。如果您正在寻找最小的套盖，它的NP-complete。

您可能希望为集合覆盖问题选择一些近似解决方案。

Approximation algorithms for Set Cover

Approximating Set Cover