재귀 backtracking 미로의 시작과 끝을 어떻게 찾을 수 있습니까?

Question

재귀 backtracking으로 생성 된 미로의 시작과 끝을 어떻게 찾을 수 있습니까? 미로가 결코 ends 인 것처럼 그것을 이해하는 것이 어려울 것 같습니다. 처음으로 백 트랙킹을 시작하는 지점이 될까요? 시작 지점은 시작 지점 일 수 있지만 때로는 더 좋은 지점이 있습니다.

Answer 1

이 같은 재귀 되돌아와 미로 생성 할 때 :

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

은 모든 세포가 연결을하고, 두 세포 사이를 이동하는 방법 중 하나는 당신의 단계를 되돌아없이 정확하게있다.

원하는 시작과 끝 지점을 선택할 수 있습니다!

미로 셀과 같이 연결된 그래프는 즉 임의의 정점에서 임의의 다른 정점으로의 경로가 정확하게 하나가되도록, 무 방향성 트리임을 유의해야한다. 가장 멀리 떨어져있는 두 점을 찾으려면 시작점과 끝점으로 사용할 수 있도록이 트리의 지름을 찾아야합니다.

이 그렇게 할 수있는 방법이 많이 있지만, 단순한는이 :

1)에서 시작하는 임의의 정점을 선택하고, 그것에서 가장 먼/정점을 찾기 위해 BFS를 사용합니다. 그것이 당신의 출발점이 될 것입니다.

2) BFS를 사용하여 시작 정점에서 가장 먼/a 정점을 찾으십시오. 그것이 당신의 종말점입니다.

시작 지점과 끝 지점은 최대한 멀리 둡니다. 떨어져 멀리있는 점은 가장자리에 필요하지 않은 Proof of correctness: Algorithm for diameter of a tree in graph theory

하는 것으로 :이 항상 작동하는 이유

이 질문에 대한 대답은 설명합니다. 나는 당신이 필요로 할 때 모서리의 무작위 포인트를 선택하면 잘 작동한다는 것을 알게되었습니다 : https://mtimmerm.github.io/webStuff/maze.html