形式の列車ネットワークの時刻表がいくつかあります-
開始場所 (時間) -> 停止 1 (時間 1) -> 停止 2 (時間 2) -> ... 終了場所
つまり、各ルート/時刻表は、時間の昇順で発生する一連の停留所で構成されています。ルートは 1 日に複数回繰り返されます。
最終的には、このデータに基づいて経路探索アルゴリズムを構築したいと考えています。最初は、これは単一の時刻表/ルートからパスを返します。しかし最終的には、複数のルートにわたる最適な移動を計算できるようにしたいと考えています。
したがって、私の質問は、ルートのクエリをできるだけ簡単にするために、このデータを保存する最良の方法は何ですか? クエリの形式は...
開始位置: x、終了位置: y、時刻: t
If you are doing path finding, a lot of path finding algorithms deal with following the shortest path segment to the next node, and querying paths from that node. So your queries will end up being, all segments from station x at or after time t, but the earliest for a given distinct destination.
If you have route from Washington, DC to Baltimore, your stop 1 and stop 2 might be New Carrolton and Aberdeen. So you might store:
id (auto-increment), from_station_id, to_station_id, departure_time, arrival_time
You might store a record for Washington to New Carrolton, a record for New Carrolton to Aberdeen, and a record from Aberdeen to Baltimore. However, I would only include these stops if (a) they are possible origins and destinations for your trip planning, or (b) there is some significant connecting route (not just getting of the train and taking the next one on the same route).
Your path finding algorithm is going to have a step (in a loop) of starting from the node with the lowest current cost (earliest arrival) list of the next segments, and the node that segment brings you to.
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)