私はCURRノードがすでにそのループから出て行く訪問したただ一つの隣人を持っている場合ことを見<strong>*の_search_algorithm</strong>が、ランタイム で検索方法retuternヌル を実装しようとしたのjava

Question

の* _search_algorithm実装 私はalgを修正するために追加する必要がありますか？一見

public Solution search(Searchable s) { 

    final StateT start = s.getInitialState(); 
    final StateT goal = s.getGoalState(); 

    initPriority(goal); 
    start.setCost(0); 
    openList.add(start); 
    double tempCost; 
    while (!(openList.isEmpty())) { 
     StateT curr = openList.poll(); 
     numOfSteps++; 

     if (curr.equals(goal)) 
      return backTrace(curr); 

     closedState.add(curr); 

     ArrayList<StateT> successors = s.getAllPossibleStates(curr); 
     for (StateT stateT : successors) { 
     } 
     for (StateT successor : successors) { 

      tempCost = curr.getCost() + s.dist_between(curr, successor); 

      if (closedState.contains(successor)) 
       continue; 

      if (!(openList.contains(successor))) 
       openList.add(successor); 

      else if (tempCost >= successor.getCost()) 
       continue; 
      successor.setCameFrom(curr); 
      successor.setCost(tempCost); 
      openList.remove(successor); 
      openList.add(successor); 
     }// for   
     for (StateT stateT : openList) { 
      System.out.println("op: "+stateT.getState());    
     } 
     System.out.println("end"); 
    } 
    return null; 
}// 

public abstract void initPriority(final StateT goal); 


public Solution backTrace(StateT current) { 

    Solution solution = new Solution(); 

    while(current != null){ 

     solution.getPath().add(current); 
     current = (StateT) current.getCameFrom(); 
    } 

    return solution; 
} 

}

Answer 1

が存在する場合、それはパスを見つける必要がありますのように、それは、正しいはずのような実装では、私には見えます。これは、コードを提供しなかったメソッド（getAllPossibleStates()など）が正しく実装されていることを前提としています。

説明したケース（ノードの可能なすべての近隣ノードが既に訪問されている場合）には、追加の処理は必要ありません。これにより、openListが空になり、nullが返される場合は、単にパスが存在しないことを意味します。あなたが行ったテストで、最初から最後までの道があると確信していますか？

このコードは、ノードから目標までのコストを見積るヒューリスティックを含んでいないため、実際にはA *アルゴリズムではなくDijkstraのアルゴリズムを実装しています。