0

これはバンガロールのメトロマップです。

バンガロールメトロルート

現在、出発地と目的地の間の停留所の数をユーザーに知らせるアプリを設計しています。ここで、ユーザーが青い線の 1 つの停留所から別の停留所に青い線だけで移動する必要があるとします。この画像のように..

ブルーラインからブルーラインへの移動

ご覧のとおり、搭乗ポイントは 1、目的地は 2 で、その間に 6 つの停留所があります。間の停留所の数と距離を計算する方法。ラインが変更された場合、つまり、ユーザーは BlueLine から YellowLine に移動したいと考えています。

各行の文字列配列の形式で停車地の名前があります.ここに配列があります..

 String[] greenline = {"Bangalore International Exhibition Center", "Jindal", "Manjunathnagar", "Nagasandra", "Dasarahalli", "Jalahalli", "Peenya Industry", "Peenya", "Yeswanthpur Industry", "Yeswanthpur", "Sandal Soap Factory", "Mahalaxmi", "Rajajinagar", "Kuvempu Road", "Srirampura", "Sampige Road", "Kempegowda Interchange", "Chikpet", "K R Market", "National College", "Lalbagh", "South End Circle", "Jayanagar", "R V Road Interchange", "Banashankari", "J P Nagar", "Puttenahalli", "Anjanapura Cross Road", "Krishna Leela Park", "Vajrahalli", "Thaighattapura", "Anjanapura/NICE Junction"};

String[] blueline = {"Kengeri", "R V College of Engineering", "Bangalore University Cross", "Rajarajeshwari Nagar", "Nayandahalli", "Mysore Road", "Deepanjali Nagar", "Attiguppe", "Vijayanagar", "Hosahall1i", "Magadi Road", "City Railway Station", "Kempegowda Interchange", "Sir M Vishweshwariah", "Vidhana Soudha", "Cubbon Park", "M G Road Interchange", "Trinity", "Halasuru", "Indiranagar", "S V Road", "Baiyyappanahalli", "Jyotipura", "K R Puram", "Mahadevpura", "Garudacharpalya", "Doddanekkundi Induatrial State", "Vishweshwariah Industrial State", "Kundanahalli", "Vydhehi Hospital", "Satya Sai Medical Institute", "ITPB", "Kadugodi Industrial Area", "Ujjwal Vidhyalaya", "Whitefield"};

String[] redline = {"Nagawara", "Arabic College", "Venkateshpura", "Tannery Town", "Pottery Town", "Cantonment Railway Station", "Shivajinagar", "M G Road Interchange", "Vellara Junction", "Langford Town", "Mico Bosch", "Dairy Circle", "Swagath Road Cross", "Jayadeva Hospital Interchange", "J P Nagar 4th Phase", "IIMB", "Hulimavu", "Gottigere"};

String[] yellowline = {"R V Road Interchange", "Ragigudda Temple", "Jayadeva hospital Interchange", "BTM Layout", "Silk Board", "HSR Layout", "Oxford College", "Muneshwara Nagar", "Chikkabegur", "Basapura Road", "Hosa Road", "Electronics City 1", "Electronics City 2", "Huskur Road", "Hebbagodi", "Bommasandra"};

誰か助けてください。事前にサンクス。

4

1 に答える 1

2

まず、線のリストを検索対象のグラフに変換します。

  • 各ノードにその名前、エッジのリストとソースからの距離 (最初は無限大)、および最適パス内の前のノードを保持させます

  • 各エッジに両方のノード、それが属するライン、およびそのコストを保持させます。

  • 「ノード」と呼ばれるノードへの文字列のハッシュ マップを準備する

  • 「転送ノード」と呼ばれるノードのセットを準備します。これには、ハッシュ マップ文字列 (名前) => ノードを使用できます。
  • 各行:
    • 「nodes」に路線の最初の駅のエントリがない場合は、新しいノードを作成して「nodes」に追加します。
    • 最初の駅を除く各駅:
      • 「nodes」にこのステーションのエントリがない場合は、新しいノードを作成して「nodes」に追加します。
      • このステーションと前のステーションを結合する新しいエッジを作成します。そのコストは 1 です。
      • このエッジを両方のステーションのエッジのリストに追加します
      • いずれかのノードが現在複数のラインに属している場合 (ルックアップが成功した場合)、このステーションを「転送ノード」に追加します。

(注: 行は一連の変数に格納されるため、次のように「各行」を実行できます:)

private HashMap<Node> nodes;
private void addLine (String[] stops, String name){...};
// ... ( ... ){ ...
addLine(greenline, "green line");
addLine(blueline,  "blue line" );
//...

転送コストがゼロでない場合は、転送コストを追加します。

  • 「転送ノード」の各ノードについて:
    • ノードを使用する各行について:
      • 元のノードにちなんで名付けられた新しいノードを作成します。
      • その行のすべて (1 つまたは両方) のエッジを新しいノードにリダイレクトします。ソースまたは宛先を変更し、それらを新しいノード エッジ リストに追加します。
    • 新しい駅ノードのペアごとに
      • それらを結合する新しいエッジを作成し、このエッジを両方のノードのエッジ リストに追加します。その費用は譲渡費用です。

次に、ソースから宛先への最も安いパスを見つけます。ダイクストラのアルゴリズムを示します。

  • 「オープンセット」と呼ばれるノードの優先キューを準備します。転送コストが 0 または 1 の場合、これには通常のキューを使用できます。
  • ソースノードを「オープンセット」に追加します。開始ステーションが中継ステーションの場合は、関連するすべてのノードを「オープン セット」に追加します。
  • ソースからのソースノードの距離をゼロに設定します
  • 繰り返す
    • 「オープン セット」から「from」というノードをポップします。そのような要素が存在しない場合はエラーです。ノードが宛先ステーションに対応する場合は、「から」を思い出してループを中断します。
    • 「to」と呼ばれる、このノードの各ネイバーについて:
      • 「to」の新しい距離を計算します。「から」の距離に接続エッジの長さを加えたものです。
      • 新しい距離が「to」の現在の距離よりも短い場合:
        • 「to」の距離を更新します。
        • 「to」のリーディング エッジを「from」と「to」の間のエッジに更新します。
        • 距離が無限大の場合は、「オープン セット」に「to」を追加します
        • そうでなければ、「オープンセット」の「to」の位置を更新します
  • 最適パスに沿ってエッジを収集します。
  • エッジの空のリストから開始する
  • 現在のノードを「from」にします。
  • 現在のノードには以前のエッジが定義されています。
    • そうでなければ、前のエッジをエッジのリストに追加します
    • 現在のノードをこのエッジの他のノードにします

あとは、パスを読み取ることです。

  • エッジカウンターを 1 に初期化する
  • エッジのリスト内の各エッジについて:
    • これが最初のエッジの場合、「start by travelling edge.linefrom start」を出力します。
    • 前のエッジが転送エッジの場合は、「count停止後、転送先edge.lineにprevEdge.node[0].name」を出力し、エッジ カウンタをリセットします。
    • それ以外の場合は、エッジ カウンターをインクリメントします。
  • 出力 "%count停止後、" で終了し%targetます。
于 2013-10-11T08:27:12.770 に答える