算法找出两个点之间距离最大的点

Im looking for an algorithm to be used in a racing game Im making. The map/level/track is randomly generated so I need to find two locations, start and goal, that makes use of the most of the map.

我正在寻找一种可以在我制作的比赛游戏中使用的算法。地图/层/轨道是随机生成的，所以我需要找到两个位置，开始和目标，这两个位置充分利用了地图的大部分。

The algorithm is to work inside a two dimensional space
算法是在二维空间中工作
From each point, one can only traverse to the next point in four directions; up, down, left, right
从每一点出发，只能从四个方向穿过下一点;上,下,左,右
Points can only be either blocked or nonblocked, only nonblocked points can be traversed
只能阻塞或非阻塞点，只能遍历非阻塞点

Regarding the calculation of distance, it should not be the "bird path" for a lack of a better word. The path between A and B should be longer if there is a wall (or other blocking area) between them.

对于距离的计算，不应该是“鸟道”，因为没有更好的词。如果A和B之间有墙(或其他阻塞区域)，则A和B之间的路径应该更长。

Im unsure on where to start, comments are very welcome and proposed solutions are preferred in pseudo code.

我不确定从哪里开始，欢迎评论，建议的解决方案在伪代码中是首选。

Edit: Right. After looking through gs's code I gave it another shot. Instead of python, I this time wrote it in C++. But still, even after reading up on Dijkstras algorithm, the floodfill and Hosam Alys solution, I fail to spot any crucial difference. My code still works, but not as fast as you seem to be getting yours to run. Full source is on pastie. The only interesting lines (I guess) is the Dijkstra variant itself on lines 78-118.

编辑:对。检查完gs的代码后，我又试了一次。我这次用的是c++，而不是python。但是，即使在阅读了Dijkstras算法、洪泛填充和Hosam Alys解决方案之后，我仍然没有发现任何关键的区别。我的代码仍然可以运行，但速度不如您让自己的代码运行得快。全部消息来源在pastie上。唯一有趣的行(我猜)是78-118行上的Dijkstra变体本身。

But speed is not the main issue here. I would really appreciate the help if someone would be kind enough to point out the differences in the algorithms.

但速度不是这里的主要问题。如果有人能指出算法中的差异，我将非常感谢您的帮助。

In Hosam Alys algorithm, is the only difference that he scans from the borders instead of every node?
在Hosam Alys算法中，他从边界而不是每个节点进行扫描的唯一区别是什么?
In Dijkstras you keep track and overwrite the distance walked, but not in floodfill, but thats about it?
在迪克斯特拉，你跟踪和覆盖了步行的距离，但不是在洪水泛滥，但这是关于它吗?

9 个解决方案

#1

Assuming the map is rectangular, you can loop over all border points, and start a flood fill to find the most distant point from the starting point:

假设地图是矩形的，你可以在所有的边界点上循环，然后开始一个洪水填充，从起点找到最远的点:

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

I guess this would be in O(n^2). If I am not mistaken, it's (L+W) * 2 * (L*W) * 4, where L is the length and W is the width of the map, (L+W) * 2 represents the number of border points over the perimeter, (L*W) is the number of points, and 4 is the assumption that flood-fill would access a point a maximum of 4 times (from all directions). Since n is equivalent to the number of points, this is equivalent to (L + W) * 8 * n, which should be better than O(n²). (If the map is square, the order would be O(16n^1.5).)

我想这将是O(n ^ 2)。如果我没有记错的话,这是(L + W)* 2 *(L * W)* 4,其中L是长度和W是地图的宽度,(L + W)* 2代表数量的边界点周边,(L * W)点的数量,和4是假设flood-fill访问一点一最大的4倍(从四面八方)。因为n等于点的个数，所以它等于(L + W) * 8 * n，应该比O(n2)好。(如果地图是正方形，顺序为O(16n1.5)。)

