BFSの検索を実装する方法〜のjava

Question

はここに私のコードです：

private void doBfs(HiRiQ node, ArrayList<HiRiQ> queue, ArrayList<HiRiQ> path, ArrayList<HiRiQ> visited) { 
    while(!queue.isEmpty()){ 
     HiRiQ current = queue.remove(0); 
     if(current.IsSolved()){ 
      current.print(); 
      System.out.println("Path found !"); 
      return; 
     } else {  
      if(current.getAllNextStates().isEmpty()){ 
       return; 
      } else { 
       queue.addAll(current.getAllNextStates()); 
      } 
     } 
     visited.add(current); 
    } 
} 

私はこの方法を継続する方法を考え出す苦労しています。私は他のメソッドにアクセスすることなく、それが複雑になる必要があることを知っているが、私はちょうどこのBFS-検索アルゴリズムに欠けているかを知りたいです。

このBFS検索の目標は、「ノード」から始まる解決の設定を見つけることが可能であれば見つけることにする必要があります。

注：HiRiQはパズルボード（この場合ゲームはペグソリティアパズル）の設定​​を表し、getAllNextStates（）メソッドは現在のものから1つ離れたすべての異なるボード構成を生成します。

私はそれだけで任意の解決策を見つけることができません、それを実行すると、それは果てしなく実行されます。

Answer 1

私はあなたの幅優先（私はあなたがそれに不明で感じる原因）のアイデアを与える、ための、簡単なバイナリツリーを言わせて、それはあなたのためにそれをより明確にする必要があります。

が、これは私たちの木であると言います。

  1 
    /   \ 
    2    3 
/ \  / \ 
4  5  6  7 

ここで、幅優先探索を行う必要があるので、キューのデータ構造を見てください。

queue -> [] 

queueが空でないながら...

- pop the first element, i.e. 1 
- if it has a left child, add it to the queue [2] 
- if it has a right child, add it to the queue [2,3] 
- repeat 

どのようにこの作品がするqueue

queue -> [1] 

で私たちのルートへの参照を置くことができますか？

pop first element, i.e. 1; queue -> [] 
- if it has a left child, add it to the queue [2] 
- if it has a right child, add it to the queue [2,3] 

pop first element, i.e. 2; queue -> [3] 
- if it has a left child, add it to the queue [3,4] 
- if it has a right child, add it to the queue [3,4,5] 

pop first element, i.e. 3; queue -> [4,5] 
- if it has a left child, add it to the queue [4,5,6] 
- if it has a right child, add it to the queue [4,5,6,7] 

pop first element, i.e. 4; queue -> [5,6,7] 
- if it has a left child, add it to the queue [5,6,7] 
- if it has a right child, add it to the queue [5,6,7] 

pop first element, i.e. 5; queue -> [6,7] 
- if it has a left child, add it to the queue [6,7] 
- if it has a right child, add it to the queue [6,7] 

pop first element, i.e. 6; queue -> [7] 
- if it has a left child, add it to the queue [7] 
- if it has a right child, add it to the queue [7] 

pop first element, i.e. 7; queue -> [] 
- if it has a left child, add it to the queue [] 
- if it has a right child, add it to the queue [] 

queue is empty 

あなたのご理解とご協力をお願いします。

Answer 2

@DebosmitRayが指摘しているように、おそらくノードが既に訪問されたことを確認しないことが問題です。だからあなたの検索はおそらく無限ループに陥るでしょう。

ここをクリックして、JavaでBFSを実装するための概略フレームワークを示します。自分自身でゲーム/ドメイン固有のロジックを実装する必要があります。作品の構成、選手が勝ったかどうかのテスト。これはStateオブジェクトの内部で実装することができます。

interface State{ 
    public List<State> getNeighbors(); 
    public boolean isGoal(); 
} 

A BFSは、親状態にリンクされている状態を検索します。

private void doBfs(State start) { 

    List<Node> openList = new ArrayList<>(); 
    Set<Node> closedSet = new HashSet<>(); 

    Node startNode = new Node(start,null); 
    openList.add(startNode); 

    while (!openList.isEmpty()) { 

     Node current = openList.remove(0); 

     //If this node has already been visited, skip it 
     if(closedSet.contains(current)) continue; 


     //check if the current node is a goal (solution) node 
     if (current.isGoal()) { 

      System.out.println("Path found !"); 

      //print the path by iterating over the parents 
      for(Node parent = current; parent != null; parent = parent.getParent()){ 
       System.out.println(parent); 
      } 

      return; 
     } 

     //Add all neighbors to the openList 
     openList.addAll(current.getNeighbors()); 

     //Add the current node to the closed set so that it is not revisted 
     closedSet.add(current); 
    } 

    System.out.println("No solution could be found from the starting state "+ start); 

}