我面临以下问题:

给定

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

  • 目标:
  • 分配(查找位置)正方形,以使包含在所有正方形中的总点数权重最大化。

  • 注意:
  • 正方形应与轴平行
  • 正方形可能会重叠,但是封闭的权重不会被计算一次以上。

  • 我正在寻找最佳作业。

    我的问题:
  • 这是一个已知的问题(它有名字吗?以前有没有研究过?)。
  • 有什么想法如何处理吗?

  • (我可能会提起我尝试过的方法。由于我正在寻找最佳分配,因此我的启发式想法并不真正相关。目前,我还不知道如何找到最佳分配)。

    最佳答案

    这是加权maximum coverage problem的几何特例。一般的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_iy_j的含义是是否覆盖点j。构造S_i s的最简单三次算法是枚举其左下顶点的x坐标等于某个点的坐标,而y坐标等于某个(可能是其他)点的坐标的正方形,因为每个其他正方形都可以向上滑动并/或在不牺牲覆盖率的情况下向右移动。

    关于algorithm - 给定平面上的加权点,找到U形的位置,以使封闭的总重量最大,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18460126/

    10-12 17:25
    查看更多