使用遞歸回溯時用盡堆

Question

我目前正在研究遞歸回溯的美麗主題。 我已經嘗試過尋找經典的例子，例如尋找迷宮中的最短路徑或n皇后問題。但是我現在正在處理的問題真的讓我感到困惑： 其實，我認爲這可能是一個簡單的練習來解決一個簡單的拼圖 - 謎題： 我有一個大小爲n = a * b的板子，很多（n）件。
最後我想把所有的東西都按照一定的順序放在棋盤上，在那裏他們遵守某些限制（比如和他們的鄰居相匹配）。相當容易，我想，我想出了下面的算法：

public board recursiveSolve(Board board, Piece[] pieces, int position){ 
// base case 
if(position == board.getLength()) 
    return board; 
else{ 
    // For each possible piece 
    for(int i = 0; i < pieces.length; i++){ 
     // if the piece is placeable at that position 
     // place it and search on recursively 
     if(board.isValid(piece[i], position)){ 
      board.putPiece(pieces[i], position); 

      // THIS IS THE FISHY PART!! 
      // Now I need to pass a set of pieces to the function recursively 
      // that does not contain the current one (pieces[i]) 
      // But I fear my (following) approach is too heap-intensive 

      Piece[] subPieces = new Piece[pieces.length - 1]; 

      // fill subPieces with all elements from pieces except from the one 
      // at position i 
      for (int j = 0; j < subPieces.length; j++) { 
       if(j >= i) 
        subPieces[j] = pieces[j+1]; 
       else 
        subPieces[j] = pieces[j]; 

      } 

      if(recursiveSolve(board, subPieces, position + 1) != null) 
       return board; 
      else 
       board.removePiece(position); 
     } 
    } 
    // If this is reached, none of the pieces have worked -> go back 
    return null; 

} 

嗯，基本上，這個算法做它應該做的 - 但不幸的是它僅適用於「小」板尺寸（N < 100）。 因爲如果我有一塊像10 x 10平方塊和100塊的板子，函數將搜索並搜索，直到由於堆空間不足而導致JVM崩潰時纔會結束。 我甚至嘗試將eclipse的內存大小限制設置爲1.2g，這使得該功能的工作時間更長，但仍然不夠。

所以我的問題是：是否有可能優化上面的算法，使它適用於板尺寸n> 100？我究竟做錯了什麼？還是我採取了完全錯誤的做法？

非常感謝您的幫助提前。

Answer 1

似乎在程序主堆的使用確實是在那裏你懷疑：初始化的size pieces.length -1新的數組時。
請注意，你確實可以在這裏節省很多空間！因爲你實際上只使用'最深'的一套。

如果你還是想用一個數組，你可能想傳遞一個額外的參數：start，並實現swap(arr,i,k)其交換ARR中第i個和第k個元素，並且在每一個步驟，而不是分配新數組，swap(pieces,start,i)，並在遞歸步驟中傳遞給新函數start+1。請注意，因爲您總是交換最後一個元素，所以接下來的步驟不會考慮交換，因爲它們位於數組的start之後。所以基本上，因爲算法從來沒有「回頭看」，所以你不會有任何問題交換這些元素......

看起來應該是這樣的：

public board recursiveSolve(Board board, Piece[] pieces, int position,int start){ 
if(position == board.getLength()) 
    return board; 
else { 
    //starting from start instead from 0 
    for(int i = start; i < pieces.length; i++){ 
     if(board.isValid(piece[i], position)){ 
      board.putPiece(pieces[i], position); 
      swap(pieces,start,i); //the swap() method I mentioned above   
      //sending start+1: 
      if(recursiveSolve(board, subPieces, position + 1,start+1) != null) 
       return board; 
      else 
       board.removePiece(position); 
     } 
    } 
    return null; 
} 

你可能知道，回溯算法是耗時的，因此，即使與空間優化的版本，該算法可能會遇到很長一段時間[指數！]直到找到答案。

Answer 2

函數式語言將通過使用尾遞歸來幫助這裏，這將節省堆。不幸的是，似乎JVM不支持尾遞歸（至少對於Java），請參閱this SO question

您可以嘗試手動模擬尾遞歸。

Answer 3

由於董事會有一種方法可以告訴你piece [i]是否在某個位置上有效，在繼續前重複位置並嘗試每個（剩餘的）塊在該位置是否更有意義？它不會使用遞歸（這將解決你的堆空間問題），但是如果你是在遞歸解決方案之後，它顯然不適合。

爲了更有效地做到這一點，我會建議將這些作品放入一個列表中，然後在放置它時刪除一個作品。事情是這樣的：

List<Piece> remainingPieces = new ArrayList<Piece>(Arrays.asList(pieces)); 
int numberOfPositions = // I assume you have some way of finding this. 
for (int position = 0; position < numberOfPositions; position++) { 
    Iterator<Piece> it = remainingPieces.iterator(); 
    while (it.hasNext()) { 
     Piece temp = it.next(); 
     if (board.isValid(temp, position)) { 
      board.putPiece(temp, position); 
      it.remove(); 
      break; 
     } 
    } 
}