在更新图上运行AStar

Question

我们正在研究一个涉及在大地图上运行最短路径算法的项目。

我们现在正在使用ASTA与Air Distance heaurstic。

我们的项目涉及接收数据库中链接的更新。 目前我们重新开始搜索每个链接更新或每隔预定义的时间间隔。 有没有办法更新AStar算法更新搜索，而不必重新接收每次更新的搜索？是否有更适合此任务的算法？

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

谢谢。

Answer 1

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

一个来实现它的方法是用Distance Vector Routing Protocol（这是Bellman Ford algorithm一个分布式的版本）和工作原理如下：

• 周期性，每个顶点发送它的“距离向量”到其 邻居[向量表示从发送顶点到每个其他顶点的“费用”。
• 它的邻居尝试更新他们的路由表[通过哪个边缘是最好移动到每个目标]
• 您的情况，每个节点知道什么是最快的方式到达它的邻居（1如果图是未加权的），并且它（顶点）将该数字添加到距离向量中的每个主体，以便知道如何以及需要多少时间才能到达目的地。每次修改到达时，相关节点都会调用协议的新迭代，直到它重新收敛。

不过请注意，这个算法是不知情的（但交易以及不断变化的图形，具有一定的局限性，仍有count to infinity problem）

---

（1）算法的解释是基于我在this thread提供了一些解释，并进行了一些修改。 （毕竟它是相同的建议算法）。