0

私は実際にバスのチケット予約システムを開発しています。プロバイダーには、多くのルートとさまざまな旅行があります。これらすべてをまとめてマッピングするかなり包括的なデータベースをセットアップしましたが、クロスルート予約に関しては、パスアルゴリズムを機能させるのに問題があります。

たとえば、ユーザーがモントリオールからシャーブルックに行きたい場合、ここでルート #47 と呼ばれるもののみを使用します。しかし、彼がシャーブルックの代わりにサットンに行く場合、彼はある時点でルート 53 に乗り換えなければなりません。

現在、たった 1 つの転送を検出することはそれほど難しくありません。しかし、複数のルートを横断するために彼ができるオプションが何であるかを検出するようになると、ちょっと怖い. SQL のみを使用して 1 ～ 3 ホップでこれを行うためのかわいくて比較的効率的な方法を考案しましたが、クライアントが残りの 2 つのルートにとどまらない可能性があるため、これらすべてをより広いスペクトルでどのように整理する必要があるのか​​ 疑問に思っていますの命です。

これまでに考えたことの例：

StartingStop
joins to Route
joins to StopsOfTheRoute
joins to TransfersOnThatStop
joins to TargetStopOfThatTransfer
joins to RouteOfThatStop
joins to StopsOfThatNewRoute
[wash rince repeat for more hops]
where StopsOFThatNewRoute = EndingStop

問題は、ホップが 3 つ以上ある場合、データベースに正しくインデックスを付けたとしても、SQL サーバーがプレッシャーの下でかなり速く詰まると確信していることです。最終的には大きな障害を簡単に予測できます...

ありがとうございました

4

1 に答える 1

1

あなたの問題についての私の理解: 適切なパス (1 つ以上のルートのセグメントをカバーする) を識別するのに役立つアルゴリズムを探しています。

これは、ジェイソンが正しく指摘しているように、経路探索の問題です。この種の問題については、ウィキペディアの経路探索に関する記事を参照することから始めてから、 Djikstra のアルゴリズムの詳細を掘り下げる必要があります。それはおそらくあなたを始めるでしょう。

ただし、構造とパフォーマンスの両方の観点から、データ モデルが問題を引き起こす可能性があることにすぐに気付くでしょう。典型的な例は、時間の制約を管理する必要がある場合です。複数ある場合、移動時間が最も短い経路はどれですか? 1 つの経路は最短ですが、1 日 1 回の乗車のみを提供し、別の経路はより長くても 1 日に数回の乗車を提供する場合があります。

これを処理する可能な方法は、各ノードが特定の時間に特定のストップに対応するグラフを作成することです。エッジは、ルームタイムのこのストップから他の地理的ストップの両方に接続するだけでなく、次の時点でそれ自体にも接続します。

私の提案は、経路探索アルゴリズムを読むことから始めてから、データモデルを再検討して、制約があるかどうかを確認することです。次に、データを格納するための構造と、パスを検索するための構造に注目します。

提案 (効率的ではありませんが、十分な量の RAM があれば機能する可能性があります)。リレーショナル データベース サーバーを使用して、基本情報 (停留所、どのルートがどの停留所に接続されているかなど) を保存します。あなたはこれをすでにカバーしているようです。次に、与えられた制約を考慮して、グラフのメモリ内表現を構築します。このための独自のライブラリを非常に高速に構築できる可能性があります (PHP 用のそのようなライブラリは知りません)。

別の方法として、Neo4jなどのグラフ データベースとその REST インターフェイスを使用することもできます。これには、アプリケーションの大幅な再設計が必要になると思います。

これがあなたに役立つ指針を与えることを願っています。

于 2012-10-16T00:29:00.210 に答える