0

此代码适用于 5x5、6x6、7x7，但在 8x8 中内存不足。我将内存增加到2048M，但它仍然不起作用。代码应该使用 Stack 类和回溯作为解决方案的一部分这是代码：

private int counter=0;
private boolean grid[][]=new boolean [ROWS][COLS];
private  Stack tour=new Stack(0,0);
private int spaces=ROWS*COLS;
private int[][] intGrid=new int[ROWS][COLS];


private static final Point[] Moves=new Point[]{
    new Point(-1, -2),
    new Point(-1, 2),
    new Point(1, -2),
    new Point(1, 2),
    new Point(-2, -1),
    new Point(-2, 1),
    new Point(2, -1),
    new Point(2, 1),
};

public void run(){
    fillIntGrid();
    tourFrom(tour.first);
    println("SOLUTION FOUND:");
    printBoard();
}

public boolean tourFrom(Point currPoint){
    counter++;
    grid[currPoint.xCoord][currPoint.yCoord] = true;
    intGrid[currPoint.xCoord][currPoint.yCoord]=counter;
    if(counter==spaces)
        return true;
    for(Point nextMove:Moves){
        int nextRow=currPoint.xCoord+nextMove.xCoord;
        int nextCol =currPoint.yCoord+nextMove.yCoord;
        tour.push(nextRow,nextCol);
        if(nextRow<0 || nextRow>=grid.length)
            continue;
        else if(nextCol<0 || nextCol>=grid.length)
            continue;
        else if(grid[nextRow][nextCol])
            continue;
        if(tourFrom(tour.first))
            return true;
        } 
    grid[currPoint.xCoord][currPoint.yCoord] = false;
    intGrid[currPoint.xCoord][currPoint.yCoord]=0;
    counter--;
    tour.pop();
    return false;
}

public void fillIntGrid(){
    for(int i=0;i<ROWS;i++){
        for (int j=0;j<COLS;j++){
            intGrid[i][j]=0;
        }
    }
}

可能的问题是什么？

4

1 回答 1

4

因为这是一个编程练习......

push提示：比较pop在tourFrom.

好的，这就是我用来解决这个问题的逻辑。

这不是一个无限递归问题，因为那会给出 a StackOverflowError，而不是 a OutOfMemoryError。

AnOutOfMemoryError表示某种存储泄漏。（可能还有其他问题……但让我们继续研究存储泄漏的想法。）

问：哪一个是唯一可能无限大小的数据结构？

答：堆栈。

问：它怎么能无限增长？

A：如果你做的推送多于弹出。

所以看看推送和弹出代码......

问：但是 6x6 和 7x7（据说）如何工作？

答：算一算:-)

退一步看解决方案，还有其他问题。例如，您没有使用tourFrom. 这意味着您将始终报告找到了解决方案，并且在找到解决方案时您不会停止。

我真的怀疑 >>this<< 代码是否适用于较小的电路板尺寸。

于 2014-05-05T15:06:55.033 回答