java - 高峰期求解器遇到无限循环任何不平凡的难题

Question

所以我正在用 Java 编写一个高峰时间求解器，这意味着能够解决配置 here 。然而，即使是该页面中最简单的谜题也会导致求解器无限运行并最终耗尽内存。我使用广度优先搜索来完成每个棋盘状态产生的所有可能的移动(使用哈希集来确保我不会重复自己)，并将每个状态映射到到达那里的移动，以便我可以回溯稍后通过他们。

问题是，我已经尝试过用我自己想出的更琐碎的谜题来解决它们，并且它能够解决它们(尽管很慢)。

我处理这个问题的方式有什么明显的错误吗？如果需要的话，我也可以从相关类中提供一些代码，但是我已经非常彻底地测试了它们，并且我很确定问题出在下面的代码中的某个地方。我的直觉告诉我，这与 HashSet 有关，并确保我不会重复自己(因为队列的大小经常达到数十万)。

有什么建议吗？

    // Start at the original configuration
    queue.add(originalBoard);

    // We add this to our map, but getting here did not require a move, so we use
    // a dummy move as a placeholder move
    previous.put(originalBoard, new Move(-1, -1, "up"));

    // Breadth first search through all possible configurations
    while(!queue.isEmpty()) {
        // Dequeue next board and make sure it is unique
        Board currentBoard = queue.poll();
        if (currentBoard == null)           continue;
        if (seen.contains(currentBoard))    continue;
        seen.add(currentBoard);

        // Check if we've won
        if (currentBoard.hasWon()) {
            System.out.println("We won!");
            currentBoard.renderBoard();
            return solved(currentBoard);
        }

        // Get a list of all possible moves for the current board state
        ArrayList<Move> possibleMoves = currentBoard.allPossibleMoves();

        // Check if one of these moves is the winning move
        for (Move move : possibleMoves) {
            Board newBoard = move.execute(currentBoard);

            // We don't need to enqueue boards we've already seen
            if (seen.contains(newBoard))   continue;
            queue.add(newBoard);

            // Map this board to the move that got it there
            previous.put(newBoard, move);
        }
    }

根据要求，这是我对 HashSet 的初始化(它们是类级别变量):

private static HashSet<Board> seen = new HashSet<>();

还有我的 Board.equals() 方法:

@Override
public boolean equals (Object b) {
    Board otherBoard = (Board) b;
    boolean equal = false;
    if (this.M == otherBoard.getM() && this.N == otherBoard.getN()) {
        equal = true;

        // Each board has an ArrayList of Car objects, and boards are only
        // considered equal if they contain the exact same cars
        for (Car car : this.cars) {
            if (otherBoard.getCar(car.getPosition()) == null) {
                equal = false;
            }
        }
    }
    System.out.println(equal);
    return equal;
}

Answer 1

您必须实现 Board.hashCode() 来覆盖默认的基于 Object 的版本，按照其约定，任何两个相等的 Board 对象具有相同的哈希码。如果您不这样做，那么您的 seen 集实际上不会为您完成任何事情。

关于另一个问题，我怀疑您检查董事会车辆的方式并不完全正确。如果它按照我认为的方式工作，它会认为这两个板是相等的: . = 空白 * = 汽车的一部分

......
.**.*.
....*.
.*....
.*.**.
......

......
.*..**
.*....
......
.**.*.
....*.