maze - 如何找到递归回溯迷宫的起点和终点？

Question

你如何找到递归回溯生成的迷宫的起点和终点？似乎很难弄清楚，因为迷宫从来没有ends。这会是你第一次开始回溯的地方吗？起点可能是您开始的地方，但有时会有更好的地方。

score 0 · Accepted Answer

当您使用递归回溯生成迷宫时，如下所示：

然后所有单元格都连接起来，并且只有一种方式可以在任意两个单元格之间旅行，而无需回溯您的步骤。

您可以选择任何您喜欢的起点和终点！

请注意，像迷宫单元一样连接的图是无向树，即，从任何顶点到任何其他顶点都只有一条路径。如果要找到相距最远的两个点，以便将它们用作起点和终点，则需要找到这棵树的直径。

有很多方法可以做到这一点，但最简单的是：

1）选择一个随机顶点开始，并使用BFS找到离它最远的顶点。那将是你的起点。

2) 使用 BFS 找到离起始顶点最远的/a 顶点。那是你的终点。

起点和终点将尽可能地分开。

这个问题的答案解释了为什么总是有效：正确性证明：图论中树的直径算法

请注意，相距最远的点不一定在边缘上。我发现当您需要时，在边缘选择随机点可以正常工作： https ://mtimmerm.github.io/webStuff/maze.html

1 回答 1