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 回答