防止深度優先搜索算法陷入無限循環，8拼圖

-4

所以我的代碼適用於基本的8拼圖問題，但是當我用較難拼圖配置測試時，它會運行到無限循環。有人可以編輯我的代碼，以防止這種情況發生。請注意，我已包含防止循環或循環的代碼。我嘗試了包括迭代深度優先搜索技術，但這也不起作用。有人可以查看我的代碼。防止深度優先搜索算法陷入無限循環，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; 
    }

來源

2017-08-17 Michael André Slimz

你需要學習如何調試你自己的代碼。從這裏開始：https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – shmosel

我請求某人查看算法，而不是讓某人告訴我調試我自己的代碼。你錯了。 –

你不能總是得到你要求的。即使你這麼做，從長遠來看，它也無濟於事。學習調試自己的代碼是您需要有效編碼的最關鍵的技能之一。 – shmosel

我建議把你的基礎上，他們是正在解決如何接近考慮到具有優先級的https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html的位置。

所以你要做的是從隊列中取出最近的位置，然後添加所有尚未處理的一次移動選項。然後重複。你將花費大部分時間來探索接近解決的可能性，而不是僅僅隨機地移動。

現在你的問題是「我們有多接近解決它」。一種方法是將所有出租車之間的距離之和作爲方格之間的位置和他們需要的位置之間的距離。一個更好的啓發式可能是讓更多的權重讓廣場遠離角落。如果你做得對，改變啓發式應該很容易。

來源

2017-08-18 00:06:08 btilly

防止深度優先搜索算法陷入無限循環，8拼圖

回答

相關問題