1

我有一个 (m*n) 矩阵，其中包含 3 个不同的点。我必须找到最小的移动次数，以使所有 3 个点在矩阵内的一个点处收敛。

到目前为止我尝试过的解决方案：

  • 蛮力解决方案：尝试矩阵中的所有点，从给定的 3 个点中找到需要最小移动的点。
  • 将三个点绑定为一个三角形，并尝试该区域中的点。这更有可能是这个三角形的质心。

我想了解针对此问题的其他优化解决方案。谢谢。

4

3 回答 3

1

每次移动都会将 x 或 y 坐标更改 +/- 1。垂直和水平距离是独立的。因此，首先将点引到一个 x 坐标，然后是 y 坐标。最优化的方法是将具有最小和最大 x 的点移动到第三个点的 x 位置。对 y 重复同样的操作，你就完成了。

这样，最终点的坐标是 x 轴上中点的 x 坐标和 y 轴上中点的 y 坐标（虽然可以有很多这样的点，但这必须是最小化集之一）。（如果它们重叠，显然任何一个重叠坐标都将是中间坐标）。

以编程方式获取一组 x 值，删除最大值和最小值，与 y 相同，您将得到最接近的点。

于 2013-07-03T03:24:26.647 回答
0

我认为这是 http://en.wikipedia.org/wiki/Steiner_tree_problem 的变体之一-可能是http://en.wikipedia.org/wiki/Rectilinear_Steiner_tree问题。这看起来很吓人，我会坚持尝试三角形内的所有点。

实际上，只有一点会聚在一个点上，我认为 sashkello 是正确的

于 2013-07-03T03:54:36.053 回答
0

对于曼哈顿距离：

只需将 3 个点的中间 x 坐标和中间 y 坐标作为目标。中间我的意思是排序坐标的中位数。

例子：

输入：(1,5), (2,4), (3,6)

x 点是1,2和3(排序到1, 2, 3)。中间的是2.

y 点是5,4和6(排序到4, 5, 6)。中间的是5.

因此，最小化距离的点是(2,5)。

证明：

如果我们从上述点开始向任何方向移动，到我们要移动的点的距离会减少，到其他两个点的距离会增加，因此每移动 1 会导致总减少1 但总共增加 2。一旦我们移过最后一个点，所有 3 个距离都会增加，因此总增加将是 3，没有减少。因此，任何移动都会导致距离增加，因此上述点是最佳的。

对于欧几里得距离：

（我现在意识到你说的是最小移动，因此这可能不是你想要的）

这有点复杂。它涉及最小化这个方程：

sqrt((x-x1)^2 + (y-y1)^2) + sqrt((x-x2)^2 + (y-y2)^2) + sqrt((x-x3)^2 + (y-y3)^2)

由于sqrt's，不能通过说x和y是不同的来简化等式。

但是，贪婪的方法可能会奏效：

  • 选择任何一点（也许使曼哈顿距离最小的点是一个好的开始）。
  • 虽然采摘点的相邻点之一会导致欧几里得较低的距离，但选择该点。
于 2013-07-03T08:48:57.777 回答