用A*算法找到几条最短路径 [英] Find several shortest paths with A* algorithm
问题描述
我正在制作一个使用 A* 算法查找路线的路由应用程序.我想提供的不仅仅是一条路线，还有几条替代路线.例如，路线比最佳路线长一点.
I am making a routing application that uses A* algorithm for finding route. I want to offer not just one route, but also a few alternative routes. For example routes that are just a little bit longer than the optimal one.
由于 A*(以及许多其他路线)只找到一条路线，我该如何搜索这些替代路线?我应该使用其他算法吗?
Since A* (and many others) find only one route, how can I search for these alternative ones? Should I use some other algorithm?
推荐答案
您可能想要研究 K条最短路径问题，即求两个节点之间的k条最短路径的问题.维基百科页面上描述的算法是Dijkstra 算法的概括.
You may want to look into research on the K shortest paths problem, which is the problem of finding the k shortest paths between two nodes. The algorithm described on the Wikipedia page is a generalisation of Dijkstra's algorithm.
为了找到最短路径，可以使用最短路径算法，例如作为 Dijkstra 算法或 Bellman Ford 算法，并将它们扩展到找到不止一条路径.K最短路径路由算法是最短路径问题的泛化.该算法不仅找到最短路径，但也有 K 条其他路径(按递增顺序)成本.K 是要找到的最短路径的数量.问题可以是限制为具有 K 条最短路径且无环(无环 K最短路径)或循环.
To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path. The K Shortest path routing algorithm is a generalization of the shortest path problem. The algorithm not only finds the shortest path, but also K other paths in order of increasing cost. K is the number of shortest paths to find. The problem can be restricted to have the K shortest path without loops (loopless K shortest path) or with loop.
一些关键论文和概念:
- 找到 k 条最短路径，大卫爱普斯坦，1997
- 问题描述
- Yen 算法:该算法假定 Dijkstra 算法用于找到两个节点之间的最短路径，但可以使用任何最短路径算法来代替它."大概可以使用A*.可以在此处找到各种实现的 Google 代码页.
- 关于该主题的详细Bibtex 参考书目，由 Eppstein 编译.
- Finding the k shortest paths, David Eppstein, 1997
- A description of the problem
- Yen's algorithm: "The algorithm assumes that the Dijkstra algorithm is used to find the shortest path between two nodes, but any shortest path algorithm can be used in its place." Presumably A* can be used. A Google code page of various implementations can be found here.
- A detailed Bibtex bibliography on the topic, compiled by Eppstein.
这篇关于用A*算法找到几条最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
