给定平面上的加权点,找到U平方的位置,使得总封闭权重最大化

Question

我遇到了以下问题:

特定

• 欧几里德平面上的一组点,每个点P(x,y,w)具有坐标和相关的正权重.
• 一组U正方形,都具有相同的大小长度L.

目标:

• 为方块分配(找到位置),使得包含在所有方块内的总点重量最大化.

笔记:

• 方块应该是轴平行的
• 方块可能重叠,但封闭的重量不会超过一次.

我正在寻找一个最佳的任务.

我的问题:

• 这是一个已知的问题(它有一个名字吗？它之前是否已被探索过？).
• 任何想法如何处理它？

(我可能会提到我尝试了什么.因为我正在寻找最佳分配,我的启发式思想并不真正相关.此时我不知道如何找到最佳分配).

Answer 1

这是加权最大覆盖问题的几何特例。一般的 MCP 是 NP 难的，我怀疑这种特殊情况也是如此，尽管与一般情况不同，它可能有一个有效的多项式时间近似方案。然而，您想要一个最佳解决方案，因此我建议的第一件事是将链接的维基百科文章中的整数线性规划公式提供给 LP 求解器。

maximize sum_j (w_j * y_j)
subject to
for all i, sum_i x_i <= U
for all j, sum_{i : j in S_i} x_i - y_j >= 0
for all i, x_i in {0, 1}
for all j, 0 <= y_j <= 1

w_j给定每个点的权重j，并且集合S_i是用宽度正方形覆盖点的所有可能性L。的含义x_i是是否S_i选择set。的含义y_j是点是否j被覆盖。构造S_is 的最简单的三次算法是枚举其左下顶点的 x 坐标等于某个点的 x 坐标且 y 坐标等于某个（可能是其他）点的坐标的所有正方形，因为每个其他正方形都可以向上滑动和/或向右移动而不牺牲覆盖范围。