Floyd-Warshall 알고리즘으로 미로 찾는 방법

Question

플로이드의 알고리즘을 사용하여 각 미로 정점에있는 98 개의 웨이 포인트가있는 미로를 통해 가장 빠른 경로 매트릭스를 생성하려고합니다. 알고리즘이 실행되면 두 개의 행렬, 즉 거리 행렬 (두 노드 사이의 최적 거리)과 경로 행렬 (두 노드 사이에서 가장 최적의 경로로 이동하는 다음 노드)이 채워집니다.

거리 매트릭스는 이전 코드에서 생성 한 인접 매트릭스로 초기화됩니다. 또한 각 웨이 포인트에 대해 네 개의 가능한 이웃 웨이 포인트에 대한 포인터를 포함하는 데이터 구조를 생성하지만이 데이터 구조를 사용하여 경로 매트릭스를 생성하지 않았습니다. 내가 경로 행렬이기 때문에이 코드에 의해 생성 된 경로 매트릭스를 사용하는 봇 (대부분의 상황에서 실패 때문에 내가 잘못 경로 행렬을 계산하고 생각

 // Initialize distance path matrix 
     distanceMatrix = adjacencyMatrix; 

     // Initialize path matrix 
     int N = (WaypointList.Count); 
     pathMatrix = new int[N, N]; 

     for (int i = 0; i < N; i++) 
      for (int t = 0; t < N; t++) 
       pathMatrix[i,t] = t; 

     // Floyd-Warshall algorithm    
     for (int k = 0; k < N; ++k) 
      for (int i = 0; i < N; ++i) 
       for (int j = 0; j <= i; ++j) 
       { 
        int currentCombo = distanceMatrix[i, k] + distanceMatrix[k, j]; 
        if (currentCombo < distanceMatrix[i, j]) 
        {        
         distanceMatrix[j, i] = distanceMatrix[i, j] = currentCombo; 
         pathMatrix[j, i] = pathMatrix[i, j] = k; 
        } 
       } 

:

여기 내 C# 코드입니다 벽을 통과하라는 말 등).

나는이 코드를 몇 시간 꼼짝 않고 들여다 보았고, 내가 잘못한 것을 잘 모르고있다. 내 미로 탐색 코드에 사용할 올바른 경로 행렬을 생성하려면 어떻게해야합니까?

Answer 1

pathMatrix[i, j] = k을 설정하면 노드 i에서 j까지의 경로가 노드 k으로 이동하는 것으로 시작한다고 가정합니다. 그러나 실제로 의미하는 바는 i에서 j까지의 경로가 어떤 시점에서 k을 통과 할 것이고, 반드시 첫 번째 이동이 아닐 수도 있습니다. 이 i에서 이동하려면 다음 노드로 target을 설정합니다

target = j 
while there is no edge from i to target: 
    target = pathMatrix[i, target] 

:

는 당신이 필요가있는 무엇을 i에서 j의 경로가 있다고 가정하면, 다음과 같다.