二维数组中的迭代加深深度优先搜索

Question

我正在尝试在二维数组（迷宫）中实现迭代加深搜索。

static void Run_Ids(int x, int y)
    {
        int depth_limit = 0;

        while(!cutoff)
        {   
            out.println("Doing search at depth: " + depth_limit);             
            depthLimitedSearch(x, y, depth_limit);
            depth_limit++;
        }      
    }

这是我使用堆栈的有限深度优先搜索。由于某种原因，它在两个单元格之间来回移动。它没有像它应该的那样扩展。我认为我这里的DFS算法有问题。

static void depthLimitedSearch(int x, int y, int depth){        
    Pair successor;    //pair is the x, y co-ordinate
    successor = starting();  //set the successor to starting cell

    stack = new Stack<>();
    int i = 0;
    stack.push(successor);

    while (!stack.isEmpty())
    {
        out.println("i level: " + i);
        Pair parent = stack.peek();   //pop it here?

        if (parent.x == Environment.goal[0] && parent.y == Environment.goal[1]){  //check to see if it is the goal
            cutoff = true;
            out.println("goal found ");                
            break;
        }
        if (i == depth){
            //stack.pop();   //pop here?
            break;
        }
        else{

            Pair  leftPos,rightPos,upPos,downPos;
            leftPos = leftPosition(parent.x, parent.y);
            rightPos = rightPosition(parent.x, parent.y);
            upPos = upPosition(parent.x, parent.y);
            downPos = downPosition(parent.x, parent.y);


            if(Environment.isMovePossible(rightPos.x, rightPos.y))
                                        //if it can go right
                   stack.push(rightPos);   

            if(Environment.isMovePossible(leftPos.x, leftPos.y))
                                       // if it can go left
                   stack.push(leftPos);

             if(Environment.isMovePossible(downPos.x, downPos.y))
                                     //if it can go down
                  stack.push(downPos);

            if(Environment.isMovePossible(upPos.x, upPos.y))                
                                        //if it can go up
                    stack.push(upPos);


            stack.pop();         //pop here?


        }  //else       

        i++;

    }//while     
}

我对堆栈没有那么多经验，我对将它推到哪里以及从哪里弹出感到困惑。如果这里有人能给我指出正确的方向，那就太好了！

Answer 1

我认为你必须标记你已经访问过的数组的位置以避免重新访问它们。不要将您已经访问过的任何位置推入堆栈。

如果不这样做，您很可能会陷入无限循环：

例如，假设您可以从您的初始位置向所有方向前进 - 左、右、上和下。所以你推这 4 个位置，然后弹出你推的最后一个 - 向下。

现在，只要向下是一个有效的方向，你就会继续向下。当您到达无法向下的位置时，您将推动下一个有效方向，其中包括向上（您刚刚来自的方向）。

因为你是在向下推之前向上推到堆栈，当你到达你不能向下推的位置时，向上将是最后一个被推的位置，这意味着你将弹出向上的位置去你原来的位置。

从那里你将返回下去，然后在无限循环中返回。

二维数组中的迭代加深深度优先搜索

Iterative deepening depth first search in a 2d array

java

artificial-intelligence

depth-first-search

maze

iterative-deepening