包含笛卡尔曲面项目的算法

Question

包含笛卡尔曲面项目的算法

algorithm

4

是否有一种算法可以帮助优化地找出最少的矩形来包含分布在笛卡尔平面上的某个数量的物品（每个物品都是具有x和y坐标的点）？矩形必须与Ox轴垂直，并且底部线段必须沿着Ox轴，每个矩形的面积必须小于给定值M。

- b1nnar

这个问题最好在http://programmers.stackexchange.com/上提问，那里更多关注算法等问题，而Stack则更多关注你正在处理的代码。 - Craig

1

我认为你只能寻找一个表面积最小的覆盖方式，针对给定数量的矩形 - 否则你将会选择n个零面积的矩形来覆盖n个点... - Darren Engwirda

我们需要处理多少个点 - 是否可以使用暴力解决方案，还是您真的需要一个复杂的算法？矩形是否允许相交？ - Leon Bouquiet

1

另外，因为你说“垂直于并且底部段在Ox轴上”，这听起来像是想用条形图来近似一个点云...？ - Leon Bouquiet

Icfseth，你是对的。这不是关于矩形的面积 - 这是我的错误。关于矩形的面积的唯一限制是每个矩形的面积必须小于给定值M。应用此约束条件，问题就是找到最小数量的这样的矩形，以便将所有给定点包围起来。 - b1nnar

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Leon Bouquiet · Accepted Answer

这不是一个完整的解决方案，而是问题的简化：

假设所有点P都处于一般位置并按x坐标排序。

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

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

显然，关键是选择栅栏的方式，使得栅栏的数量（因此也是矩形的数量）最小化，同时保持所有矩形的总表面积低于允许的最大值。

编辑
~~可能使用动态规划可以解决放置F个栅栏的问题。~~ 这是我目前想出的：

如果是这样，最多会有|P|-1个栅栏位置；这些可能会成为动态规划表中的列。动态规划表中的每一行应该表示使用一个额外的栅栏（记住，我们正在尝试找到使用最少数量的栅栏的结果）。然后，每个单元格（X，Y）将表示在前X个可用位置上精确分配Y个栅栏的总矩形大小的最优解。然而，我有点看不出表格的相邻单元格如何（或是否）有助于确定特定单元格的值。

编辑2：算了吧，我认为动态规划方法不可行。这是因为我认为无法逐步构建最优解（通过添加另一个点或栅栏，最优解配置可能会完全改变）。这也排除了贪心方法。

我唯一能想到的，虽然从算法的角度来看略微不太起眼，是一种随机化方法，例如模拟退火，用于分配栅栏。它不能保证最优解，但您应该能够接近它。 编辑3：针对本帖下的反应，我们是否可以不一定要求最佳解决方案，而是选择一个“相当不错”的解决方案，并应用您现在正在学习的内容。

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

贪心算法的解决方案可以是定义第一个矩形，使其包含最左边的点。接下来，扩展矩形以包括其右侧的点。继续添加下一个点，直到矩形超过其最大尺寸。在这种情况下，重新开始一个新的矩形并再次开始添加点，以此类推。

通过分治法获得解决方案的方法可以是从覆盖所有点的矩形开始。显然，该矩形超出了最大尺寸M，因此根据某些启发式方法（例如完全在中间或在两个连续点之间距离最远的点处）将其垂直分成2个较小的矩形Ml和Mr。以相同的方式递归处理Ml和Mr，再次分割矩形或将找到的矩形作为结果的一部分报告，如果它<= M。

请注意，对于这两种方法，结果可能对于某些刻意构造的配置任意糟糕，但通常解决方案应该是“可以”的。