查找汽车的路线非常容易:您可以存储所有道路的加权图,并可以使用Djikstra's algorithm [1]。公交路线不太明显。对于公交车,您必须代表“等待下一辆公交车10分钟”或“步行一个街区到另一个公交车站”之类的东西,然后将其输入到寻路算法中。
对于汽车来说,它甚至并不总是那么简单。在某些城市中,有些道路在早上仅进入城市,而在晚上则仅离开城市。一些高级GPS知道如何在高峰时段避免繁忙的路线。
您将如何有效地表示这种与时间相关的图并找到路线?不需要可证明的最佳解决方案;如果旅行者想准时到达,他们会买车。 ;-)
[1]在示例中要提到的一个很棒的算法,因为大家都听说过它,尽管A *对于该应用程序来说是一个更可能的选择。
最佳答案
我参与了瑞典斯德哥尔摩公共(public)交通的一个行程计划系统的开发。它基于Djikstra的算法,但是在访问系统中的每个节点之前都已终止。今天,当每个站点都有可靠的坐标可用时,我猜想A *算法将是明智的选择。
定期从几个数据库中提取有关即将到来的流量的数据,并将其编译成大表,再装入搜索服务器集群的内存中。
成功算法的一个关键是使用基于出行和等待时间乘以不同权重的路径成本函数。这些加权时间在瑞典语中称为“kresu”时间,反射(reflect)了这样一个事实,例如,一分钟的等待时间在“不便”方面通常等同于两分钟的旅行时间。
KRESU重量表
在旅途中。停在屋顶下
与商店等可以稍微
重量较轻且拥挤的车站
调高算法。
数据结构
区域
您可以在旅途中开始或结束的命名区域。公交车站可能是有两个车站的区域。一个有多个平台的大型车站可以是一个区域,每个平台一站式。
数据:名称,停靠区域
停止
包含所有公交车站,火车站和地铁站的阵列。请注意,您通常需要两个站点,每个方向一个站点,因为过马路或步行到另一个平台需要一些时间。
数据:名称,链接,节点
链接
您可以从该站点步行到达其他站点的列表。
数据:其他站点,步行至其他站点的时间
线路/游览
您在公共(public)汽车上有一个号码,还有一个目的地。公交车从一站开始,并在到达目的地的途中经过数个站。
数据:编号,名称,目的地
节点
通常,您的时间表最短的时间应该在巡回赛的第一站和最后一站。公交车/火车每次经过停靠点时,都会向阵列添加一个新节点。该表每天可以有数百万个值。
数据:线路/游览,停留,到达时间,出发时间,误差幅度,游览中的下一个节点
搜索
数组的大小与用于存储到达位置和路径成本的Nodes数组大小相同。
数据:与上一个节点的反向链接(如果未访问该节点则不设置),路径成本(对于未访问的无限)