シンプルなバスルート検索エンジンを作るにはどうすればいいですか？

Question

[未：EユーザーがDevelopment of railway enquiry system, how to model Trains, Stations and Stops?で再びこれを求めている] 私の問題の説明：

私はそれがA、B、C、D、通過しますROUTE-1にBUS-123を持っていると仮定E、F、G、HおよびROUTE-2内のBUS-321〜D、E、F、X、Y、Z。 誰かがBをソースポイントとして入力し、Fを宛先ポイントとして入力すると、BUS-123のROUTE-1が結果に表示されます。しかし、誰かが出典としてHを入力し、目的地の結果としてAが表示されるべきではない。なぜなら、戻ってくる旅行は常に旅行と同じではないからである。人がROUTE-1とBUS-321を有すると、次いでBUS-123先としてソース及びZとして入力した場合 しかしROUTE-2が表示されなければなりません。

私の問題は どのようにデータベースにそのルート情報を保存しますか？私がRDBMSに次のように格納する場合

BUS_NUMBER ROUTE_NUMBER VIA_ROUTES 
BUS-123  ROUTE-1   A, B, C, D, E, F, G, H 
BUS-321  ROUTE-2   D, E, F, X, Y, Z 

次に検索がどのように機能するのですか。文字列で検索する方法を意味します。 そして、私はすべてのVIA_ROUTESを別々の異なる列に格納すれば、それはどうなるでしょうか？あなた自身のテクニックで私を提案してください。緊急ではありませんが、私は基本的なバスルート検索を行う予定ですので、あなたのご意見は高く評価されます。

Answer 1

私はそれを循環グラフとしてモデル化したいと思います。各バス停は頂点で表されます。 2つの停留所間の各直接接続は、ルート番号でラベル付けされたエッジで表されます。その結果、各ルートは接続されたエッジのシーケンスです。エッジも方向付けします。停止Aから停止Bへ移動するすべてのルートが必ずしも停止Bから他の方向の停止Aへ移動するわけではありません。

日曜日の午前2時には、変動が小さいかもしれないが、金曜日の夕方の午後5時には、その脚の分散の尺度（または測定値）それは非常に高いかもしれないし、出発時間のリストも。

次にグラフトラバーサルのその問題とあなたは「最小コスト」を定義することを選択したが、「最小コスト」のルート、発見 - あなたが考慮したいと思うかもしれない要因含まれます：

• 総旅行時間
を
• 次の脚が離れるのを待つのに費やされた合計時間。
• 個々の停止時の待機時間。
• 距離？

あまりにも多くの待ち時間が悪いことに注意してください（10月1日にバスを待っている時間は40分かかります）。地方の交通状況の変動に非常に敏感であるため、バスがスケジュールに対してかなり大きな変動性を持つ傾向があることから、接続が欠落する確率が高くなるので、あまりにも悪いことです。

それは私がそれを行う方法です。

私はそれをSQLで直接解決しようとは思わないと思います。

モデルはSQLに適していますが、

• 停止するには、次のエンティティが必要です。次に、スケジュールなどを表す必要があるため、いくつかのエンティティが必要です。バス停。グラフの頂点。
• 経路。バス路線。
• セグメント。 2つの停留所の間の直接リンク。グラフの端。
• RouteSegment。ルートを構成するセグメントの順序付きシーケンスを表す連想エンティティ。

Answer 2

bus_numbersはあまり重要ではないと思います。多分あなたが必要とするのは、bus_stopsを大行列にして2次元行列を作成し、dijkstraのようなグラフを使ってAからBへの最短経路を見つけることです。バスパーツを見つけたら、簡単にbus_numbersとそれらをクライアントに示します。したがって、あなたのデータベースはすでにとても良いと思います。

Answer 3

私はrouteテーブルとroute_partテーブルを持っています。後者には、ルートへの参照と並べ替えのための序数、およびstopテーブルへの参照が含まれます。したがって、任意のルートを格納することができます。

2つの停留所の間のルートを検索する場合は、route_partテーブルの2つの停留所を検索して、いずれの場合も同じルートに表示されるかどうかを確認できます。ルートは一方向に存在し、他方は存在しない）。