7

我面临以下问题：

给定

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

目标：

  • 分配（查找位置）方格，以使包含在所有方格内的总点的权重最大化。

笔记：

  • 正方形应该是轴平行的
  • 方块可能会重叠，但包含的权重不会被计算多次。

我正在寻找最佳分配。

我的问题：

  • 这是一个已知问题吗（它有名字吗？之前有没有探索过？）。
  • 任何想法如何处理它？

（我可能会提到我尝试过的事情。由于我正在寻找最佳分配，我的启发式想法并不真正相关。此时我不知道如何找到最佳分配）。

4

1 回答 1

2

这是加权最大覆盖问题的几何特殊情况。一般的 MCP 是 NP 难的，我怀疑这种特殊情况也是如此，尽管与一般情况不同，它可能具有有效的多项式时间逼近方案。但是，您需要一个最佳解决方案，因此我建议的第一件事是将链接的 Wikipedia 文章中的整数线性规划公式提供给 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 的最简单的三次算法S_i是枚举其左下顶点的 x 坐标等于某个点的坐标且 y 坐标等于某个（可能是其他）点的坐标的所有正方形，因为每个其他正方形都可以向上滑动和/或向右而不牺牲覆盖范围。

于 2013-08-27T13:31:16.810 回答