2012-02-22 14 views
2

私は、旅を計画するためにコーチのタイムテーブルを読むシステムを実装しようとしています。Dijkstraのアルゴリズムによるタイムテーブルの実装


出発日、出発駅と最終駅を入力するだけですが、AからBに行くには3〜4回の接続が必要となり、いくつかのオプションを返すことができ、必要な合計時間で順序付けられます。データベースの設定には、駅のテーブル、旅のテーブル、旅行のためのテーブル(旅行の包括的な日付が含まれています)があります。

私はDijkstraのアルゴリズムの優れた実装を得ていますが、接続するバスステーションで待つ時間を含める方法と、多くの旅に行くことができないため制限されています別の時代にある駅から別の駅に混乱に加わることになります。旅に1日か2日かかる場合も考慮する必要がありますが、これは面倒なことが判明しています。ダイクストラの価値はここで頑張っているのですか、誰かがもっと適した何かを知っていますか?

私はasp.net MVC3、C#、EF4を使用していますが、これはあまりコードではありません。私はここを最後にしています。私が前にやったことはまったくありません。 (私はこのプロジェクトのためにボランティアしたときに噛むことができた以上に噛んでいたかもしれません)誰かがこの状況に役立ついくつかのアドバイス、あるいはいくつかのドキュメントへのリンクを提供できれば、それは非常に助けになります。おかげで

+0

[OK]をクリックしてもう一度表示されるようになりました。 –

答えて

2

最初に:野心的なプロジェクトでボランティアのためのあなたに良い。第二に、これは難しいかもしれませんが、以下にリンクされた別のStackOverflow投稿から判断してください。NP-Complete

ダイクストラのアルゴリズムは、静的グラフ上で単一ソースの最短経路を見つけますが、これはあなたがこの問題でやっていることではありません。そのようなグラフの頂点は、おそらく一時的スペースを重複に存在するので、からから最速のバス12:00 pmに残すことができるが、からから最速のバス同じ日に午前11時59分に出発することができます。それは非スターターです。

明らかに、あなたはこれについて考えましたが、問題を見るための抽象的な方法は、グラフ内で最短の経路を見つけようとしていないことです。実質的に3次元空間(第3次元としての時間)である。ブルートフォースアプローチ(小さいグラフではそれにもかかわらず)は、時間的にノードをトポロジー的に順序付けると仮定すると、幅広い最初の探索として実装できます。

関連リンクはこちらです:トピックを読んBus public transport algorithm

一部:

フォースがあなたと一緒に可能性があります。

+0

こんにちはBrandon - ありがとう。現在、上記で追加したSOのリンクにあるMulti Modal Route Planningに関する記事を読んでいます。後で報告する... –

関連する問題