深度優先搜索早期終止

Question

我正在用Java創建一個程序，它不使用啓發式就解決了n-puzzle，只是對狀態空間進行深度優先搜索和廣度優先搜索。我在深度優先搜索的實現上掙扎了一些。有時候它會解決給定的難題，但有些時候它似乎早就放棄了。

這是我的DFS類。 DepthFirstSearch（）傳遞一個PuzzleBoard，它最初是通過對一個已解決的板進行混洗而生成的（以確保該板處於可解的狀態）。

public class DepthFirst { 
static HashSet<PuzzleBoard> usedStates = new HashSet<PuzzleBoard>(); 

public static void DepthFirstSearch(PuzzleBoard currentBoard) 
{ 
    // If the current state is the goal, stop. 
    if (PuzzleSolver.isGoal(currentBoard)) {  
     System.out.println("Solved!"); 
     System.exit(0); 
    } 

    // If we haven't encountered the state before, 
    // attempt to find a solution from that point. 
    if (!usedStates.contains(currentBoard)) {      
     usedStates.add(currentBoard);   
     PuzzleSolver.print(currentBoard); 

     if (PuzzleSolver.blankCoordinates(currentBoard)[1] != 0) { 
      System.out.println("Moving left"); 
      DepthFirstSearch(PuzzleSolver.moveLeft(currentBoard)); 
     } 
     if (PuzzleSolver.blankCoordinates(currentBoard)[0] != PuzzleSolver.n-1) { 
      System.out.println("Moving down"); 
      DepthFirstSearch(PuzzleSolver.moveDown(currentBoard)); 
     } 
     if (PuzzleSolver.blankCoordinates(currentBoard)[1] != PuzzleSolver.n-1) { 
      System.out.println("Moving right"); 
      DepthFirstSearch(PuzzleSolver.moveRight(currentBoard)); 
     } 
     if (PuzzleSolver.blankCoordinates(currentBoard)[0] != 0) { 
      System.out.println("Moving up"); 
      DepthFirstSearch(PuzzleSolver.moveUp(currentBoard));  
     } 

     return; 
    } else { 
     // Move up a level in the recursive calls 
     return; 
    } 
} 
} 

我可以斷言，我爲moveUp（），moveLeft（），MoveRight的（）和下移（）方法和邏輯正常工作，所以這個問題必須位於其他地方。

這裏是我的PuzzleBoard對象類將hashCode和equals方法：

static class PuzzleBoard { 
    short[][] state;   
    /** 
    * Default constructor for a board of size n 
    * @param n Size of the board 
    */ 
    public PuzzleBoard(short n) { 
     state = PuzzleSolver.getGoalState(n); 
    } 
    public PuzzleBoard(short n, short[][] initialState) { 
     state = initialState; 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + Arrays.deepHashCode(state); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) { 
      return true; 
     } 
     if (obj == null) { 
      return false; 
     } 
     if (getClass() != obj.getClass()) { 
      return false; 
     } 
     PuzzleBoard other = (PuzzleBoard) obj; 
     for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
       if (state[i][j] != other.state[i][j]) 
        return false; 
      } 
     } 
     return true; 
    } 
} 

如前所述，有時候搜索的正常工作，並找到解決的路徑，但有時它停止它找到一個解決方案之前，並在內存耗盡之前。

這是輸出的一個片段，在搜索停止搜索之前開始幾個步驟。

... 
Moving down 
6 1 3 
5 8 2 
0 7 4 
Moving right 
6 1 3 
5 8 2 
7 0 4 
Moving left 
Moving right 
Moving up 
6 1 3 
5 0 2 
7 8 4 
Moving left 
Moving down 
Moving right 
Moving up 
Moving up 
Moving right 
Moving down 
Moving up 
Moving down 
Moving up 
Moving down 
Moving up 
Moving down 
Moving up 
Moving down 
... 

爲簡明起見，我提前截斷了它，但它最終只是上下移動數十次，從未達到解決的狀態。

任何人都可以闡明我做錯了什麼？

編輯：這裏是MoveUp（）。其餘的移動方法以相同的方式實現。

/** 
* Move the blank space up 
* @return The new state of the board after the move 
*/ 
static PuzzleBoard moveUp(PuzzleBoard currentState) { 
    short[][] newState = currentState.state; 
     short col = blankCoordinates(currentState)[0]; 
     short row = blankCoordinates(currentState)[1]; 
     short targetCol = col; 
     short targetRow = row; 
     newState[targetCol][targetRow] = currentState.state[col - 1][row]; 
     newState[targetCol - 1][targetRow] = 0; 

     return new PuzzleBoard(n, newState); 
    } 

Answer 1

我曾在儘量不存儲對象HashSet的，但試圖將對象編碼爲字符串過去最好的東西用一個HashSet很多問題。

這裏是一個辦法做到這一點： -

StringBuffer encode(PuzzleBoard b) { 

    StringBuffer buff = new StringBuffer(); 

    for(int i=0;i<b.n;i++) { 

     for(int j=0;j<b.n;j++) { 

      // "," is used as separator 
      buff.append(","+b.state[i][j]); 

     } 
    } 
    return buff; 
} 

Make two changes in the code:- 

if(!usedStates.contains(encode(currentBoard))) { 

usedStates.add(encode(currentBoard)); 
...... 

} 

注： -這裏沒有必要寫自己的哈希碼功能&也沒有必要實現equals功能的Java已經做它爲您在StringBuffer的。

Answer 2

我在你的執行的問題之一： -

在次下面的代碼： -

static PuzzleBoard moveUp(PuzzleBoard currentState) { 
    short[][] newState = currentState.state; 
     short col = blankCoordinates(currentState)[0]; 
     short row = blankCoordinates(currentState)[1]; 
     short targetCol = col; 
     short targetRow = row; 
     newState[targetCol][targetRow] = currentState.state[col - 1][row]; 
     newState[targetCol - 1][targetRow] = 0; 

     return new PuzzleBoard(n, newState); 
    } 

這裏使用的是相同的陣列newState從currentState.state的參考，所以當你對newState進行更改，currentState.state也將更改，這將在調用返回時影響DFS。爲了防止你應該初始化一個新的數組。下一步該做什麼： -

static PuzzleBoard moveUp(PuzzleBoard currentState) { 
    short[][] newState = new short[n][n]; 
     short col = blankCoordinates(currentState)[0]; 
     short row = blankCoordinates(currentState)[1]; 
     short targetCol = col; 
     short targetRow = row; 
     for(int i=0;i<n;i++) { 

      for(int j=0;j<n;j++) { 

       newState[i][j] = currentState.state[i][j]; 
      } 

     } 
     newState[targetCol][targetRow] = currentState.state[col - 1][row]; 
     newState[targetCol - 1][targetRow] = 0; 

     return new PuzzleBoard(n, newState); 
    } 

對所有moveup，movingown做這個改變....

此外，我不覺得你的哈希集合正常工作，因爲如果它是那麼你總是會在哈希集中發現你的新狀態，你的程序將停止。如同等於你比較具有相同參考的狀態數組，因此將總是成立。請嘗試使用我的編碼函數作爲散列。