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

関数型言語は、ヒープを節約する末尾再帰を採用することで、ここで役立ちます。残念ながら、JVMは末尾再帰をサポートしていないようです（少なくともJavaの場合）。このSOの質問を参照してください。

手で末尾再帰をエミュレートしてみることができます。

于 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 に答える
1

プログラムでの主なヒープの使用法は、実際に疑わしい場所であるようです。の新しい配列を初期化するときですsize pieces.length -1。 ここで実際に多くのスペースを節約できることに
注意してください！実際には「最も深い」セットのみを使用するためです。

それでも配列を使用したい場合は、追加のパラメーターを渡し、新しい配列を割り当てる代わりに、各ステップでarrのi番目とk番目の要素を交換するstart実装を行うことができます。再帰ステップの新しい関数に。常に最後の要素を交換するため、次の手順では、配列の位置の後にあるため、交換は考慮されないことに注意してください。つまり、基本的に、アルゴリズムは「振り返る」ことはないので、これらの要素を入れ替えるのに問題はありません...swap(arr,i,k)swap(pieces,start,i)start+1start

次のようになります。

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 に答える