1

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

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     
}

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

4

1 回答 1

0

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

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

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

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

由于您在下推之前向上推到堆栈，因此当您到达无法下推的位置时，上将是最后推的位置，这意味着您将弹出上位置并转到该位置你来自。

从那里您将返回然后返回无限循环。

于 2015-03-29T18:40:52.790 回答