0

私が取り組んでいるゲームでパス検索を機能させるために、1週間試してきました。私はフロイド・ウォーシャルのアルゴリズムのこの実装を使用しています。問題をこのループ内に絞り込むことができたと思います。

for(int k = 0; k < nodes.length; k++)
    for(int i = 0; i < nodes.length; i++)
        for(int j = 0; j < nodes.length; j++)
            if(D[i][k] != Integer.MAX_VALUE
            && D[k][j] != Integer.MAX_VALUE
            && D[i][k] + D[k][j] < D[i][j]){
                D[i][j] = D[i][k]+D[k][j];
                P[i][j] = nodes[k];
            }

すべてのノードが他のすべてのノードに接続し、すべての接続の重みが 1 である 4 つのノードでテストしてきました。これは、ループ前のすべての関連変数の値です。

for(Node n:nodes)System.out.println(n.pos.toString() + " " + n.index);

出力：

[x: 4, y: 4] 0
[x: 4, y: 5] 1
[x: 5, y: 4] 2
[x: 5, y: 5] 3

これは予想通り

for(Edge e:edgeList)
    System.out.println(e.from.pos.toString() + " " + e.to.pos.toString());

出力：

[x: 4, y: 4] [x: 5, y: 4]
[x: 4, y: 4] [x: 4, y: 5]
[x: 4, y: 4] [x: 5, y: 5]
[x: 4, y: 5] [x: 4, y: 4]
[x: 4, y: 5] [x: 5, y: 4]
[x: 4, y: 5] [x: 5, y: 5]
[x: 5, y: 4] [x: 4, y: 4]
[x: 5, y: 4] [x: 4, y: 5]
[x: 5, y: 4] [x: 5, y: 5]
[x: 5, y: 5] [x: 4, y: 4]
[x: 5, y: 5] [x: 5, y: 4]
[x: 5, y: 5] [x: 4, y: 5]

これも予想通り。

for(int[] ia:D){
    for(int a:ia)System.out.print(a + " ");
    System.out.print("\n");
}

出力：

2147483647 1 1 1 
1 2147483647 1 1 
1 1 2147483647 1 
1 1 1 2147483647

これも予想通り。

P = new Node[nodes.length][nodes.length];
for(int k = 0; k < nodes.length; k++)
    for(i = 0; i < nodes.length; i++)
        for(int j = 0; j < nodes.length; j++)
            if(D[i][k] != Integer.MAX_VALUE
            && D[k][j] != Integer.MAX_VALUE
            && D[i][k]+D[k][j] < D[i][j]){
                D[i][j] = D[i][k]+D[k][j];
                P[i][j] = nodes[k];
                System.out.println(nodes[k].pos.toString() + " " + k);
            }

出力：

[x: 4, y: 4] 0
[x: 4, y: 4] 0
[x: 4, y: 4] 0
[x: 4, y: 5] 1

ここに問題があると思います。出力にはすべての異なるノードが含まれていると予想していましたが、ここで見つかった 2 つのノードのみが getShortestPath 関数で機能します。これはループの正しい出力であり、私が理解している限り、順序は無関係であるはずです。

[x: 4, y: 4] 0
[x: 4, y: 5] 1
[x: 5, y: 4] 2
[x: 5, y: 5] 3

ループ内で何が問題を引き起こしているのか、またはアルゴリズムについて何か誤解しているのかどうかはわかりません。

4

1 に答える 1

1

結果から:

[x: 4, y: 4] 0
[x: 4, y: 4] 0
[x: 4, y: 4] 0
[x: 4, y: 5] 1

何が起こったのか、ほぼ推測できます。以外のすべてD[i][j]を に初期化した可能性1があります。最初の 3 回の更新は、でした。ただし、更新できるのは.D[i][i]Integer.MAX_VALUED[i][i] = D[i][0] + D[i][0]k = 0i = 1..3D[0][0]d[0][1] + d[1][0]

floyd-warshall の実装はまったく問題ないようです。たぶん、最短パスルートの回復のようなバグを持っているより欠陥のある他の場所でバグをチェックする必要があります.

于 2012-09-25T03:15:54.907 に答える