廣度優先搜索 - 不返回路徑（正確路徑）

-1

我的廣度優先搜索存在問題。我們將學校練習作爲一個代碼模板來實現廣度優先搜索。廣度優先搜索 - 不返回路徑（正確路徑）

我已經根據書中的僞代碼人工智能 - 現代方法實現了BFS，但我無法使其工作。測試程序根本沒有返回路徑。

public class CustomGraphSearch implements SearchObject { 

    private HashSet<SearchNode> explored; 
    private NodeQueue frontier; 
    protected ArrayList<SearchNode> path; 
    private boolean insertFront; 

    /** 
    * The constructor tells graph search whether it should insert nodes to front or back of the frontier 
    */ 
    public CustomGraphSearch(boolean bInsertFront) { 
     insertFront = bInsertFront; 
    } 

    /** 
    * Implements "graph search", which is the foundation of many search algorithms 
    */ 
    public ArrayList<SearchNode> search(Problem p) { 
     // The frontier is a queue of expanded SearchNodes not processed yet 
     frontier = new NodeQueue(); 
     /// The explored set is a set of nodes that have been processed 
     explored = new HashSet<SearchNode>(); 
     // The start state is given 
     GridPos startState = (GridPos) p.getInitialState(); 
     // Initialize the frontier with the start state 
     frontier.addNodeToFront(new SearchNode(startState)); 

     // Path will be empty until we find the goal. 
     path = new ArrayList<SearchNode>(); 

     // The start NODE 
     SearchNode node; 

     // Check if startState = GoalState?? 
     if(p.isGoalState(startState)){ 
      path.add(new SearchNode(startState)); 
      return path; 
     } 


     do { 

      if(frontier.isEmpty()) { 
       return path; 
      } 

      node = frontier.removeFirst(); 
      explored.add(node); 

      ArrayList reachable = new ArrayList<GridPos>(); 
      reachable = p.getReachableStatesFrom(node.getState()); 

      SearchNode child; 

      for(int i = 0; i< reachable.size(); i++){ 

       child = new SearchNode((GridPos)reachable.get(i)); 

       if(!explored.contains(child) || !frontier.contains(child)){ 
        if(p.isGoalState(child.getState())){ 
         path = child.getPathFromRoot() ; 
         return path; 
        } 

        frontier.addNodeToBack(child); 

       } 

      } 
     }while(!frontier.isEmpty()); 

     return path; 
}

我將不勝感激任何幫助和建議。

來源

2012-09-24 mrjasmin

你能更具體嗎？你有沒有空路？ – Tudor

聽起來像問題是在'child.getPathFromRoot（）' - 顯示我們的代碼。 –

@Tudor：（s）他得到一個無限循環，因爲孩子們在探索後不斷重新添加到'frontier'。（看我的答案。） – ruakh

有一些問題在這裏，但我認爲關鍵問題是這樣的：

if(!explored.contains(child) || !frontier.contains(child)){

需要爲任一：

if(!explored.contains(child) && !frontier.contains(child)){ 

if(! (explored.contains(child) || frontier.contains(child))){

（如果不響鐘，然後閱讀the "De Morgan's laws" article on Wikipedia。）

來源

2012-09-24 19:17:57 ruakh

嗨！謝謝你，非常笨拙的我，但它仍然不工作:(我似乎它探索了正確的節點，但它並沒有繪製一條通往目標的路徑（我有一個圖形界面） – mrjasmin

我也得到目標不可達的消息:( – mrjasmin

廣度優先搜索 - 不返回路徑（正確路徑）

回答

相關問題