解决方案中缺少节点(迷宫 DFS 求解算法)
Missing nodes in solution (maze DFS solving algorithm)
我的 DFS 算法在解中缺少节点时遇到问题(检查图像)。每次我的算法遇到死胡同时都会发生这种情况:节点从堆栈中弹出并返回,直到找到可用的移动,并且再也不会重新包含在内。有没有一种简单的方法可以在不重新实现整个算法的情况下修复它?
final int start = maze.getStart();
final int stop = maze.getStop();
final int columns = maze.getColumns();
final int[] moves = { 0, 1, 2, 3 }; //North, E, S, W
int position = start;
Maze.Cells cells = maze.getCells();
cells.setVisited(position);
Stack<Integer> stack = new Stack<>();
visitCells:
while(position != stop){
boolean[] availableMoves = cells.getAvailableMoves(position); //only visit yet unvisited cells
for(int move : moves){
if(availableMoves[move] && maze.isMovePossible(position, move)){
position = doMove(position, move)
cells.setVisited(position);
stack.push(position);
continue visitCells;
}
}
position = stack.pop();
}
return stack;
我希望代码是自解释的。绘图算法是正确的,所以我不post这里。不要犹豫,在评论中询问更多信息。
我认为问题在于,当您从 A 移动到 B 时,您正在将新位置 B 推入堆栈。这意味着当你回溯时,你永远不会回到 A.
尝试重新排序:
position = doMove(position, move)
cells.setVisited(position);
stack.push(position);
至
stack.push(position);
position = doMove(position, move)
cells.setVisited(position);
我的 DFS 算法在解中缺少节点时遇到问题(检查图像)。每次我的算法遇到死胡同时都会发生这种情况:节点从堆栈中弹出并返回,直到找到可用的移动,并且再也不会重新包含在内。有没有一种简单的方法可以在不重新实现整个算法的情况下修复它?
final int start = maze.getStart();
final int stop = maze.getStop();
final int columns = maze.getColumns();
final int[] moves = { 0, 1, 2, 3 }; //North, E, S, W
int position = start;
Maze.Cells cells = maze.getCells();
cells.setVisited(position);
Stack<Integer> stack = new Stack<>();
visitCells:
while(position != stop){
boolean[] availableMoves = cells.getAvailableMoves(position); //only visit yet unvisited cells
for(int move : moves){
if(availableMoves[move] && maze.isMovePossible(position, move)){
position = doMove(position, move)
cells.setVisited(position);
stack.push(position);
continue visitCells;
}
}
position = stack.pop();
}
return stack;
我希望代码是自解释的。绘图算法是正确的,所以我不post这里。不要犹豫,在评论中询问更多信息。
我认为问题在于,当您从 A 移动到 B 时,您正在将新位置 B 推入堆栈。这意味着当你回溯时,你永远不会回到 A.
尝试重新排序:
position = doMove(position, move)
cells.setVisited(position);
stack.push(position);
至
stack.push(position);
position = doMove(position, move)
cells.setVisited(position);