是否有任何算法可以帮助最佳地找到最小数量的矩形以包含分布在笛卡尔表面上的一定数量的项目（每个项目都是具有 x 和 y 坐标的点）？矩形必须与 Ox 轴正交且底部段位于 Ox 轴上，并且每个矩形的面积必须小于给定值 M。
问问题
163 次
1 回答
1
不是一个完整的解决方案，而是问题的简化：假设所有点 P 都在一般位置并且在 x 坐标上排序。
然后通过找到x >= fx将 P 划分为不相交集的 F 个垂直栅栏（形式为 ）来形成解决方案。
然后每个集合可以被一个轴对齐的矩形覆盖，其中集合中的第一个和最后一个点确定矩形的宽度，集合中具有最高 y 坐标的点确定高度，从而确定表面大小的矩形。
显然，现在的诀窍是选择栅栏，使栅栏的数量（以及矩形的数量）最小化，同时将所有矩形的总表面尺寸保持在允许的最大值以下。
编辑可能可以使用动态编程解决
放置 F 栅栏的问题。
到目前为止，这是我想出的：
如果是这样，则最多有 |P|-1 个栅栏位置；这些可能会成为动态规划表中的列。动态规划表中的每一行都应该表示使用了一个额外的栅栏（请记住，我们试图找到栅栏数量最少的结果）。然后，每个单元格 (X, Y) 将代表在前 X 个可用位置上精确分布 Y 栅栏的最佳解决方案（就总矩形大小而言）。但是，我在查看表格的相邻单元格如何（或是否）有助于确定特定单元格的值时遇到了一些问题。
编辑2：忘记这一点，我认为动态编程方法是不可能的。这是因为我认为不可能逐步构建最佳解决方案（通过添加另一个点或栅栏，最佳解决方案配置可能会完全改变）。这也将排除贪婪的方法。
我能想到的唯一想法，虽然从算法的角度来看没有那么壮观，但它是一种随机方法，例如用于分布栅栏的模拟退火。它不能保证最佳解决方案，但您应该能够非常接近它。
编辑 3：为了回应这篇文章下的反应，我们不一定需要最好的解决方案，而是选择一个“相当不错”的解决方案，并应用你现在正在学习的东西。
无论如何，您可能需要从左到右对所有点进行排序。
一个贪婪的解决方案可能是定义第一个矩形，使其包含最左边的点。接下来，展开矩形，使其包含右侧的点。继续添加下一个点，直到矩形超过其最大尺寸。在这种情况下，从一个新的矩形开始，然后再次开始添加点，等等。
获得解决方案的一种分而治之的方法可能是从覆盖所有点的矩形开始。显然，这个矩形超过了最大尺寸 M，所以你可以根据一些启发式方法将它垂直分成 2 个较小的矩形 Ml 和 Mr（例如，正好在中间，或者在两个后续点相距最远的点）。以相同的方式递归处理 Ml 和 Mr，或者再次拆分矩形，或者如果找到的矩形 <= M，则将找到的矩形报告为结果的一部分。
请注意，对于这两种方法，对于某些人为的配置，结果可能是任意的，但总的来说，解决方案应该是“好的”。
于 2012-11-26T10:49:22.253 回答