3

有一些 n 个点位于 2d 网格中。要求是将一个项目从所有这些点（n-1 个点）移动到一个点（在 n 个点的集合中），以便将所有项目移动到该点的成本将是最小的。如果有多个这样的点，那么我们可以随机选择任何点。搬家费用计算如下。

成本计算公式

如果有一个点，则将对象从所有 8 个相邻点(x,y)移动所需的成本为 1 个单位(x,y){(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1),(x,y-1),(x-1,y-1),(x,y-1),(x+1,y-1)}

有人可以为此建议任何 O(N) 算法吗？我已经尝试过 O(N2) 算法（比如取每一对并计算成本）。

4

3 回答 3

2

听起来您想将所有点移动到“中心”，其中中心被定义为总成本值最小的点。对于三点，我认为答案在三角形的质心附近。质心是我们通过简单地平均所有 3 个 x 值和所有三个 y 值得到的点。

扩大到三分以上，我认为平均分要么是正确答案，要么接近正确答案。如果您使用的是点之间的欧几里得距离公式，那么我相当肯定您所寻求的点只是平均值。但是您正在使用一些修改后的出租车几何形状，这使得 45 度角的计数“少于”应有的值。根据您的定义，从 (0,0) 到 (5,5) 的成本是 5，而不是使用标准几何图形的 5 sqrt(5)（大约多 40%）。但是对于水平或垂直移动，指标是相同的。那么，我的快速猜测与正确答案相差多远？如果您可以对半径进行一些估计，那么我建议使用此算法：

  • 计算机平均点（在 O(n) 时间内运行）
    C = 新点（平均（xVals），平均（yVals））
  • 计算机半径 - 对真实答案与快速欧几里得答案的距离的一些估计。
  • 考虑该半径内的所有点，看看它们产生的总成本是否低于 C。

最后一项在 O(r^2) 中运行，只要你能证明 r 远小于 n，你就有一个很好的解决方案。

于 2012-06-14T15:04:50.987 回答
0

我的猜测是 O(n) 解决方案是不可能的。如果输入数据集的所有点都近似于一个圆，那么算法似乎必须检查每个点以查看它是否是最佳解决方案。

现在，可能有很好的算法可以及时处理与 n 成比例的“正常”情况。
AO(N log N) 启发式排序点以进行最佳优先搜索似乎很可能。A-star 甚至可能是可能的，但似乎更难。

于 2012-06-14T16:50:24.243 回答
0

我认为您可以在线性时间内计算 n 个点的质心，然后在线性时间内计算最接近该质心的点。

获得质心：

center = points[0];
for (int i=1; i<points.length; ++i) {
  center = massCenter(center, i+1, points[i]);
}

Point massCenter(Point currCent, int weight, Point p) {
  double x = (currCent.x * weight + p.x)/(weight+1);
  double y = (currCent.y * weight + p.y)/(weight+1);
  return new Point(x, y);
}

为了正确计算中心，我为该点假设了一个双坐标。

于 2012-06-14T14:59:36.857 回答