鉴于加权点，找到ü方块的位置，使得总重量封闭将最大化

我面临着以下问题：鉴于加权点，找到ü方块的位置，使得总重量封闭将最大化

鉴于

一组点在欧几里得平面上，每个点P（x，y，w）具有坐标和相关的正权重。
甲集合U的平方，所有具有相同尺寸的长度L.

目标：

分配（查找位置）的平方，以使总点数重量包围内所有的广场将被最大化。

注：

正方形应该是轴平行
正方形可重叠，但在封闭的权重将不会被计算多于一次。

我在寻找最佳作业。

我的问题：

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

（我预期可能谈不上什么都我试过了。因为我正在寻找一个最佳分配，我的想法启发是不是真的重要。在这一点上我不知道如何找到最佳分配）。

来源

2013-08-27 Lior Kogan

请说明您对U square的定义。并且通过包围在所有正方形中，并不意味着这些点应该位于正方形的平面中，而是包含在一组盒子中，其中每一侧由这些轴平行正方形构成，或者与其他相交这样的盒子？ –

@RobertJørgensgaardEngdahl：U是我希望找到最佳位置的同等大小的正方形的数量。正方形与点在同一平面上（这是一个2D问题）。 –

你可以添加一个2D程序应该做的事情的图像吗？ – jambono

这是一个加权maximum coverage problem的几何特例。一般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

的重量每个点j的w_j被给出，并且集S_i是用于覆盖点的宽度L方所有的可能性。 x_i的含义是是否选择了设置S_i。 y_j的含义是是否涵盖点j。构造S_i的最简单的三次算法是枚举所有左下角顶点的x坐标等于某点的y坐标和y坐标等于某个点（可能是其他点）坐标的所有正方形，因为每隔一个正方形可以向上滑动并且/或在不牺牲覆盖范围的情况下向右转。

来源

2013-08-27 13:31:16

感谢David。您是否有机会参考更广泛的构造S_i方法的描述？（使用哪些数据结构等） –

@LiorKogan我没有一个参考，因为我只是想到了它，稍微详细一点，算法是收集和排序点的x坐标，收集并对这些点的y坐标进行排序，对于x坐标中的x，对y坐标中的y进行排序，扫描其他点以查看哪些属于左侧具有x坐标x的宽度L的平方以及其底部有y坐标y，我怀疑在这里使用数据结构会起反作用，因为解决整数程序需要一段时间。 –

鉴于加权点，找到ü方块的位置，使得总重量封闭将最大化

回答

相关问题