0

フロイドのアルゴリズムを使用して、98 個のウェイポイント (各迷路の頂点にある) を持つ迷路を通る最速ルート マトリックスを生成しようとしています。アルゴリズムが実行されると、Distance マトリックス (2 つのノード間の最適な距離) と Path マトリックス (任意の 2 つのノード間の最適なパスに移動する次のノード) の 2 つのマトリックスが生成されます。

距離行列は、前のコードで生成した隣接行列で初期化されます。また、ウェイポイントごとに 4 つの可能な近隣ウェイポイントのそれぞれへのポインターを含むデータ構造も生成しますが、パス マトリックスの生成にはこのデータ構造を使用しませんでした。

ここに私のC＃コードがあります：

        // 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;
                    }
                }

このコードによって生成されたパス マトリックスを使用するボットは、ほとんどの状況で (パス マトリックスが壁を通過するように指示しているため) 失敗するため、パス マトリックスを正しく計算していないと思います。

私は何時間もこのコードを見つめてきましたが、何が間違っていたのか頭に浮かびません。迷路ナビゲーション コードで使用する正しいパス マトリックスを生成するにはどうすればよいですか?

4

1 に答える 1

1

を設定しているとき、これは node から nodeへのパスが node に行くことから始まることをpathMatrix[i, j] = k意味すると想定しています。しかし実際には、 からへのパスは、必ずしも最初の移動ではなく、ある時点で通過することを意味します。ijkijk

iからへのパスがあると仮定して、次のことを行う必要がありますj。

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

これはtarget、 from から移動する次のノードに設定されiます。

于 2012-12-17T12:08:50.610 に答える