寻找两个距离最远的点的算法

Question

我正在制作一款赛车游戏，需要使用一种算法。地图/关卡/赛道是随机生成的，因此我需要找到起点和终点两个位置，以利用地图的大部分区域。

• 该算法将在二维空间内运作
• 从每个点出发，只能向四个方向之一移动：上、下、左、右
• 点只能是阻塞或非阻塞的，只有非阻塞的点才能被遍历

关于距离的计算，它不应该是“鸟的路径”（缺乏更好的词语）。如果A和B之间有墙壁（或其他阻塞区域），则它们之间的路径应该更长。

我不确定从哪里开始，欢迎评论，最好使用伪代码提供解决方案。

编辑：好的，在查看gs的代码后，我又尝试了一次。这次我使用的是C++，而不是Python。但即使我阅读了Dijkstra算法、floodfill和Hosam Alys的解决方案，我仍然没有发现任何关键的区别。我的代码仍然有效，但速度不如你所说的那么快。完整源代码位于pastie上。唯一有趣的行（我猜）是Dijkstra变体本身，位于第78-118行。

但速度不是主要问题。如果有人能够友好地指出算法之间的差异，我将非常感激。

• 在Hosam Aly的算法中，唯一的区别是他从边界开始扫描，而不是每个节点吗？
• 在Dijkstra算法中，你会跟踪并覆盖行走的距离，但在洪水填充算法中却不是这样，这就是其中的区别吗？

- mizipzor

---

你的地图/关卡/轨道长什么样子？例如，它是矩形的吗？可以将其分成均匀大小的正方形吗？ - Hosam Aly

地图可以有多大？最多有多少个点？ - Hosam Aly

它不会很大，但理论上没有限制。在我的应用程序中，150-200个点在两个轴上被认为是“大”的。 - Mizipzor

你需要它多快呢？我猜在O(n^3)内的任何速度都可以，不是吗？ - Hosam Aly

你的实现现在工作了吗？ - Georg Schölly

Answer 1

假设地图是矩形的，您可以循环遍历所有边界点，并开始洪水填充以查找距离起始点最远的点：

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

我猜这个时间复杂度应该是O(n^2)。如果我没错的话，它应该是(L+W) * 2 * (L*W) * 4，其中L是地图的长度，W是宽度，(L+W)*2代表周长上的边界点数，(L*W)是点数，4是洪水填充最多访问一点的假设（从所有方向）。由于n等于点数，因此这相当于(L+W)*8*n，应该比O(n^2)更好。 （如果地图是正方形，则顺序将为O(16n^1.5)。）

更新：根据评论，由于地图更像是迷宫（而不是我最初想到的简单障碍物），您可以使用上述相同的逻辑，但检查地图上的所有点（而不仅仅是边界上的点）。这应该是O(4n^2)，仍然比F-W和Dijkstra更好。

注意：对于这个问题，泛洪填充更加适用，因为所有顶点仅通过4个边直接连接。地图的广度优先遍历可以相对快速地产生结果（仅需O(n)）。我假设每个点都可以从其4个邻居中的每一个进行泛洪填充检查，因此上述公式中的系数。

更新2：我感谢所有关于这个算法的积极反馈。特别感谢@Georg进行他的评论。

附注：欢迎任何意见或更正。

- Hosam Aly

---

不能保证所有边界点都属于最长距离。虽然可能性很大，但取决于迷宫生成器，可能会有其他解决方案。 - Georg Schölly

地图上不会有太多障碍物，但边缘会非常复杂。这些边缘本身很少是直线。 - Mizipzor

@mizipzor：实现 F-W 应该相当简单。for (int i = 0; i < nPoints; ++i) for (int j = 0; j < nPoints; ++j) for (int k = 0; k < nPoints; ++k) distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]); - Hosam Aly

你可以在答案中看到我的结果。正如你所说，这是关于n的平方。 - Georg Schölly

@mizipzor，很高兴你选择了我的算法。你能分享一下你的地图（如果可能的话还有算法实现）吗？我或许可以进一步优化它。 - Hosam Aly

Answer 2

关于Floyd-Warshall或Hosam Aly的简单算法的问题的跟进：

我创建了一个测试程序，可以使用这两种方法。以下是文件：

• 迷宫创建者
• 查找最长距离

