java - DFS 算法 - 8-Puzzle 或 nXn-Game

Question

我想解决 DFS 算法。它是关于游戏 8-puzzles 或 N x N 拼图。一开始我有两个数组(零代表一个空字段):

int[][] start = {{0,1,2}, {4,5,3}, {7,8,6}};
int[][] target = {{1,2,3}, {1,5,6}, {7,8,0}};

这个数组进入我的通用 DFS 类，它工作正常。我正确地将它用于其他任务。但为了完整起见，这里是我的 DFS 类的 basic 部分:

private static boolean search(State node, State target) {
    if (node.equals(target))
        return true;

    for (State neighbour : node.getNeighbours()) {
        if (!visited.contains(neighbour)) {
            predMap.put(neighbour,node);
            visited.add(neighbour);
            if (search(neighbour, target)){
              return true;
            }
        }
    }
    return false;
}

所以一开始我的 start 数组将作为第一个参数传递，而我的 target 数组作为第二个参数传递。

在我的 State 类中，我想实现 getNeighbours() 方法，它应该返回所有可能的状态。在第一轮是这样的:

First:
|0|1|2|
|4|5|3|
|7|8|6|

Second (rotated zero):
|1|0|2|
|4|5|3|
|7|8|6|

etc...

这是我的问题。你怎么能那样做？它适用于前 4 个操作，但随后出现异常(零或空字段不在异常位置或有两个零)。那里有什么问题？

@Override
public List<State> getNeighbours() {
    List<State> neighbours = new LinkedList<>();

    // possibles moves...
    final int startX = (freeX - 1 < 0) ? freeX : freeX - 1;
    final int startY = (freeY - 1 < 0) ? freeY : freeY - 1;
    final int endX = (freeX + 1 > N - 1) ? freeX : freeX + 1;
    final int endY = (freeY + 1 > N - 1) ? freeY : freeY + 1;

    for (int row = startX; row <= endX; row++) {
        for (int column = startY; column <= endY; column++) {
            int tmp = board[row][column];
            board[row][column] = board[freeX][freeY];
            board[freeX][freeY] = tmp;

            // Just show the table...
            System.out.println("=== BEFORE ===");
            for (int[] x : board) {
                System.out.println(Arrays.toString(x));
            }

            neighbours.add(new State(board, freeX + row, freeY + column));

            board[freeX][freeY] = board[row][column];
            board[row][column] = tmp;

            // Just show the table...
            System.out.println("=== AFTER ===");
            for (int[] x : board) {
                System.out.println(Arrays.toString(x));
            }
        }
    }

    return neighbours;    
}

完整代码https://gist.github.com/T0bbes/66d36326aa8878d5961880ce370ba82d

Answer 1

我检查了你的代码，得到那个异常的原因是，board 数组由每个状态共享。您应该对该数组进行深度复制，您可以尝试使用以下代码:

public Board(int[][] board, int x, int y){
    if (board[x][y]!=0)
        throw new IllegalArgumentException("Field (" +x+","+y+") must be free (0).");
    this.board = new int[board.length][board[0].length];
    for (int i = 0; i < this.board.length; i++)
        for (int j = 0; j < this.board[i].length; j++)
            this.board[i][j] = board[i][j];
    this.freeX = x;
    this.freeY = y;
    this.N = board.length;
}

但是你的代码还存在一些问题:

1. DFS 可能会多次递归并得到 StackOverflow——您应该增加堆栈大小(-Xss100m 对我有用)。增加堆栈大小后，您的代码可以输出解决方案，但需要 197144 步...

2. 确实，如您所见，DFS 仅输出有效解决方案(如果您的代码正确)，而不是最佳解决方案。你应该试试 BFS。