デプスファーストサーチアルゴリズムが無限ループに陥るのを防ぐために8 Puzzle

Question

私のコードは基本的な8個のパズルの問題に対応していますが、より難しいパズル構成でテストすると無限ループになります。これを防ぐためにコードを編集してください。ループまたはサイクルを防ぐコードが含まれていることに注意してください。私は反復的な深さの最初の検索技術を含めてみましたが、それも機能しませんでした。誰かが私のコードを確認してください。

/** Implementation for the Depth first search algorithm */ 
static boolean depthFirstSearch(String start, String out){  

    LinkedList<String> open = new LinkedList<String>(); 
    open.add(start); 

    Set<String> visitedStates = new HashSet<String>();  // to prevent the cyle or loop 

    LinkedList<String> closed = new LinkedList<String>(); 

    boolean isGoalState= false; 

    while((!open.isEmpty()) && (isGoalState != true)){ 

     String x = open.removeFirst(); 

     System.out.println(printPuzzle(x)+"\n\n"); 
     jtr.append(printPuzzle(x) +"\n\n"); 

     if(x.equals(out)){    // if x is the goal 
      isGoalState = true; 
      break; 
     } 
     else{ 
                   // generate children of x 
      LinkedList<String> children = getChildren(x); 

      closed.add(x);    // put x on closed 
      open.remove(x);    // since x is now in closed, take it out from open 

      //eliminate the children of X if its on open or closed ? 
      for(int i=0; i< children.size(); i++){ 
       if(open.contains(children.get(i))){ 
        children.remove(children.get(i)); 
       } 
       else if(closed.contains(children.get(i))){ 
        children.remove(children.get(i)); 
       } 
      } 


      // put remaining children on left end of open 
      for(int i= children.size()-1 ; i>=0 ; i--){ 
       if (!visitedStates.contains(children.get(i))) { // check if state already visited 
         open.addFirst(children.get(i));    // add last child first, and so on 
         visitedStates.add(children.get(i)); 
       } 
      } 

     } 
    } 

     return true; 
    } 

Answer 1

私は、あなたは彼らが解決されることにどれだけ近いかに基づいて優先順位を持つhttps://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.htmlに検討している位置を置くことを示唆しています。

だから、キューから最も近い位置をとり、まだ処理されていない1つの移動オプションをすべて追加します。その後、繰り返します。永遠に無作為に移動するのではなく、解決に近い可能性を探索するために、ほとんどの時間を費やします。

ここであなたの質問は「どれくらい近く解決しているか」です。 1つの方法は、四角形がどこにあるか、どこにある必要があるかの間のすべてのタクシーの距離の合計を取ることです。より良いヒューリスティックは、最初にコーナーから四角形を取り除くことに重点を置くことです。あなたがそれを正しくするならば、あなたのヒューリスティックを変えるのは簡単なはずです。