优先级队列--背后更新密钥的效果

Question

我试图理解为什么我的A*搜索的实现似乎工作良好，尽管我似乎是在优先级队列后面更新键。

在表示映射的类中，我有以下数据结构来保存映射中的所有节点（例如从文件加载）。

// maps a latitude/longitude to a node in the map
HashMap<GeographicPoint, MapNode> nodes;

为了实现*搜索，我的MapNode类包含“从开始到开始的距离”和“从目标到启发式距离”属性。在搜索开始之前，我将映射中每个节点的距离初始化为无穷大。这一切都很好。

PriorityQueue<MapNode> toExplore = new PriorityQueue<MapNode>();

toExplore.add(startNode);

稍后，作为*实现的一部分，当我在node对象中重新计算和更新距离时，我将再次使用指向相同原始节点的引用来执行此操作。嗯，PQ也引用了相同的原始节点，所以效果是我只是改变了距离（即键）下的PQ！

这对PQ不可能有好处。但一切都还管用！--意思是我得到了正确的最短路径，并探索了正确的节点数等。

提供PQ正在使用的MapNode实现中的相关部分可能很有用：

public class MapNode implements Comparable<MapNode> {

// the location of the intersection in the world
private GeographicPoint location;


// NOTE: Equals method is based on comparing actual geographic point. 
// Whereas compareTo based on distances. 
// This implies a.equals(b) and a.compareTo(b) == 0 will return different result. 
// Is this OK? 

@Override
public boolean equals(Object obj) { 
    return this.location.equals(obj);
} 

// NOTE: Equals method is based on comparing actual geographic point. 
// Whereas compareTo based on distances. 
// This implies a.equals(b) and a.compareTo(b) == 0 will return different result. 
// Is this OK? 

@Override
public int compareTo(MapNode other) {
    // Comparison based on priorities
    return Double.compare(this.getTotalEstimatedDistance(), 
                          other.getTotalEstimatedDistance());
}

null

Answer 1

我不明白当我出队时，优先级队列如何能够给我正确的最高优先级节点。我在背后弄它的钥匙。

虽然这是一个坏主意，但没有保证人，这将成为一个问题。PriorityQueue不是为所有条目排序的（只有第一个条目），所以更改另一个条目不一定是问题。在删除第一个之前，请尝试更改它。；）

我怎样才能设计得更好，这样我就不会有这种代码气味了？

Queue<MapNode> q = new PriorityQueue<>(
                               Comparator.comparing(MapNode::getTotalEstimatedDistance));