6

私は、Javaで幅優先検索を実装するための学校の演習として持っています。私はほとんどすべてを実装しましたが、問題は検索が機能せず、問題を見つけることができないことです:(だから私にアドバイスを求め、最終的な問題がどこにあるのかについてのガイドラインを教えてください。

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 = new SearchNode(startState); 

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


        do {  

          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.addNodeToFront(child); 
              }

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


        return path;
    }

ありがとうございました

4

2 に答える 2

8 
frontier.addNodeToFront(child);

assuming the rest of your code (getReachableStatesFrom(), etc) is correct, adding elements to the front of your queue will cause your code to execute as a depth first search.

于 2012-09-23T19:34:09.953 に答える
0

幅優先検索を実装するには、キューを使用する必要があります。このプロセスは非常に複雑になる場合があります。そのため、シンプルに保つことをお勧めします。ノードの子をキューにプッシュし (左から右へ)、ノードにアクセスします (データを出力します)。次に、ノードをキューから削除する必要があります。キューが空になるまで、このプロセスを続行する必要があります。ここで BFS の実装を確認できます: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java

于 2016-08-07T00:16:49.310 に答える