Исчерпание кучи при использовании рекурсивного возврата

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 х 10 квадратов и 100 штук, функция выполняет поиск и поиск и просто не заканчивается до тех пор, пока не произойдет сбой JVM из-за недостатка места в куче.Я даже пытался установить ограничение размера памяти eclipse до 1.2g, что делало функцию более продолжительной, но все же было недостаточно. </p>

Поэтому мой вопрос: возможно ли оптимизировать алгоритм, приведенный выше, чтобы он работал для размеров платы?n> 100?Что я делаю неправильно?Или я придерживаюсь совершенно неправильного подхода?

Спасибо большое за помощь заранее.

Answer 1

Поскольку на доске есть метод, позволяющий определить, является ли фигура [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;
        }
    }
}

Answer 2

Кажется, что основное использование кучи в вашей программе действительно там, где вы подозреваете: при инициализации нового массива size pieces.length -1.
Обратите внимание, что вы действительно можете сэкономить много места здесь! поскольку вы на самом деле используете только самый глубокий набор.

Если вы все еще хотите использовать массив, вы можете передать дополнительный параметр: start и реализовать swap(arr,i,k), который меняет i-й и k-й элементы в arr, и вместо этого на каждом шаге выделения нового массива 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 3

Функциональные языки помогут здесь, используя хвостовую рекурсию, которая сэкономит кучу. К сожалению, кажется, что JVM не поддерживает хвостовую рекурсию (по крайней мере, для Java), см. этот вопрос SO

Вы можете попытаться подражать хвостовой рекурсии вручную.