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

我想了解为什么我的A *搜索实现似乎工作正常，即使我似乎更新优先队列背后的密钥。优先级队列 - 更新密钥背后的效果

在我的代表地图的类中，我有以下数据结构来保存地图中的所有节点（比如从文件加载）。

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

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

当aStarSearch功能调用时，创建一个Prority队列（PQ）如下：

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

现在，当我排队节点到该PQ如下：

toExplore.add(startNode);

通告，我我没有创建节点的新副本。我只是创建一个额外的参考到原始节点，并将其添加到PQ。后来，作为A *实现的一部分，当我重新计算和更新节点对象中的距离时，我再次使用指向同一个原始节点的引用再次执行此操作。那么，PQ也是参考同一个原始节点，所以效果是我只是改变了PQ下的距离（即键）！

这对PQ来说不好。但一切仍然有效！ - 这意味着我得到了正确的最短路径，并已探索节点等的正确数量

这可能是有用的，以提供从MapNode执行相关部件的PQ正在与：

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()); 
}

问题：

我不明白如何优先队列将能够给我正确的最高优先级节点，当我出列。我正在搞乱它背后的关键。
我怎样才能更好地设计这样的，我没有这种代码味道？

如果需要，我可以提供额外的代码片段，以便更好地理解。

来源

2016-02-07 AGandhi

此处的行为是未定义的，可能看起来像是起作用，但会表现出不可预测性。更新优先级队列中的密钥很可能注定要失败。一个典型的Java实现将只用新密钥重新插入密钥而不删除旧条目。 –

我不明白当我出队时，Priority Queue如何能够给我正确的最高优先级节点。我正在搞乱它背后的关键。

虽然这是一个坏主意，但没有保证它会显示为一个问题。 PriorityQueue没有为所有条目排序（只有第一个条目），因此更改其他条目不一定是个问题。在删除它之前，请尝试更改第一个。 ;）

我该如何设计这个更好的，使我没有这种代码味道？

无论何时在有序集合中更改元素（以可能更改其位置的方式），必须将其删除，然后将其更改并重新添加以确保集合未损坏。

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

来源

2016-02-07 15:34:29

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

回答

相关问题