java：广度优先遍历迷宫回溯

Question

我正在尝试为迷宫实现广度优先遍历。这是我到目前为止使用链表的代码，但我不确定它是否是广度优先搜索。这是正确的方法吗？有什么建议、意见吗？

    public boolean traverseBreadth(){
    //traverse the floor from entrance to exit
    //stepping only on red tiles
    steps = new LinkedList<Tile>();
    possibleSteps = new LinkedList<Tile>();
     //reset markings
     reset();
    //push the entrance onto the stack
    entrance.setVisited();
    steps.add(entrance);

    System.out.println("add " + entrance);
    nextMoves(entrance);
    //keep going as long as we have a possibility to move
    //and we haven't reached the end yet
    while (!possibleSteps.isEmpty()&& (!possibleSteps.getLast().equals(exit)))
    {   
        Tile x = possibleSteps.removeLast();

        x.setMarked();   //walked on that square
        steps.add(x);  //walk to that square
        System.out.println("Walked to the square  " + x);
        //now figure out where you can walk from this square
        nextMoves(x);
        try {
               Thread.currentThread().sleep(1000);
               }
             catch (InterruptedException e) {
               e.printStackTrace();
               }





    }
    if (possibleSteps.getLast().equals(exit)){
        steps.push(possibleSteps.removeLast());
        System.out.println("made it from entrance to exit");
        System.out.println(steps.toString());
        return true;
    }
    else 
    {   JOptionPane.showMessageDialog(null,"sorry can't reach the exit");
        return false;
    }

}

Answer 1

这不是广度优先搜索 - 这是深度优先。

有 2 个地方显然是深度优先的，

• 您从边界的末尾（可能的图块）而不是开头删除。
• 您没有遍历层次结构（父到子）来重建遍历路径，只有一个带有图块的“路径”。因此，深度优先。

需要更改的内容：

• 将 LinkedList 更改为 Dictionary。字典的键将是图块，值将是图块的父级。用它来重建你的最终路径。
• 您的“moveNext”功能可能是正确的。确保它被推到列表的末尾。
• 不要从 MaybeSteps 中弹出 (getLast())。 possibleSteps 应该是先进先出队列。检索可能步骤的第一个图块（这将首先探索最接近起点的图块）。

需要改进的地方：

• 不要使用 Tile 来跟踪探索，而是使用 Set（称为 ExploredTile）来放置已遍历的图块），
• 使用 Queue 而不是 List。

一些 C#/伪代码（因为我不在 IDE）

Dictionary<Tile,Tile> path = ...;
Queue<Tile> frontier = ...;
Set<Tile> explored = ...;

path[start] = null;

while(frontier.Count > 0){
    var tile = frontier.Dequeue();

    if(explored.Contains(tile)){
        continue;
    }
    explored.add(tile);

    if (Tile == Exit){
        rebuildPath(Exit);
    }else{
        for (Tile t in Tile.neighbours){
            if (!explored.Contains(t)){
                frontier.Enqueue(t);
                path[t] = tile; // Set the path hierarchy
            }
        }
    }
}

RebuildPath

LinkedList<Tile> finalPath = ...;

Tile parent = path[exitTile];
finalPath.push(exitTile);

while(parent != null){
    finalPath.push(parent);
    parent = path[parent];
}

finalPath.reverse();

希望我做对了...:)