CFS에서 미로의 DFS 최단 경로

DFS를 사용하여 목표까지 최단 경로를 얻으려고 시도하는 중 ...이 작업을 수행하는 방법을 정확히 파악하는 데 문제가 있습니다. 나는 BFS가 더 뛰어나다는 것을 알고 있지만 이것을 위해 DFS를 사용하도록 요청 받았다. 보시다시피 목표를 찾기 위해 끝까지 연결되는 모든 스택을 비교하려고 시도하지만 작동하지 않습니다. 목표로 연결되는 첫 번째 스택 만 인쇄됩니다 ... 필요한 곳을 알고 있습니다. 노드를 탐색하지 못하지만 정확히 어떻게 계산할 수는 없습니다. 지금 나는 목표로 향하는 길을 얻지 만, 최단 거리가 아니다. 어떤 도움이라도 대단히 감사하겠습니다.CFS에서 미로의 DFS 최단 경로

출처

2014-03-31 seanscal

** 비 재귀 ** DFS를 쓰는 구체적인 이유는 무엇입니까? –

@faranwath 특별한 이유가 없으면 재귀가 여기에서 더 쉬워 질 것입니다. 나는 모두 그것을위한 것입니다 – seanscal

그래프는 어떻게 정의됩니까? –

고유 한 스택을 사용하여 비 재귀 DFS를 작성할 수 있지만 재귀적인 솔루션이 더 우수하다는 것을 알게되었습니다. 여기에 하나의 스케치가 있습니다 :

DFS(vertex) 

    path.push_back(vertex) 
    visited[vertex] = true 

    if we found the exit 
     output path 
    else 
     for each neighbor v of vertex 
      if not visited[v] 
       DFS(v) 

    visited[vertex] = false 
    path.pop_back()

출처

2014-03-31 14:46:00

이렇게하면이 모델을 기반으로 한 결과를 얻을 수있었습니다. 고맙습니다. 이것은 훨씬 더 의미가 있으며 시도했던 것보다 훨씬 적은 코드입니다. – seanscal

재귀 버전을 사용하면 비 재귀 버전을 작성하는 것이 좋습니다. 이점은 방정식에서 스택 오버플로를 제거하고 (의도 한 말투가 없음) 현재 상태를 볼 수있는 유연성이 더 있거나 알고리즘을 일부 변경하고 싶을 때 유용합니다. –

CFS에서 미로의 DFS 최단 경로

답변

관련 문제