java - 在 GPS 上实现 A* 算法的开放和封闭列表

Question

我目前正在尝试创建一个 GPS 系统，它可以接收 map 数据并在最短距离内找到起点和终点之间的最短距离。

程序接收顶点(每个顶点都包含一个标签以及 x 和 y 坐标)和边(详细说明往返于哪条道路以及距离)，然后将它们存储在邻接列表中。

我决定使用 A* 算法并尝试遵循此 introduction但我不确定如何实现开放和封闭列表。一个简单的 vector 就足够了吗？还是我需要使用其他东西，比如优先级队列？

Answer 1

此处的开放列表用于获取下一个最佳或最短路径，因此您可以为此使用优先级队列。

closed list只是把你不想再用的方 block 丢弃，你可以用hash table来实现closed list，这样你就可以在O(1)中找到这个方 block 是否被丢弃。