Update: as per the comments, since the map is more of a maze (than one with simple obstacles as I was thinking initially), you could make the same logic above, but checking all points in the map (as opposed to points on the border only). This should be in order of O(4n²), which is still better than both F-W and Dijkstra's.

更新:根据评论，由于地图更像一个迷宫(而不是像我最初想的那样有简单的障碍)，你可以在上面做同样的逻辑，但是检查地图中的所有点(而不是只检查边界上的点)。这应该是O(4n2)的顺序，这仍然比F-W和Dijkstra的好。

Note: Flood filling is more suitable for this problem, since all vertices are directly connected through only 4 borders. A breadth first traversal of the map can yield results relatively quickly (in just O(n)). I am assuming that each point may be checked in the flood fill from each of its 4 neighbors, thus the coefficient in the formulas above.

注:洪水填充更适合这个问题，因为所有顶点都直接通过4个边界连接。广度优先遍历映射可以相对快速地产生结果(仅在O(n)中)。我假设每个点都可以从它的4个邻域的洪水填充中检查，从而得到上面公式中的系数。

Update 2: I am thankful for all the positive feedback I have received regarding this algorithm. Special thanks to @Georg for his review.

更新2:我感谢我收到的关于这个算法的所有积极反馈。特别感谢@Georg的评论。

P.S. Any comments or corrections are welcome.

注:欢迎提出任何意见或更正。

#2

Follow up to the question about Floyd-Warshall or the simple algorithm of Hosam Aly:

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

I created a test program which can use both methods. Those are the files:

我创建了一个可以使用这两种方法的测试程序。这些文件:

maze creator
迷宫的创造者
find longest distance
寻找最长的距离

In all test cases Floyd-Warshall was by a great magnitude slower, probably this is because of the very limited amount of edges that help this algorithm to achieve this.

在所有的测试用例中，Floyd-Warshall的速度都要慢很多，这可能是因为帮助算法实现这一点的边非常有限。

These were the times, each time the field was quadruplet and 3 out of 10 fields were an obstacle.

这是时间，每次田地是四倍，10个田地中有3个是障碍。

Size         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      -

The time of Hosam Aly seems to be quadratic, therefore I'd recommend using that algorithm. Also the memory consumption by Floyd-Warshall is n², clearly more than needed. If you have any idea why Floyd-Warshall is so slow, please leave a comment or edit this post.

Hosam Aly的时间似乎是二次型的，所以我建议使用该算法。Floyd-Warshall算法的内存消耗是n2，显然比需要的多。如果你知道Floyd-Warshall为什么这么慢，请留下评论或编辑这个帖子。

PS: I haven't written C or C++ in a long time, I hope I haven't made too many mistakes.

PS:我已经很久没有写C或c++了，希望我没有犯太多的错误。

#3

