在更新图上运行AStar

Question

我们正在进行一个项目，该项目涉及在大地图上运行最短路径算法。在

我们现在使用的是空距heaurstic。在

我们的项目包括接收数据库中链接的更新。 目前，我们重新开始搜索每个链接更新或在每个预定义的间隔。 有没有一种方法可以更新AStar算法来更新搜索而不必在每次收到更新时重新启动搜索？有没有更好的算法适合这个任务？在

披露：这是学生项目的一部分。在

谢谢。在

Answer 1

您可能正在寻找一种路由算法（它本质上处理不断变化的图形）。在

实现它的一种方法是使用Distance Vector Routing Protocol（它是Bellman Ford algorithm的分布式版本），其工作方式如下所示：

• 每个顶点周期性地将其“距离向量”发送到 邻域[向量表示从发送顶点到另一个顶点的“成本”。在
• 它的邻居试图更新它们的路由表[通过哪个边移动到每个目标]
• 对于您的例子，每个节点都知道到达其邻居的最快方法是什么（如果图未加权，则为1），并且它（顶点）将该数字添加到距离向量中的每个中心，以便知道如何以及需要多长时间到达目的地。每次修改到达时，相关节点将调用协议的新迭代，直到它重新收敛。在

但是请注意，这个算法是未知的（但是处理变化的图很好，有一定的限制，仍然存在count to infinity problem）

---

（1）算法的解释是基于我在this thread中提供的一个解释，并作了一些修改。（这毕竟是建议的算法）。在