我试图理解为什么我的 A* 搜索实现似乎工作正常,即使我似乎正在更新优先级队列后面的键。
在代表 map 的类中,我有以下数据结构来保存 map 中的所有节点(例如从文件加载)。
// maps a latitude/longitude to a node in the map
HashMap<GeographicPoint, MapNode> nodes;
为了实现 A* 搜索,我的 MapNode 类包含“距起点的距离”和“距目标的启发式距离”属性。在搜索开始之前,我将 map 中每个节点的距离初始化为无穷大。这一切都很好。
当调用 aStarSearch 函数时,我创建一个 Prority Queue (PQ),如下所示:
PriorityQueue<MapNode> toExplore = new PriorityQueue<MapNode>();
现在,当我将节点排列到此 PQ 中时,如下所示:
toExplore.add(startNode);
请注意,我没有创建节点的新副本。我只是创建一个对原始节点的附加引用并将其添加到 PQ 中。
稍后,作为 A* 实现的一部分,当我重新计算和更新节点对象中的距离时,我将使用指向同一原始节点的引用再次执行此操作。好吧,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());
}
问题:
- 我不明白当我出队时,优先级队列如何能够为我提供正确的最高优先级节点。我在背后弄乱了它的 key 。
- 我怎样才能更好地设计它,这样我就没有这种代码味道?
如果需要,我可以提供其他代码片段,以便更好地理解。
最佳答案
I don't understand how the Priority Queue would be able to give me the correct highest priority node when I dequeue. I am messing with it's keys behind it's back.
虽然这是一个坏主意,但不能保证它会出现问题。 PriorityQueue 并未对所有条目(仅第一个)进行排序,因此更改另一个条目不一定是问题。在删除它之前尝试更改第一个。 ;)
How can I design this better such that I do not have this code smell?
每当您更改有序集合中的元素(以可能改变其位置的方式)时,您都必须删除它,更改它并将其添加回以确保集合不会损坏。
Queue<MapNode> q = new PriorityQueue<>(
Comparator.comparing(MapNode::getTotalEstimatedDistance));
关于java - 优先级队列 - 背后更新 key 的影响,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35255375/