Java的二叉堆不工作的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()返回双...

然而

当我打印的堆与所有的getF()的I看到这一点：

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 *有时都需要更改插入到Heap中的元素的优先级。规避此功能缺失的唯一方法是删除元素（Java的PriorityQueue实现速度较慢），然后重新插入它。

但是有一个问题：从PQ/Heap中删除对象时，它仍然必须包含“旧”优先级（getF()必须仍然返回旧值），否则该元素可能不会被发现。如果元素已经包含新值，则PQ/Heap会在要删除的新位置查找它，而不是在与旧值匹配的位置。因此，序列必须是：（1）从PQ中删除元素，（2）调整其权重/优先级，（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); 

如果你仔细看看它，你修改的neighbor重量为行标*2由于在线路*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，或者更改为另一个提供了方法的堆实现。 （或者甚至更好：一个decreaseKey方法，所以不需要删除重新插入元素）。

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

tl; dr：不要修改已插入到PriorityQueue或堆中的元素的权重/优先级。