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

これは幅優先検索ではなく、深さ優先です。

明らかに深さ優先の場所が 2 か所あります

  • 最初ではなく、フロンティアの最後 (possibleTiles) から削除します。
  • トラバーサル パスを再構築するためのトラバーサル階層 (親から子へ) はなく、タイルを含む単一の「パス」のみがあります。したがって、深さ優先です。

変更点:

  • LinkedList の代わりに、Dictionary に変更します。ディクショナリのキーはタイルになり、値はタイルの親になります。これを使用して、最終パスを再構築します。
  • あなたの「moveNext」機能はおそらく正しいでしょう。リストの最後までプッシュしていることを確認してください。
  • PossibleSteps からポップ (getLast()) しないでください。PossibleSteps は先入れ先出しキューである必要があります。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
            }
        }
    }
}

RebuildPath

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 に答える