在更新的图上运行AStar

Question

3

我们正在开展一个涉及在大地图上运行最短路径算法的项目。目前我们使用的是AStar算法，其中包括空气距离启发式。

我们的项目需要接收来自数据库链接的更新。目前，我们每次更新链接或在每个预定义的时间间隔内重新启动搜索。是否有一种方法可以更新AStar算法以在接收到每个更新时不重新启动搜索？是否有更适合此任务的更好算法？

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

谢谢。

- CaptainNemo

1

这里没有太多上下文可供参考。是否可以发布更多关于您的具体问题以及您想要改变的内容的详细信息？ - Hunter McMillen

该图是道路和交叉口的图表。道路上标注有长度。这个长度可以更改。 - CaptainNemo

你是否在使用A*算法来解决全源最短路径问题？ - Fred Foo

不是所有的配对，只需要1个配对。 - CaptainNemo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

您可能正在寻找一种路由算法（这种算法通常处理不断变化的图形）。

一种实现它的方法是使用距离向量路由协议（它是Bellman-Ford算法的分布式版本），其工作原理如下¹：

定期，每个顶点都会将其“距离向量”发送到其邻居[该向量指示从发送顶点到每个其他顶点的旅行成本]。
其邻居试图更新其路由表[通过哪个边缘最好地移动到每个目标]
对于您的情况，每个节点都知道到达其邻居的最快方式（如果图形未加权，则为1），并且它（顶点）将此数字添加到距离向量中的每个条目中，以便知道如何以及需要多长时间才能到达目的地。每当修改到达时，相关节点都将调用协议的新迭代，直到重新收敛。

请注意，这个算法是无信息的（但对于变化的图表处理得很好，有一定的限制，仍然存在无限计数问题）。

算法的解释基于我之前在这个帖子中提供的解释，有些修改（毕竟它是同样的建议算法）。