1

二次行列で移動する最良の方法を見つけるために、Javaで深さ優先検索アルゴリズムを実装しようとしています。「不要な」オブジェクト、つまり (X,Y) 位置を保持するためだけのオブジェクトを作成することは避けています。

私は何かを忘れていますか？（0,0）の開始点と（4,5）の目的で実行しています。何が起こるかというと、無限ループです。

int x = this.move_to_x;
int y = this.move_to_y;

Stack X = new Stack();
Stack Y = new Stack();

Stack visited_X = new Stack();
Stack visited_Y = new Stack();

X.push(this.current_x);
Y.push(this.current_y);

while(!X.empty()){
    int tmp_x = (int)X.pop();
    int tmp_y = (int)Y.pop();

    if(tmp_x == x && tmp_y == y){
        System.out.println("best way found!");
        return;
    }

    //there is only 8 possible ways to go (the neighbors)
    for(int a = -1; a < 2; a++){
        for(int b = -1; b < 2; b++){
            if(a == 0 && b == 0){
                break;
            }

            if(visited_X.search(tmp_x + a) == -1 && visited_Y.search(tmp_y + b) == -1){
                X.push(tmp_x + a);
                Y.push(tmp_y + b);

                visited_X.push(tmp_x + a);
                visited_Y.push(tmp_y + b);

                System.out.println("added x " + tmp_x + a + " y " + tmp_y + b);
            }
        }
    }
}
4

1 に答える 1

1

私はいくつかの問題を見ることができます:

1) 以下の場合:

        if(a == 0 && b == 0){
            break;
        }

continueではなく使用する必要がありますbreak。

2) 以下:

if(visited_X.search(tmp_x + a) == -1 && visited_Y.search(tmp_y + b) == -1){

は正しくありません:(tmp_x, tmp_y)ペアはの同じインデックスに存在する必要がありvisited_X/visited_Yます。

3) に開始位置を追加する必要がありvisited_{X,Y}ます。

4) アルゴリズム的に、あなたのメソッドが最短パスを返すと考える理由はありません。

5) コードが (ほぼ) 無限ループに陥る理由は、行列の境界をチェックしていないためです。

于 2013-03-07T06:42:59.770 に答える