algorithm - 笛卡尔曲面项包含算法

Question

是否有任何算法可以帮助以最佳方式找到最少数量的矩形以包含分布在笛卡尔曲面上的一定数量的项目(每个项目都是一个具有 x 和 y 坐标的点)？矩形必须正交于 Ox 轴并在 Ox 轴上具有底部线段，并且每个矩形的面积必须小于给定值 M。

Answer 1

不是完整的解决方案，而是对问题的简化: 假设所有点P都在一般位置，并按x坐标排序。

然后通过找到 F 垂直栅栏(形式为 x >= fx )来形成解决方案 将 P 划分为不相交的集合。

然后每个集合可以被一个轴对齐的矩形覆盖，其中集合中的第一个点和最后一个点确定矩形的宽度，集合中具有最高 y 坐标的点确定高度，特此确定矩形的表面尺寸。

显然，现在的诀窍是选择栅栏，使栅栏的数量(以及矩形的数量)最小化，同时将所有矩形的总表面大小保持在允许的最大值以下。

编辑
可能放置 F 栅栏的问题可以使用动态规划来解决。 这是我到目前为止想出的:

如果是，最多有|P|-1个围栏位置；这些可能会成为动态规划表中的列。动态规划表中的每一行都应该代表使用一个额外的栅栏(记住，我们试图找到栅栏数量最少的结果)。然后，每个单元格 (X, Y) 将代表在前 X 个可用位置上精确分布 Y 个栅栏的最佳解决方案(根据总矩形大小)。但是，我在查看表格的相邻单元格如何(或是否)有助于确定特定单元格的值时遇到一些问题。

编辑 2:算了吧，我不认为动态编程方法是可能的。这是因为我认为不可能逐步构建最佳解决方案(最佳解决方案配置可能会通过添加另一个点或栅栏而完全改变)。这也将排除贪婪的方法。

我能想到的唯一想法是一种随机方法，例如 Simulated annealing，尽管从算法的角度来看不那么引人注目。用于分发围栏。它不能保证最佳解决方案，但您应该能够非常接近它。

编辑 3:针对这篇文章下的 react ，我们不一定需要最佳解决方案，而是寻求“相当不错”的解决方案怎么样相反，立即应用您正在学习的内容。

无论如何，您可能需要从左到右对所有点进行排序。

贪婪的解决方案可能是定义第一个矩形，使其包含最左边的点。接下来，展开矩形，使其包含其右侧的点。继续添加下一个点，直到矩形超过其最大尺寸。在这种情况下，从一个新的矩形开始并再次开始添加点，等等。

获得解决方案的分而治之的方法可能是从覆盖所有点的矩形开始。显然，这个矩形超过了最大尺寸 M，因此根据一些启发式方法(例如，恰好在中间，或者在两个后续点相距最远的点)，您将它垂直拆分为 2 个较小的矩形 Ml 和 Mr。以相同的方式递归处理 Ml 和 Mr，要么再次拆分矩形，要么将找到的矩形报告为结果的一部分，如果它 <= M。

请注意，对于这两种方法，对于某些人为的配置，结果可能任意糟糕，但总的来说，解决方案应该是“好的”。