2

我目前正在研究递归回溯这个美丽的话题。我已经尝试过经典的例子，比如找到迷宫中的最短路径，或者 n-queens 问题。但是我现在正在处理的问题确实让我感到困惑：实际上，我认为解决一个简单的拼图游戏可能是一个简单的练习：我有一块大小为 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 的电路板尺寸？我究竟做错了什么？还是我采取了完全错误的方法？

非常感谢您提前提供的帮助。

4

3 回答 3

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

您可能知道回溯算法非常耗时 [指数！]，因此即使使用空间优化版本，该算法也可能会运行很长时间，直到找到答案。

于 2011-10-22T00:43:19.620 回答
1

函数式语言将通过使用可以节省堆的尾递归来提供帮助。不幸的是，似乎 JVM 不支持尾递归（至少对于 Java），请参阅这个 SO question

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

于 2011-10-21T15:35:25.627 回答
1

既然棋盘有一种方法可以告诉您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;
        }
    }
}
于 2011-10-21T15:40:22.877 回答