IDDFS를 사용하여 경로 배열 만들기

Question

내 IDDFS 알고리즘은 인접 행렬을 사용하여 그래프의 최단 경로를 찾습니다. 이것은 솔루션의 깊이를 보여줍니다 (시작 지점에서 끝 지점까지 연결된 지점의 양이라는 것을 알고 있습니다).
이 배열을 배열로 가져오고 싶습니다.

예 :
솔루션은 깊이 5에서 발견되므로 포인트가있는 배열을 원합니다. {0,2,3,4,6}.
깊이 3 : 배열 {1,2,3}.

int DLS(int node, int goal, int depth,int adj[9][9]) 
{ 
    int i,x; 

    if (depth >= 0) 
    { 
     if (node == goal) 
      return node; 

     for(i=0;i<nodes;i++) 
     { 
      if(adj[node][i] == 1) 
      { 
       child = i; 
       x = DLS(child, goal, depth-1,adj); 

       if(x == goal) 
        return goal; 
      } 
     } 
    } 
    return 0; 
} 

int IDDFS(int root,int goal,int adj[9][9]) 
{ 
    depth = 0; 
    solution = 0; 
    while(solution <= 0 && depth < nodes) 
    { 
     solution = DLS(root, goal, depth,adj); 
     depth++; 
    } 
    if(depth == nodes) 
     return inf; 

    return depth-1; 
} 

int main() 
{ 
    int i,u,v,source,goal; 

int adj[9][9] = {{0,1,0,1,0,0,0,0,0}, 
     {1,0,1,0,1,0,0,0,0}, 
     {0,1,0,0,0,1,0,0,0}, 
     {1,0,0,0,1,0,1,0,0}, 
     {0,1,0,1,0,1,0,1,0}, 
     {0,0,1,0,1,0,0,0,1}, 
     {0,0,0,1,0,0,0,1,0}, 
     {0,0,0,0,1,0,1,0,1}, 
     {0,0,0,0,0,1,0,1,0} 
    }; 

    nodes=9; 
    edges=12; 

    source=0; 
    goal=8; 

    depth = IDDFS(source,goal,adj); 

    if(depth == inf)printf("No solution Exist\n"); 
    else printf("Solution Found in depth limit (%d).\n",depth); 

    system("PAUSE"); 
    return 0; 
} 

-
(I 거의 그래프와 초보자있어 내가 방문한 점을 다시 방문하는 경우 검색하거나하지는 않지만, 그 알고리즘이 "알고"잘 모르겠어요) : 여기

는 C++의 알고리즘이다

다른 경로 찾기 알고리즘 대신 IDDFS를 사용하는 이유는 정확한 길이의 경로를 찾기 위해 지정된 숫자로 깊이를 변경하고자한다는 것입니다 (그러나 작동하는지 확실하지 않습니다). 누군가가 인접 행렬을 사용하여 지정된 길이의 경로를 찾기위한 다른 알고리즘을 제안하는 경우

---

, 내가 그것에 대해 알려 주시기 바랍니다.

Answer 1

경로 찾기 알고리즘에서 검색된 실제 경로를 얻으려는 아이디어는 map:V->V을 사용하여 키가 정점이고 값이 키를 발견하는 데 사용 된 정점입니다 (소스는 키가 아니거나 임의의 정점에서 발견되지 않았으므로 null 값이있는 키입니다.

경로 찾기 알고리즘이 실행되는 동안이 맵을 수정하고 완료되면 표에서 반복적으로 읽는 방식으로 경로를 얻을 수 있습니다. 경로를 반대 순서로 사용하십시오.

DFS : 새 정점 (즉, key)을 발견 할 때마다 (key,value) 쌍을 삽입합니다. key이 이미지도의 키인 경우이 분기를 건너 뜁니다.
특정 경로를 탐색하고 정점을 "닫은 후에"목록에서 제거해야합니다. 그러나 알고리즘을 최적화하고이 부분을 건너 뛸 수 있습니다 (분기 요소를 더 작게 만듭니다).

IDDFS는 실제로 DFS를 반복적으로 수행하기 때문에 동일한 논리를 따르고 새로운 DFS 반복을 만들 때마다 더 높은 깊이로 이전 맵을 지우고 처음부터 새로 시작할 수 있습니다.

다른 길 찾기 알고리즘은 BFS, A* 및 dijkstra's algorithm입니다. 마지막 2 개는 가중치 그래프에도 적합합니다. IDDFS에서 특정 깊이에 도달하면 DFS가 종료되는 것과 같은 특정 깊이에 도달하면 이러한 모든 작업이 종료 될 수 있습니다.