Java BinaryHeap无法在A *上运行(未排序) [英] Java BinaryHeap not working on A* (not sorted)
问题描述
我正在使用Heap for A *算法的这种实现:
I am using this implementation of Heap for A* algorithm:
https://courses.cs.washington .edu/courses/cse373/11wi/homework/5/BinaryHeap.java
我做了一点修改，但是只添加了contains方法并将remove重命名为poll，因为我以前使用过PriorityQueue，但是它没有用.
I slightly modified it but only adding contains method and renaming remove to poll, because I previously used PriorityQueue but it didn't work.
这是我对Comparable<Spot>接口的实现:
@Override
public int compareTo(Spot o) {
Double.compare(getF(), o.getF());
}
getF()返回双...
但是，当我用所有getF()打印堆时，我看到的是:
however when I print the Heap with all the getF()s I see this:
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也错误...
Now the 175 is wrong because it's lower than 176, 87 is also wrong...
PriorityQueue在我身上发生了同样的事情，我在做什么错了?
The same exact thing happened to me with PriorityQueue, what am I doing wrong?
编辑 这是我的A *实现:
EDIT Here is my A* implementation:
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<>();
}
推荐答案
使用Java的PriorityQueue或类似的堆实现来实现Dijkstra或A *算法时，常见的问题是缺少decreaseKey方法. Dijkstra或A *有时都需要更改插入到堆中的元素的优先级.避免缺少此功能的唯一方法是删除元素(这在Java的PriorityQueue实现中很慢)，然后重新插入.
A common problem when using Java's PriorityQueue or similar heap implementations to implement Dijkstra or A* algorithms is the missing of a decreaseKey method. Both Dijkstra or A* sometimes need to change the priority of an element inserted into the Heap. The only way to circumvent the missing of this functionality is to remove the element (which is slow in Java's PriorityQueue implementation) and then re-insert it.
但是有一个问题:从PQ/Heap中删除对象时，它仍然必须包含旧"优先级(在您的情况下，getF()必须仍然返回旧值)，否则该元素可能找不到.如果元素已经包含新值，则PQ/Heap会在要删除的新位置而不是与旧值匹配的位置中查找它.
But there is one problem with this: When removing the object from the PQ/Heap, it must still contain the "old" priority (getF() must still return the old value in your case), as otherwise the element may not be found. If the element already contains the new value, the PQ/Heap would look for it in the new place to be removed, instead of in the place matching the old value.
因此，序列必须为:(1)从PQ中删除元素，(2)调整其权重/优先级，(3)将其重新插入PQ.
So, the sequence must be: (1) remove element from PQ, (2) adapt its weight/priority, (3) re-insert it into the PQ.
在您的代码中，包含以下部分:
In your code, you have the following part:
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);
如果仔细观察，由于行*1的更改，您将修改标记为*2的行的neighbor的权重.要解决此问题，您可以尝试以下操作:
If you look closely at it, you modify the weight of neighbor at line marked *2 due to the change at line *1. To fix it, you could try the following:
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)之后才插入.
This removes the element from the Heap if it's already there (*3) and inserts it only after the weight is correctly calculated (*4, *5).
现在的问题:您的堆实现不提供这样的remove(Object)方法. Java的 PriorityQueue可以.因此，您将不得不更改为Java的PriorityQueue或另一个提供remove(Object)方法的堆实现. (或更妙的是:一种decreaseKey方法，因此根本不必删除重新插入元素的方法.)
The problem now: Your Heap-implementation does not offer such a remove(Object) method. Java's PriorityQueue does. So you would have to change to Java's PriorityQueue, or to another Heap-Implementation that offers a remove(Object) method. (Or even better: a decreaseKey method, so one would not have to remove an re-insert the element at all).
在我看到的许多使用Java的PQ的Dijkstra/A * -Implementations中，第一次尝试都做错了，导致堆的顺序不正确.
In many Dijkstra/A*-Implementations I saw using Java's PQ, this was done wrong in the first attempt, leading to the incorrect order of the Heap.
tl; dr:请勿修改已插入PriorityQueue或Heap中的元素的权重/优先级.
tl;dr: Do not modify the weight/priority of an element already inserted into a PriorityQueue or Heap.
这篇关于Java BinaryHeap无法在A *上运行(未排序)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