在所有测试案例中，Floyd-Warshall明显慢得多，可能是因为有限的边数帮助该算法实现。

这些是时间，每次场地都是四倍的，其中3个场地是障碍物。

大小          Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

Hosam Aly的时间似乎是二次方的，因此我建议使用那个算法。此外，Floyd-Warshall的内存消耗是n²，明显超出了需要的范围。如果您知道为什么Floyd-Warshall如此慢，请留下评论或编辑此帖子。

PS：我很久没有写过C或C ++，希望我没有犯太多错误。

- gs

---

仅仅从你的时间表上看，你编写的H-A算法是O(n^2)，而你编写的F-W算法是O(n^3)。可能你标记错了一些东西？ - casualcoder

@casualcoder：据我所知，这是正确的。 "H-A"只是广度优先搜索，其时间复杂度为O(n)，因此运行n次的时间复杂度为O(n^2)。似乎在稀疏图上（就像我们这里的每个顶点只有4条边），F-W实际上相当慢，但对于密集图来说它要快得多。 - j_random_hacker

@gs：你的代码看起来没问题，但有一个小错误：H-A代码将距离存储在检查“.”字符表示位置“未阻塞”的相同位置 - 你需要为此使用单独的数组，否则当距离可以>=46（ASCII码为'.'）时，你的代码将失败！ - j_random_hacker

@randomhacker：这就是距离为负数的原因。如果我再写一遍代码，我会使用单独的数组。这样也比每次复制旧地图更快。 - Georg Schölly

我还没有成功，但我怀疑它是否有效，因为在这种情况下，只有4条边会被尝试，而不是起点和终点之间的所有边。 - Georg Schölly

Answer 3

看起来您需要的是由图直径分离的终点。 一种相当好且易于计算的近似方法是选择一个随机点，找到距离该点最远的点，然后找到那里距离最远的点。 这最后两个点应该接近最大分离。

对于矩形迷宫，这意味着两次洪水填充可以让你得到一个相当不错的起点和终点。

- Boojum

---

如果例如选择的点被墙壁包围且只能到达其他3个点，那么这可能会产生非常糟糕的结果。 - Georg Schölly

在这种情况下，这是可以的，因为所有节点都将连接在一起。这是从地图生成方式来保证的。 - Mizipzor

Answer 4

