Java BinaryHeap 不在 A* 上工作（未排序）

Question

我正在为 A* 算法使用堆的实现：

https://courses.cs.washington.edu/courses/cse373/11wi/homework/5/BinaryHeap.java

我稍微修改了它，只是添加了contains方法并将remove重命名为poll，因为我以前使用过PriorityQueue但是没有用。

这是我对 Comparable<Spot> 接口的实现：

@Override
public int compareTo(Spot o) {
    Double.compare(getF(), o.getF());
}

getF()returns双...

然而，当我用所有 getF() 打印堆时，我看到了这个：

1. 176.0
2. 175.0
3. 180.0
4. 176.0
5. 223.0
6. 182.0
7. 146.0
8. 177.0
9. 87.0
10. 202.0
...

现在175是错误的，因为它低于176，87也是错误的...

我和 PriorityQueue 发生了同样的事情，我做错了什么？

编辑这是我的 A* 实现：

public List<Spot> process(GameBodyObject me, Point target, ArrayList<GameBodyObject> others) throws Exception {

    if(grid == null) {
        throw new Exception("You have to initialize AStar first.");
    }

    grid.unsetObstacleForObject(me);

    Spot start = grid.getSpotAtPosition(me.getPosition().getX(), me.getPosition().getY());
    Spot end = grid.getSpotAtPosition(target.getX(), target.getY());

    end = grid.moveSpotSoThatItDoesntCollide(end, me.getRadius());

    Heap<Spot> openSet = new Heap<Spot>(grid.getMaxSize());
    List<Spot> closedSet = new ArrayList<>();
    List<Spot> path = new ArrayList<>();

    openSet.add(start);

    while(openSet.size() > 0) {

        /*int winner = 0;
        for(int i = 1; i < openSet.size(); i++) {
            if(openSet.get(i).getF() < openSet.get(winner).getF()) {
                winner = i;
            }
        }*/

        Spot current = openSet.poll(); //openSet.get(winner);

        int i = 1;
        for(Spot s : Arrays.asList(openSet.getArray())) {
            if(s != null) {
                System.out.println(i + ". " + s.getF());
                i++;
            }
        }

        if(current.equals(end)) {
            // We are done, reconstruct the path...
            Spot temp = current;
            path.add(temp);
            while(temp.getPrevious() != null) {
                path.add(temp.getPrevious());
                temp = temp.getPrevious();
            }

            grid.resetObstacles();
            return path;
        }

        closedSet.add(current);

        List<Spot> neighbors = current.getNeighbors();

        for(Spot neighbor : neighbors) {
            if(!closedSet.contains(neighbor) && !grid.isCollidingWithObstacle(neighbor, me.getRadius())) {
                double tempG = current.getG() + 1;
                if(openSet.contains(neighbor)) {
                    if(tempG < neighbor.getG()) {
                        neighbor.setG(tempG);
                    }
                } else {
                    neighbor.setG(tempG);
                    openSet.add(neighbor);
                }

                neighbor.setH(heuristic(neighbor, end));
                neighbor.setF(neighbor.getG() + neighbor.getH());
                neighbor.setPrevious(current);
            }
        }

    }

    grid.resetObstacles();
    return new ArrayList<>();
}

Answer 1

使用 Java 的 PriorityQueue 或类似的堆实现来实现 Dijkstra 或 A* 算法时的一个常见问题是缺少 decreaseKey 方法。 Dijkstra 或 A* 有时都需要更改插入堆中的元素的优先级。避免缺少此功能的唯一方法是删除元素（这在 Java 的 PriorityQueue 实现中很慢）然后重新插入它。

但这有一个问题：当从 PQ/Heap 中删除对象时，它必须仍然包含 "old" 优先级（getF() 必须仍然 return在您的情况下为旧值），否则可能找不到该元素。如果元素已经包含新值，PQ/Heap 将在要删除的新位置查找它，而不是在匹配旧值的位置。

因此，序列必须是：(1) 从 PQ 中删除元素，(2) 调整其 weight/priority，(3) 将其重新插入 PQ。

在您的代码中，您有以下部分：

            if(openSet.contains(neighbor)) {
                if(tempG < neighbor.getG()) {
                    neighbor.setG(tempG); // *1
                }
            } else {
                neighbor.setG(tempG);
                openSet.add(neighbor);
            }

            neighbor.setH(heuristic(neighbor, end));
            neighbor.setF(neighbor.getG() + neighbor.getH()); // *2
            neighbor.setPrevious(current);

如果你仔细观察，你会在标记为 *2 的行修改 neighbor 的权重，因为第 *1 行的更改。要修复它，您可以尝试以下操作：

            if(openSet.contains(neighbor)) {
                if(tempG < neighbor.getG()) {
                    openset.remove(neighbor); // *3
                    neighbor.setG(tempG);
                }
            } else {
                neighbor.setG(tempG);
                // openSet.add(neighbor); // *4
            }

            neighbor.setH(heuristic(neighbor, end));
            neighbor.setF(neighbor.getG() + neighbor.getH());
            openSet.add(neighbor); // *5
            neighbor.setPrevious(current);

如果元素已经存在，则从堆中移除该元素 (*3) 并仅在正确计算权重后插入它 (*4, *5)。

现在的问题： 您的堆实现不提供这样的 remove(Object) 方法。 Java 的 PriorityQueue does。因此，您必须更改为 Java 的 PriorityQueue，或更改为提供 remove(Object) 方法的另一个堆实现。（或者甚至更好：一种 decreaseKey 方法，因此根本不必删除并重新插入元素）。

在许多 Dijkstra/A*-我看到的使用 Java 的 PQ 的实现中，第一次尝试就做错了，导致堆的顺序不正确。

tl;dr: 不要修改已插入到 PriorityQueue 或堆中的元素的 weight/priority。

Java BinaryHeap 不在 A* 上工作（未排序）

Java BinaryHeap not working on A* (not sorted)

java

heap