寻找移动成本最小化的点的算法

Question

在二维网格中有n个点。要求将所有这些点中的一个物品（n-1个点）移动到单个点（在n个点集合中），以便将所有物品移动到该点的成本最小。如果有多个这样的点，则可以随机选择任何一个点。移动成本计算如下。

成本计算公式：

如果点在(x,y)处，那么将对象从(x,y)移动到所有8个相邻点{(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)}所需的成本为1个单位。

有没有人能提供任何O(N)算法？我已经尝试了O(N2)算法（例如取每对并计算成本）。

- Alok

---

@Alok 但是既然你要求算法，那么这将是与语言无关的。 - Alexis Pigeon

如果坐标上没有点，移动的成本是多少？ - Hurda

@Hurda，我们正在移动物品存在的地方。如果是空的话，那么移动物品就没有意义了。你可以换个思路考虑。有N个仓库，我想把每个仓库里的一个物品都倒到一个特定的仓库里，使得总移动成本最小。 - Alok

@Alok 那么你要移动的每个坐标都必须被点占据吗？我假设对象等同于你问题中的物品。那么我们可以假设所有的点都通过其他点相互连接？ - Hurda

@Hurda，你为什么要考虑互连性呢？我们可以用更简单的方式来思考。我只想找到那个仓库，从其他n-1个仓库移动物品的成本最低。无论你选择哪个点，它是否被占用都无所谓。你只需要在点集中找到一个或多个这样的点即可。 - Alok

Answer 1

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

在超过三个点的情况下，我认为平均点可能是正确答案或接近正确答案。如果您正在使用点之间的欧几里德距离公式，那么我相当确定您寻找的点只是平均值。但是，您正在使用一些修改后的出租车几何，使45度角计数“不足”它们应该计数的次数。从（0,0）到（5,5）的成本根据您的定义为5，而使用标准几何学则为5 sqrt（5）（大约多40％）。但对于水平或垂直移动，指标是相同的。因此，正确答案与我的快速猜测相差多远？如果您可以在半径上获得一些估计值，则建议使用以下算法：

计算平均点（运行时间为O（n））

C = new Point（average（xVals），average（yVals））

计算半径-一些估计值，即真实答案距快速欧几里德答案有多远。
考虑半径内的所有点，并查看它们是否产生比C更低的总成本。
这最后一项运行时间为O（r ^ 2），只要您可以表明r远小于n，您就有一个很好的解决方案。

- Thorn

---

Thom你的建议很好，但在多个点位于同一坐标的情况下会失败。对我来说重要的不是质心，即使我选择距离质心最近的点，有些测试用例也会失败。 - Alok

我不明白为什么具有相同坐标的多个点会使答案远离质心。这不应该影响欧几里得情况。就你寻求的实际答案而言，通常它不会是质心。但是通过查看一些示例，您能否估计答案距离质心有多远？这个最大距离就是我在上面答案中称之为r的距离。 - Thorn

Answer 2

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

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

- dave jones

---

你能解释其中任何一个算法吗？我的意思是如何修改上述问题陈述以适用于这些算法。 - Alok

Answer 3

我认为你可以在线性时间内计算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);
}

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

- Attila

---

它并不保证质心会导致最小成本。 - Alok

@Alok - 质心确实是整体最小距离，因此移动成本也应该尽量减少。 - Attila

这个问题中定义了不同的距离。Alok正在使用非欧几里得距离。 - Thorn

@Thorn - 你说得对，我没有考虑到对角线移动与垂直/水平移动具有相同的代价。 - Attila