我删掉了原来推荐 Floyd-Warshall 算法的帖子。:(

gs 进行了真实的基准测试，结果发现对于典型地图尺寸，F-W 比 Hosam Aly 的“泛洪填充”算法慢得多！所以尽管 F-W 是一种很酷的算法，并且在稠密图上比 Dijkstra 的算法快得多，但我不能再推荐它用于 OP 的问题，因为该问题涉及非常稀疏的图（每个顶点只有 4 条边）。

记录一下：

• Dijkstra算法的高效实现对于具有E条边和V个顶点的图需要O(Elog V)的时间。
• Hosam Aly的“洪水填充”是一种广度优先搜索，其时间复杂度为O(V)。这可以看作是Dijkstra算法的一个特殊情况，在该情况下，任何顶点的距离估计值都不能被修正。
• Floyd-Warshall算法的时间复杂度为O(V^3)，非常容易编码，并且在稠密图（顶点通常连接到许多其他顶点的图）中仍然是最快的。但它不适用于OP的任务，因为涉及到非常稀疏的图。

- j_random_hacker

---

我支持这个，也删除了我关于F-W的帖子。 - Georg Schölly

它有13个赞，我不认为足够多的人会踩它。 - Georg Schölly

好吧，我不能对自己的帖子进行踩，而且有7个赞同，要让它被踩掉需要一段时间。删除它可以避免误导他人。 - j_random_hacker

Answer 5

在他的论文“On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs [pdf]”的第一部分中，Raimund Seidel提供了一种简单的方法，使用矩阵乘法计算无权、无向图（正是你想要的）的所有对之间的距离矩阵。

输入是邻接矩阵，输出是所有对之间的最短路径距离矩阵。运行时间为O(M(n)*log(n))，其中n为点数，M(n)是矩阵乘法算法的运行时间。

如果您需要，该论文还提供了计算实际路径的方法（在相同的运行时间内）。

Seidel的算法很酷，因为运行时间不受边数影响，但我们实际上在这里并不关心，因为我们的图是稀疏的。然而，如果您想要所有对距离矩阵，这仍然可能是一个不错的选择（尽管略劣于n^2的运行时间），并且这也可能比迷宫上的泛洪算法更容易实现和调试。

以下是伪代码：

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

为了获得距离最大的点对，我们只需返回argmax_ij(d_ij)。

- Imran

---

有趣的是，根据维基百科的说法，子O(n^3)矩阵乘法算法很难编写，并且具有很大的开销。O(n^2.376)算法“对于可以适应今天计算机的矩阵来说并不实用”。因此，在实践中，您将使用O(n^3)算法，使其比F-W更慢。 - j_random_hacker

Answer 6

完成了一个Python的Dijkstra算法问题的模拟。代码有点长，所以我把它发布到了其他地方：http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

在我设置的规模下，运行该算法需要大约1.5秒钟才能处理一个节点。对每个节点运行需要几分钟。

然而似乎并不起作用，它总是显示左上角和右下角为最长路径；58个瓷砖。当然，在没有障碍物的情况下是正确的。但即使添加了几个随机放置的障碍物，程序仍然找到了那个最长的路径。也许这仍然是正确的，没有更高级的形状很难测试。

但也许它至少可以展示我的雄心壮志。

- mizipzor

---

这个算法使用的是n^3，因此不是一个很好的算法。使用Hosam Aly的算法。 - Georg Schölly

看起来我至少现在让我的代码工作了。但是它需要很长时间。我明天会研究你的代码@gs。希望我能让它更快。http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other#refactor_144521 - Mizipzor

Answer 7

好的，“Hosam算法”是一种带有节点预选的广度优先搜索算法。 在这里不应该应用Dijkstra算法，因为你的边没有权重。

区别非常关键，因为如果边的权重不同，你需要保持很多选择（备选路径）并在每一步检查它们。这使得算法更加复杂。 使用广度优先搜索，你只需按照找到它们的顺序探索所有边缘，以确保找到每个节点的最短路径。

所以基本上区别在于Dijkstra必须“回溯”并查看它之前探索过的边缘，以确保它正在遵循最短路线，而广度优先搜索始终知道它正在遵循最短路线。

此外，在迷宫中，外部边界上的点不能保证是最长路径的一部分。 例如，如果你有一个呈巨大螺旋形的迷宫，但外部末端返回到中心，你可以在螺旋的中心和末端都有两个点！

因此，做到这一点的好方法是从每个点使用广度优先搜索，但在搜索之后删除起始点（您已经知道所有到它和从它出发的路径）。 广度优先的复杂度是O(n)，其中n = |V|+|E|。我们对V中的每个节点进行一次操作，因此它变成了O(n^2)。

- Rutger Prins

Answer 8

根据您的描述，这似乎是一个迷宫路径规划问题。可以尝试使用Lee算法。关于VLSI设计中的布局和布线问题的书籍可能会对您有所帮助 - Sherwani的“VLSI物理设计自动化算法” 是不错的选择，而且您可能会发现Sait和Youssef的“VLSI物理设计自动化”也很有用（在Google版本中价格更便宜...）

- Yuval F

---

迷宫路由不需要定义起点和目标吗？或者您建议我对每个节点执行Lee算法，类似于提出的Dijkstra解决方案？ - Mizipzor

这对于你的问题来说会太慢了。这个算法可以找到路径，但它并没有被优化来寻找距离。 - Georg Schölly

迷宫路由需要定义起点和目标点。它的优势在于考虑了障碍物。我建议您使用启发式算法 - 从具有最大“鸟飞行”距离的点对开始，然后为这些点对运行李氏算法。 - Yuval F

Answer 9

如果您的对象（点）不经常移动，您可以在比O(n^3)时间短得多的时间内执行此类计算。

您所需要做的就是将空间分成大网格并预先计算网格间距离。然后选择占据最远网格的点对只是一个简单的表查找问题。在平均情况下，您只需要逐对检查一小组对象。

如果距离度量是连续的，则此解决方案有效。因此，例如地图中有许多障碍物（如迷宫），则此方法可能会失败。

- bgbg

---

我可以问一下，当地图像迷宫一样时，这是如何可能的吗？ - Hosam Aly

对于每个网格，您需要计算出入口/出口点（用于穿越）以及子网格内任何感兴趣的点到该网格出口的距离。这里列出的方法也不是最糟糕的。 - Clinton Pierce