java - 高峰时间求解器会遇到任何非平凡难题的无限循环

因此，我正在用Java编写一个“高峰时间”求解器，它旨在能够解决here配置。但是，即使是该页面上最简单的难题，也会导致求解器无限运行，并最终耗尽内存。我正在使用广度优先搜索来遍历每个板状态产生的所有可能动作（使用HashSet来确保我不会重复自己），并将每个状态映射到到达该状态的动作，以便我可以回溯通过他们以后。

问题是，我尝试了一些自己想出的更简单的难题，并且能够解决这些难题（尽管速度很慢）。

我如何解决这个问题有什么公然的错误？如果需要，我也可以从相关类中放入一些代码，但是我已经对它们进行了彻底的测试，并且我确定问题出在下面的代码中。我的直觉说这与HashSet有关，并确保我不会重复自己（因为Queue的大小经常达到数十万）。

有什么建议么？

    // 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;
}

最佳答案

您必须实现Board.hashCode()来覆盖默认的基于Object的版本，以这种方式，根据其合同，任何两个相等的Board对象都具有相同的哈希码。如果您不这样做，那么您的seen集实际上根本不会为您完成任何工作。

在另一个问题上，我怀疑您检查电路板汽车的方式不完全正确。如果按我认为的方式工作，它将认为这两个委员会是平等的：
. =空白
* =汽车的一部分

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

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

关于java - 高峰时间求解器会遇到任何非平凡难题的无限循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39500162/