5

我在我的应用程序中使用了稍微修改过的 Dijkstra 算法，但它很慢，我知道必须有更好的方法。我的输入数据是巴士站，彼此之间有指定的行程时间（约 400 个节点和约 800 条路径，最大结果深度 = 4（最多 4 次巴士改变或什么都没有）。

输入数据（公交路线）：

bus_id | location-from | location-to | travel-time | calendar_switch_for_today
XX | A | B | 12 | 1
XX | B | C | 25 | 1
YY | C | D | 5  | 1
ZZ | A | D | 15 | 0

dijkstraResolve(A,D, '2012-10-10') -> (XX,A,B,12),(XX,B,C,25),(YY,C,D,5) 
=> one bus change, 3 bus stops to final destination
* A->D cant be used as calendar switch is OFF

正如您可以想象的那样，在更复杂的图表中，例如主要城市（节点）确实与不同城市有 170 个连接，Dijkstra 速度较慢（~ 超过 5 秒），因为首先一个一个地计算所有邻居，因为它不是“试图”通过其他方式到达目标目的地...

你能推荐我其他适合的算法吗？

我在看：

最好有（只是可选的东西）： - 选择最少数量的公共汽车更改或最少的时间 - 选择寻找替代方式的选项（如果旅行时间相似）

谢谢你的提示

4

3 回答 3

6

也许是 A* 算法？见：http ://en.wikipedia.org/wiki/A-star_algorithm

也许收缩层次结构？请参阅：http ://en.wikipedia.org/wiki/Contraction_hierarchies 。

收缩层次结构由非常好的、非常快速的开源路由机 (OSRM) 实现：

http://project-osrm.org/

通过 OpenTripPlanner：

http://opentripplanner.com/

A* 由多个路由系统实现。只需使用 Google 进行搜索。

OpenTripPlanner 是一个多模式路由系统，据我所知，应该与您的项目非常相似。

于 2012-09-30T21:50:50.920 回答
5

听起来您正在寻找A*。它是 Djikstra 的变体，它使用启发式算法来加速搜索。在某些合理的假设下，A* 是最快的最优算法。只要确保始终与端点断开联系。

还有一些 A* 的变体可以在更短的时间内提供接近最优的路径。例如，请参见此处和此处。

Bellman-Ford （如您的问题中所建议的那样）往往比 Djikstra 或 A* 慢 - 它主要用于存在负边权重时，而这里没有。

于 2012-09-30T21:51:21.507 回答
0

A* 算法很适合这个；它通过使用启发式方法获得更好的性能。

这是一个简单的教程，可以帮助您入门：http ://www.policyalmanac.org/games/aStarTutorial.htm

于 2012-09-30T21:50:46.543 回答