깊이 최단 경로를 찾으려면 먼저 검색 하시겠습니까?

Question

나는 이것이 일반적으로 너비가 넓은 것으로 끝난다는 것을 알고있다. 그러나 우리는 둘 다로해야만한다. 나는 이미 너비를 먼저 달성했다. ...

나는 깊이 첫 번째 검색을 사용하는 전형적인 예다. 그래서 나는 여기서 도움을 얻을 수 있기를 바랐다 ... 나는 깊이 우선 검색을 사용하여 미로를 통과하는 최단 경로를 찾으려고 시도하고있다. 그러나 지금 당장은 그것을 정확히 어떻게 수행 할 것인지에 대해 머리를 감쌀 수 없다. 지금

void maze::findPathRecursive(graph &g, int position, int goal) { 
    if (position == goal) { 
     isPath = true; //returns true if there is a path to the goal 
     correctPath.push_back(position); // the path to the goal 
    } else { 
     g.mark(position); 
     g.visit(position); 

     //gets all the neighbors of the current position 
     vector<int> neighbors = getNeighbors(position, g); 

     while (!neighbors.empty()) { 
      int n = neighbors.back(); 
      neighbors.pop_back(); 

      if (!g.isVisited(n)) { 
       findPathRecursive(g, n, goal); 
      } 

      if (isPath) { 
       correctPath.push_back(position); 
       break; 
      } 
     } 
    } 
} 

는, 어떤이가하는 일은 거기에서 목표 및 휴식 시간에 그것을 할 수있는 최초의 경로를 찾을 수 있습니다 : 이것은 지금까지 내 코드입니다. 내가 휴식을 제거해야 할거야 그리고 내가 가장 짧은 경로를 저장하고 이전과 가장 짧은 이전의 길이를 비교하는 다른 벡터를 만들려고했는데 어떤 점에서 노드를 비켜 필요가 있기 때문에 그것이 작동하지 않았다 여기 정확히 어떻게해야 하는지를 알 수는 없습니다.

도움을 주시면 대단히 감사하겠습니다 !!

g는 미로를 포함하는 방식으로 나타낸 그래프입니다.

Answer 1

DFS shortest path of a maze in C++ 검사가 오히려 "unvisit"노드 이상의

Answer 2

일반적으로 가장 짧은 경로를 찾기 위해 DFS를 사용하고 싶지 않습니다 (그래프가 명확하게 비순환 적이며 방향이없는 경우를 제외하고는 처음 목표를 세울 경로가 하나뿐입니다). 가능한 경우, 그러나 그것은 매우 고안된 것입니다. 가장 단순한 수준에서 DFS는 경로가 있는지 판단한 후 최상의 경로가 무엇인지 결정하는 데 더 능숙합니다.

다양한 Breadth First Search (BFS) 알고리즘을 살펴 보는 것이 좋습니다. 미로가 그리드 위에 있으면 A *가 가장 좋은 방법 일 것입니다.

Answer 3

나는이 질문을 완전히 이해하고 있는지 잘 모르겠지만 일반적으로 너비 우선 검색을 사용하지 않겠는가? (가장 단순한 경우에는)? DFS가 바로 가기를 "놓칠"수 있기 때문에 최단 경로를 찾으려고하는 DFS는 일종의 BFS로 변해야합니다.

아마도 https://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used-to-find-shortest-paths-in-unweighted-graphs이고이 http://en.wikipedia.org/wiki/Shortest_path_problem이 도움이됩니다.

Answer 4

DFS를 사용하여 경로를 찾을 수는 있지만 (가장 짧은 경로 인 경우) 일반적으로 최단 경로를 보장하지는 않습니다. BFS가 최선의 방법입니다.

그러나 접근 방식은 Iterative Deepening입니다. 위키 :

반복 심화 된 깊이 우선 탐색 1 (IDDFS)는이 D에 도달 할 때까지 반복 될 때마다 깊이 제한을 증가 상태 공백 됨 깊이 한정 검색을 반복 실행하는 전략 이고 , 가장 얕은 목표 상태 인 깊이는 입니다. IDDFS는 너비 우선 검색 과 동일하지만 메모리 사용량이 훨씬 적습니다. 각 반복에서 은 깊이 - 우선 검색과 동일한 순서로 검색 트리의 노드를 방문하지만 노드를 처음 방문한 누적 순서는 입니다. 위키 다시

의사 코드 :

> IDDFS(root, goal) { 
> depth = 0 
> for(i=1, i<10, i++) { 
>  DFS(limit=i) 
> } 
> } 

첫째는 DFS 구현은 (정확히 BFS처럼하지만 스택 대신 대기열을 사용한다), 다음 ID 알고리즘을 구현한다. 희망이 도움이됩니다.도움이 질문은 내 다른보다 더 많은 주목을 받고있는 이유, 확실하지 여기에 제공된

Answer 5

대답 나는 당신이 얼마나 많은 가장자리 각 노드에 저장할 필요가 있다고 생각 거기에 도착했다. 더 짧은 경로를 통해 다시 도착하면 해당 노드와 해당 노드에서 목표까지의 최적 경로에있는 모든 노드의 에지 수를 업데이트합니다.