7

適切なデータ (都市、列車のルート、駅のリスト) が与えられ、ユーザーが選択した任意の 2 つの都市間の接続のリストを返すことができるアプリケーションを作成するには、どのアルゴリズムを使用しますか? アプリケーションは、受け入れられた列車変更の制限に該当する接続のみを選択する必要があります。

例:パリからモスクワまで最大で移動する必要がある場合、どの列車に乗ればよいかをアプリケーションに尋ねます。1 駅/乗り換え - アプリケーションは次のルートを返します: 列車 1 (パリ - ベルリン) -> 列車 2 (ベルリン -> モスクワ) (直接接続はありません)。

グラフィカルな例 地図

http://i.imgur.com/KEJ3I.png

町 Aから町 Gへの可能な接続についてシステムに問い合わせると、次のような応答が返されます。

  • 茶線 (0 スイッチ = 直接)
  • ブラウンラインからB町へ、オレンジラインからG町へ（乗り換え1回）
  • 茶色のラインから町 B へ / オレンジのラインから町 D へ / 赤いラインから町 G へ (2 つのスイッチ)
  • ...他のすべての可能性

そして、2 番目と 3 番目のオプションは 1 番目よりも短いですが、優先すべきは 1 番目です (列車の切り替えが含まれていないため)。

4

2 に答える 2

10

重要なのは「ストップ/スイッチの数」だけであると仮定すると、実際の問題は、重み付けされていない 有向グラフで最短経路を見つけることです。

グラフ モデルはG = (V,E)どこでV = {all possible stations}、E = { (u,v) | there is a train/route from station u to station v }
注: a_0 で始まる列車があり、a_1、a_2、...a_n を通るパスがあるとしましょう: E には以下が含まれます:(a_0,a_1),(a_0,a_2),..,(a_0,a_n)また、(a_1,a_2),(a_1,a_3),...形式的には: for each i < j: (a_i,a_j) ∈ E .

BFSはこの問題を解決し、完全[解決策があれば常に解決策を見つける] かつ最適[最短経路を見つける] の両方です。

エッジ [ルート] が重み付けされている場合は、代わりにダイクストラのアルゴリズムのようなものが必要になります。

すべての可能なルートのリストが必要な場合は、訪問済みセットを維持せずに反復深化 DFSを使用し、見つかったすべてのパスを関連する深さまでターゲットに出力できます。[クリークの反例で BFS がすべてのパスを返さない]

于 2012-04-04T16:15:22.903 に答える
0

すべてのペアの最短経路を計算する必要があると思います。http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithmを確認してください。

于 2012-04-04T16:19:04.870 に答える