1

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

    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;
    }

}
4

1 回答 1

0

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

有两个地方明显是深度优先

  • 你从边界的末端（可能的Tiles）移除，而不是从开始。
  • 您没有遍历层次结构（父级到子级）来重建遍历路径，只有一个带有瓦片的“路径”。因此，深度优先。

要改变的事情：

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

需要改进的地方：

  • 而不是使用 Tile 来跟踪探索，而是使用一个 Set（称为 ExploredTile），在其中放置已遍历的图块）
  • 使用队列而不是列表。

一些 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
            }
        }
    }
}

重建路径

LinkedList<Tile> finalPath = ...;

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

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

finalPath.reverse();

希望我做对了... :)

于 2012-01-05T03:07:13.453 回答