java - java 中的另一个深度优先搜索问题

Question

我正在用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);
            }
        }
    }
}

Answer 1

我可以看到几个问题:

1)如下:

        if(a == 0 && b == 0){
            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)您的代码最终陷入(几乎)无限循环的原因是您没有检查矩阵边界。