我正在尝试在二维数组(迷宫)中实现迭代深化搜索。
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
}
我对堆栈没有太多经验,我对在哪里推送它以及在哪里弹出感到困惑。如果这里有人能指出我正确的方向,那就太好了!