どうすればBFSの検索でキューのサイズを制限することができます〜のJava

Question

ここに私のBFSの検索方法である：

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 { 


       if(queue.contains(current)){ continue; } 

       else if (visited.contains(current)){ continue; } 


       else{ queue.addAll(current.getAllNextStates()); } 



      } 
       visited.add(current); 
      } 
     } 
     } 

それが見つかるまで、このアルゴリズムは、おそらくペグソリティアパズル構成から開始し、チェックし、すべてのネイバーコンフィギュレーション解決された構成。それは動作するように見えますが、任意の構成では、実行して解決策を見つけるのに本当に長い時間がかかります。

この検索アルゴリズムを最適化する方法の1つは、キューのサイズを制限することです。特定のポイントの後には、キューに多くのノードを配置し、ノードを実際に処理する時間をほとんど費やすことができないからです。だから、ある時点で私はキューを埋めるのを止めて、あなたのキューで待っている解決策があるかどうかをチェックするだけです。

どうすればこの問題を解決できますか？ありがとうございます

Answer 1

iterative deepening depth-first searchを使用することをお勧めします。メモリが大事な時に設計されていて、いくつかのグラフの問題のBFSベースの単純なソリューションは、すべての利用可能なRAMを簡単に食べる可能性があります。しかし、それはあなたが到達したい、キューのサイズを制限する、最短パスの解決策を見つけることを保証し、分岐ファクタが高い場合はBFSより高速です。

ソリューションのパフォーマンスを向上させるもう1つの方法は、パズルを解決するための優れたヒューリスティックを見つけることです。コードを作成できるヒューリスティックができたら、あなたの運を試すことができますA* algorithm