我们正在开展一个项目，该项目涉及在大地图上运行最短路径算法。
我们现在使用 AStar 和 Air Distance heurstic。
我们的项目涉及接收数据库中链接的更新。目前我们重新开始搜索每个链接更新或在每个预定义的时间间隔。有没有办法更新 AStar 算法来更新搜索，而无需在收到的每个更新时重新开始搜索？是否有适合此任务的更好算法？
披露：这是学生项目的一部分。
谢谢你。
问问题
346 次
1 回答
2
您可能正在寻找一种路由算法（本质上处理不断变化的图形）。
实现它的一种方法是使用距离矢量路由协议（它是贝尔曼福特算法的分布式版本），其工作原理如下1：
- 周期性地，每个顶点将其“距离向量”发送给它的邻居[该向量表示从发送顶点到另一个顶点的“成本”。
- 它的邻居尝试更新他们的路由表[最好通过哪个边缘移动到每个目标]
- 对于您的情况，每个节点都知道到达其邻居的最快方法是什么（如果图未加权，则为 1），并且它（顶点）将此数字添加到距离向量中的每个主干，以便知道如何以及如何到达目的地需要很多时间。每次修改到达时，相关节点将调用协议的新迭代，直到它重新收敛。
但是请注意，该算法是不知情的（但可以很好地处理不断变化的图形，但有一定的限制，仍然存在计数到无穷大的问题）
(1) 算法的解释基于我在此线程中提供的解释，并进行了一些修改。（毕竟这是相同的建议算法）。
于 2012-12-20T17:22:13.190 回答