java - 广度优先搜索(高峰时间) - 链表队列包含同一板的重复项

Question

您好 stackoverflow 用户， 我正在尝试对经典的高峰时段游戏实现广度优先搜索。但是，我在队列方面遇到了问题。在向队列添加内容之前，我打印出了每个板的外观:

[-, 0, 0, -, -, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

0 1 0
[-, -, 0, 0, -, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

0 2 0
[-, -, -, 0, 0, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

但是，当我打印出队列时，结果是这样的:

[-, -, 0, 0, -, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

[-, -, -, 0, 0, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

[-, -, -, 0, 0, 1]
[2, -, -, 4, -, 1]
[2, 3, 3, 4, -, 1]
[2, -, -, 4, -, -]
[5, -, -, -, 6, 6]
[5, -, 7, 7, 7, -]

我打印出这些板的代码段:

for (int i = car.getY() + 1; i < (5 - car.getLen()) + 1; i++) {
    if (isSafeHorizontal(b, car, i)) {
        Board copy = new Board(b.boardVehicles, b.moves, nextCar);
        copy.moveVehicle(car.getX(), i, b.currentCar);
        for (int a = 0;  a< queue.size(); a++) {
            System.out.println(queue.get(a));
        }

        //System.out.println(copy);System.out.println("" + car.getX() + " " + i + " " + b.currentCar);
        queue.add(copy);
    }
}

我认为引用可能有问题，但我无法找出它不工作的任何原因。

编辑: 这是我的完整代码供引用: BreadthFirstSearch.java , Board.java AND Vehicle.java

Answer 1

你的问题看起来有两个方面:

1. 第二次打印列表时，您缺少第一个节点(或板)。
2. 您将第三项打印两次。

解决方案之一:可以在pastebin中的BreadthFirstSearch类的第94行看到:

System.out.println(firstNode);
            LinkedList<Board> queue = new LinkedList<Board>();
            queue.addFirst(firstNode);
            Board solved = null;
            while (queue.size() != 0) {
                    Board b = queue.get(0);

                    System.out.println("!===========\ns: " + queue.size() + "\n");
                    //for (int i = 0; i < queue.size(); i++){System.out.println(queue.get(i));}
                    queue.remove(0);

您正在检索第一个项目，然后将其删除。所以你错过了第一项。我认为您没有任何理由删除该节点。

问题 2 的解决方案:

看起来您在第 110 - 133 行之间的 if 语句中两次添加了具有相同信息的节点:

 if (car.getDir().equals("V")) {
     // go through every position before the current car's X
     for (int i = 0; ((i < car.getX()) && (i < (5 - car.getLen()) + 1)); i++) {
         // no car in current position? create new vehicle
         // instance
         if (isSafeVertical(b, car, i)) {
             Board copy = new Board(b.boardVehicles, b.moves, nextCar);
             copy.moveVehicle(i, car.getY(), b.currentCar);
             queue.add(copy);
         }
     }
     // go through every position after current car's x
     for (int i = car.getX() + 1; i < (5 - car.getLen()) + 1; i++) {
         // no car in current pos? create new vehicle instance.
             if (isSafeVertical(b, car, i)) {
                 Board copy = new Board(b.boardVehicles, b.moves, nextCar);
                 copy.moveVehicle(i, car.getY(), b.currentCar);
                 queue.add(copy);
             }
     }
     // move horizontal cars and add to queue

看看如何在其中添加节点，并查看如何在打印出节点的 for 语句中将节点添加到队列中。