java - 解决方案中缺少节点(迷宫 DFS 求解算法)

Question

我的 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;

我希望代码是可 self 解释的。绘图算法是正确的，所以我不在这里发布。不要犹豫，在评论中询问更多信息。

Answer 1

我认为问题在于，当您从 A 移动到 B 时，您正在将新位置 B 插入堆栈。这意味着当你回溯时，你永远不会回到 A。

尝试重新排序:

            position = doMove(position, move)
            cells.setVisited(position);
            stack.push(position);

到

            stack.push(position);
            position = doMove(position, move)
            cells.setVisited(position);