java：廣度第一遍遍跟蹤迷宮

我想實現一個廣度優先遍歷迷宮。這是我迄今使用鏈表的代碼，但我不確定它是否首先搜索寬度。這是做到這一點的正確方法嗎？任何建議，意見？java：廣度第一遍遍跟蹤迷宮

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

}

來源

2012-01-05 trs

做你得到這個工作？你介意分享你的代碼的最終版本嗎？我需要完全一樣的東西。 – 2013-03-07 08:10:15

這不是廣度優先搜索 - 這是深度優先。

有2個地方是明顯的深度第一

您從前沿（possibleTiles）的最後刪除，而不是開始。
你沒有遍歷層次結構（父到子）來重建遍歷路徑，只有一個「路徑」與瓷磚。因此，它是深度優先。

事情改變：而不是鏈表的

，即改爲詞典。字典的關鍵將是瓦片，並且該值將是瓦片的父級。用它來重建你的最終路徑。
您的「moveNext」功能可能是正確的。確保它正在推到列表的末尾。
不能從PossibleSteps中彈出（getLast（））。 PossibleSteps應該是先進先出隊列。檢索PossibleSteps的第一個Tile（這將探索最接近開始的tile）。

事情，以改善：中

而不是使用瓷磚跟蹤勘探，使用Set（稱之爲ExploredTile），你把你所走過的瓷磚）
使用隊列，而不是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();

希望我這樣做是正確... :)

來源

2012-01-05 03:07:13

java：廣度第一遍遍跟蹤迷宮

回答

相關問題