I deleted my original post recommending the Floyd-Warshall algorithm. :(

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

gs did a realistic benchmark and guess what, F-W is substantially slower than Hosam Aly's "flood fill" algorithm for typical map sizes! So even though F-W is a cool algorithm and much faster than Dijkstra's for dense graphs, I can't recommend it anymore for the OP's problem, which involves very sparse graphs (each vertex has only 4 edges).

gs做了一个现实的基准，猜猜看，F-W比Hosam Aly的“洪水填充”算法在典型地图大小上要慢得多!因此，尽管F-W是一个很酷的算法，对于密集的图，它比Dijkstra算法要快得多，但对于OP的问题，我再也不能推荐它了，这个问题涉及到非常稀疏的图(每个顶点只有4条边)。

For the record:

备案:

An efficient implementation of Dijkstra's algorithm takes O(Elog V) time for a graph with E edges and V vertices.
Dijkstra算法的有效实现需要O(Elog V)时间来处理具有E边和V顶点的图。
Hosam Aly's "flood fill" is a breadth first search, which is O(V). This can be thought of as a special case of Dijkstra's algorithm in which no vertex can have its distance estimate revised.
Hosam Aly的“洪水填充”是一个广度优先搜索，也就是O(V)。这可以被认为是Dijkstra算法的一个特例，在这个算法中，没有顶点的距离估计被修正。
The Floyd-Warshall algorithm takes O(V^3) time, is very easy to code, and is still the fastest for dense graphs (those graphs where vertices are typically connected to many other vertices). But it's not the right choice for the OP's task, which involves very sparse graphs.
Floyd-Warshall算法需要O(V ^ 3)时间,很容易的代码,和仍然是最快的密度图(图,顶点通常连接到其他顶点)。但是对于OP的任务来说，它不是正确的选择，因为它涉及到非常稀疏的图形。

#4

It sounds like what you want is the end points separated by the graph diameter. A fairly good and easy to compute approximation is to pick a random point, find the farthest point from that, and then find the farthest point from there. These last two points should be close to maximally separated.

它听起来像你想要的是由图直径分开的端点。一个很好的很容易计算的近似值就是选择一个随机的点，找到离它最远的点，然后找到离它最远的点。最后两个点应该接近最大分离。

For a rectangular maze, this means that two flood fills should get you a pretty good pair of starting and ending points.

对于一个矩形的迷宫，这意味着两个洪水填充应该给你一个很好的起点和终点。

#5

Raimund Seidel gives a simple method using matrix multiplication to compute the all-pairs distance matrix on an unweighted, undirected graph (which is exactly what you want) in the first section of his paper On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs [pdf].

Raimund Seidel在他关于非加权无向图中全对最短路径问题的论文的第一节中给出了一个简单的方法，使用矩阵乘法来计算无权无向图上的全对距离矩阵(这正是你想要的)[pdf]。

The input is the adjacency matrix and the output is the all-pairs shortest-path distance matrix. The run-time is O(M(n)*log(n)) for n points where M(n) is the run-time of your matrix multiplication algorithm.

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

The paper also gives the method for computing the actual paths (in the same run-time) if you need this too.

如果需要的话，本文还提供了计算实际路径(在相同的运行时)的方法。

Seidel's algorithm is cool because the run-time is independent of the number of edges, but we actually don't care here because our graph is sparse. However, this may still be a good choice (despite the slightly-worse-than n^2 run-time) if you want the all pairs distance matrix, and this might also be easier to implement and debug than floodfill on a maze.

Seidel的算法很酷，因为运行时与边的数量无关，但实际上我们并不在意，因为我们的图是稀疏的。然而,这仍是一个不错的选择(尽管slightly-worse-than n ^ 2运行时)如果你想要全对的距离矩阵,这可能也更容易实现和调试比floodfill迷宫。

Here is the pseudocode:

这是伪代码:

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

To get the pair of points with the greatest distance we just return argmax_ij(d_ij)

要获得距离最大的点对只需返回argmax_ij(d_ij)

#6

Finished a python mockup of the dijkstra solution to the problem. Code got a bit long so I posted it somewhere else: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

完成了对dijkstra解决方案的python模拟。代码有点长，所以我把它贴在了别的地方:http://refactormycode.com/codes/717-dijkstra-to-find-two-point -furthest-away from-each-other

In the size I set, it takes about 1.5 seconds to run the algorithm for one node. Running it for every node takes a few minutes.

在我设置的大小中，为一个节点运行算法大约需要1.5秒。为每个节点运行它需要几分钟。

Dont seem to work though, it always displays the topleft and bottomright corner as the longest path; 58 tiles. Which of course is true, when you dont have obstacles. But even adding a couple of randomly placed ones, the program still finds that one the longest. Maybe its still true, hard to test without more advanced shapes.

但似乎行不通，它总是将左上角和右下角显示为最长的路径;58瓷砖。当你没有障碍的时候，这当然是对的。但是即使添加了一些随机放置的，程序仍然会发现一个是最长的。也许它仍然是正确的，没有更高级的形状很难测试。

But maybe it can at least show my ambition.

但也许它至少能显示出我的雄心。

#7

Ok, "Hosam's algorithm" is a breadth first search with a preselection on the nodes. Dijkstra's algorithm should NOT be applied here, because your edges don't have weights.

Hosam的算法是首先对节点进行广度搜索。Dijkstra的算法不应该在这里应用，因为你的边没有权值。

The difference is crucial, because if the weights of the edges vary, you need to keep a lot of options (alternate routes) open and check them with every step. This makes the algorithm more complex. With the breadth first search, you simply explore all edges once in a way that garantuees that you find the shortest path to each node. i.e. by exploring the edges in the order you find them.

差异是至关重要的，因为如果边缘的权重不同，您需要保持许多选项(备用路径)打开，并在每一步检查它们。这使得算法更加复杂。通过广度优先搜索，您只需要对所有边进行一次搜索，就可以找到每个节点的最短路径。也就是说，通过探索你找到它们的顺序。

So basically the difference is Dijkstra's has to 'backtrack' and look at edges it has explored before to make sure it is following the shortest route, while the breadth first search always knows it is following the shortest route.

所以基本上，不同之处在于Dijkstra的搜索必须“回溯”，并查看它之前探索过的边缘，以确保它遵循了最短的路径，而广度优先搜索总是知道它遵循了最短的路径。

Also, in a maze the points on the outer border are not guaranteed to be part of the longest route. For instance, if you have a maze in the shape of a giant spiral, but with the outer end going back to the middle, you could have two points one at the heart of the spiral and the other in the end of the spiral, both in the middle!

此外，在迷宫中，边界外的点不能保证是最长路线的一部分。例如，如果你有一个巨大的螺旋形状的迷宫，但是外面的一端回到中间，你可以有两个点一个在螺旋的中心，另一个在螺旋的末端，都在中间!

So, a good way to do this is to use a breadth first search from every point, but remove the starting point after a search (you already know all the routes to and from it). Complexity of breadth first is O(n), where n = |V|+|E|. We do this once for every node in V, so it becomes O(n^2).

因此，一种很好的方法是使用广度优先搜索每个点，但是在搜索之后删除起点(您已经知道了所有的往返路径)。宽度优先的复杂度是O(n)，其中n = |V|+|E|。我们做这一次每个节点的V,所以它变成了O(n ^ 2)。

#8

Your description sounds to me like a maze routing problem. Check out the Lee Algorithm. Books about place-and-route problems in VLSI design may help you - Sherwani's "Algorithms for VLSI Physical Design Automation" is good, and you may find VLSI Physical Design Automation by Sait and Youssef useful (and cheaper in its Google version...)

你的描述听起来像一个迷宫的路径问题。查看Lee算法。关于VLSI设计中的位置和路径问题的书籍可能会对您有所帮助——Sherwani的“VLSI物理设计自动化算法”是很好的，您可能会发现Sait和Youssef的VLSI物理设计自动化非常有用(在谷歌版本中更便宜…)

#9

If your objects (points) do not move frequently you can perform such a calculation in a much shorter than O(n^3) time.

如果你的对象(点)不要移动经常可以执行更短的计算比O(n ^ 3)时间。

All you need is to break the space into large grids and pre-calculate the inter-grid distance. Then selecting point pairs that occupy most distant grids is a matter of simple table lookup. In the average case you will need to pair-wise check only a small set of objects.

你所需要的只是把空间分解成大网格，并预先计算网格间的距离。然后，选择占据最远处网格的点对是一个简单的表查找问题。在一般情况下，您只需要对一小组对象进行成对检查。

This solution works if the distance metrics are continuous. Thus if, for example there are many barriers in the map (as in mazes), this method might fail.

如果距离度量是连续的，那么这个解决方案是有效的。因此，例如，如果映射中有许多障碍(如迷宫中)，该方法可能会失败。

#1