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

これは、幅広い最初の検索ではありません。これは深さ優先です。

は明らかに

• あなたはフロンティア（possibleTiles）の末尾から削除第1の深されている2ヶ所、ない初めがあります。
• トラバーサルパスを再構築するためのトラバーサル階層（親から子）はなく、タイル付きの単一の「パス」のみです。したがって、まず深さです。

変更するもの：

• 代わりのLinkedListの、辞書にそれを変更します。辞書のキーはタイルになり、値はタイルの親になります。これを使用して最終パスを再構築します。
• あなたの「moveNext」機能はおそらく正しいでしょう。リストの最後まで押していることを確認します。
• PossibleStepsからポップ（getLast（））しません。 PossibleStepsはFirst-In-First-Outキューである必要があります。 PossibleStepsの最初のタイルを取得します（これは最初に最初に最も近いタイルを探索します）。改善する

もの：

• 代わりに探査を追跡するためにタイルを使用するのではなく、代わりに、リストのキューを使用して、あなたが横断したタイルを置くセット（ExploredTileそれを呼び出す））
• を使用。

いくつかのC＃/疑似コード（私はIDEではないよcuzを）

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(); 

がうまくいけば、私は右のそれを得た... :)