database - 存储路线数据

标签 database algorithm path-finding

我有许多火车网络的时间表,其形式为 -

Start Location (Time) -> Stop 1 (time1) -> Stop 2 (time2) -> ... End Location

即每条路线/时间表都由一系列按上升时间发生的停靠点组成。这些路线每天重复多次。

最终,我想在此数据之上构建一个寻路算法。最初这将从单个时间表/路线返回路径。但最终我希望能够计算出跨越一条以上路线的最佳旅程。

因此,我的问题是,存储此数据以使查询路线尽可能简单的最佳方式是什么?我想象查询的格式是...

Start Location: x, End Location: y, At Time: t

最佳答案

如果您正在进行寻路,许多寻路算法处理跟随最短路径段到下一个节点,并从该节点查询路径。因此,您的查询最终将是,在时间 t 或之后来自站点 x 的所有路段,但对于给定的不同目的地是最早的路段。

如果您有从华盛顿特区到巴尔的摩的路线,您的第 1 站和第 2 站可能是新卡罗尔顿和阿伯丁。所以你可以存储:

id (auto-increment), from_station_id, to_station_id, departure_time, arrival_time

您可以存储一条从华盛顿到新卡罗尔顿的记录,一条从新卡罗尔顿到阿伯丁的记录,以及一条从阿伯丁到巴尔的摩的记录。但是,如果 (a) 它们是您旅行计划的可能出发地和目的地,或者 (b) 有一些重要的连接路线(不仅仅是下火车和乘坐同一路线的下一类火车),我只会包括这些站点.

您的寻路算法将有一个步骤(在一个循环中)从当前成本最低的节点开始(最早到达)下一个路段列表,以及该路段将您带到的节点。

select segments.*
from segments inner joint segments compare_seg on segments.to_station_id = compare_seg.station_id
where departure_time > ?
group by segments.id
having segment.arrival_time = min(compare_seg.arrival_time)

关于database - 存储路线数据,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10667753/

相关文章:

mysql - “找不到兼容的服务器”错误消息

java - 为什么我用 Java 实现的快速排序不起作用?

c# - 尝试将密码存储到数据库

php - 是什么导致了这个 FatalErrorException?

javascript - 寻找一种迭代具有此约束的项目的算法

c# - AI 敌人在追逐玩家时会聚在一起

c - 曼哈顿距离高估了,让我发疯

algorithm - 什么算法计算 map 上从 A 点到 B 点的方向?

sql - 如何从包含自引用外键的表中删除所有数据

java - 较短版本的计算