使用递归回溯时耗尽堆

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

看来您的程序中的主要堆使用情况确实是您怀疑的地方：初始化 sizepieces.length -1 的新数组时。

请注意，这里您确实可以节省大量空间！因为您实际上只使用“最深”的集合。

如果您仍然想使用数组，您可能需要传递一个额外的参数：start，并实现 swap(arr,i,k) 来交换第 i 个数组和 arr 中的第 k 个元素，并且在每个步骤中，不是分配新数组，而是 swap(pieces,start,i)，并传递给新函数 start+1 code> 在递归步骤中。请注意，由于您总是交换最后一个元素，因此接下来的步骤不关心交换，因为它们位于数组的 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 而言），请参阅

您可以尝试手动模拟尾递归。

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;
        }
    }
}