你如何找到递归回溯迷宫的开始和结束？

Question

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

Answer 1

当你产生这样的递归回溯一个迷宫：

http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking

那么所有的电池连接，并有完全不追溯你的步骤中的任何两个单元之间的旅行方式之一。

你可以选择你喜欢的任何开始和结束点！

请注意，像迷宫细胞那样连接的图形，即从任何顶点到任何其他顶点都只有一条路径是无向树。如果你想找到距离最远的两个点，以便你可以使用它们作为起点和终点，那么你需要找到这棵树的直径。

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

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

2）使用BFS查找离开始顶点最远的顶点。这是你的终点。

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

回答这个问题解释了为什么总是工作：Proof of correctness: Algorithm for diameter of a tree in graph theory

注意，是相隔最远的点不一定在边缘上。我发现，当你需要这些边缘时，随机点的选取工作正常：https://mtimmerm.github.io/webStuff/maze.html