넓이 우선 검색 구현

Question

JavaScript (자바 스크립트)에서는 Breadth First Search (다른 알고리즘이지만 현재는 bfs)를 구현하려고합니다.

결국 모든 그리드에서 검색 알고리즘을 적용하여 시작부터 목표 노드까지의 경로를 찾고 싶습니다. (필자는 bfs가 그리 좋지는 않다는 것을 알고 있습니다.) 구현을했지만 문제는 내가 전체 트리를 미리 가지고 있지 않다는 것입니다. 내가 원한 것은 시작 노드와 끝 노드를주고 그 노드를 기반으로 그들 사이의 경로를 찾는 것입니다.

내가 겪고있는 문제는 인접한 격자 사각형을 결정할 때 모든 이웃을 반환하므로 이미 통과 한 것입니다. 그러면 트리 검색이 아닌 그래프 검색이됩니다. 이를 해결하는 방법은 모든 경로를 기억하여 어느 이웃 라우터가 이미 통과했는지 확인할 수 있으므로 더 이상 검사 할 필요가 없습니다. 그러나 검색 알고리즘에 대해 배웠을 때 bfs는 현재 깊이 수준의 모든 노드를 메모리로 사용합니다. 모든 경로를 저장하면 해당 경로보다 훨씬 많은 메모리가 소모됩니다.

미리 나무 구조가없고 사이클을 피할 때 bfs가 검색하는 현재 깊이의 노드 만 메모리에 유지할 수 있습니까?

나는 내 자신을 분명히했으면 좋겠다. 사전에

감사합니다, 스테판

Answer 1

당신이 방문 노드를 "잊지"경우, 당신은 발견 DFS 같은 문제로 얻을 수 있습니다 - ((최적의 경로를 찾을 수)가 최적이 아닌도 완료 무한 루프로 인해 솔루션이 존재하지 않을 수도 있습니다.

참고 :

• 만 가장 깊은 수준의 노드를 기억하더라도 - 여전히 많은 도움이되지 않습니다 - 이진 트리에, 예를 들어, 노드의 절반 잎 것을 기억 때문에, 공간의 복잡성은 여전히 ​​커질 것입니다.
• 노드의 일부만 기억한다고해서 최적 성이 보장되는 것은 아닙니다. 결국 잊어 버린 버텍스를 다시 발견하게 될 것이고, 그때까지는 루프에 빠지게 될 것입니다.

완전한 최적의 메모리 효율적인 알고리즘을 찾고 계시다면 - Iterative Deepening DFS 일 수 있습니다.