Loading article…
k最短経路ルーティング問題は、特定のネットワークにおける最短経路ルーティング問題の一般化です。最短経路だけでなく、次のk−1最短経路 (最短経路よりも長い場合があります) についても問われます。この問題のバリエーションとして、ループのないk最短経路があります。
k最短経路を見つけることは、ダイクストラのアルゴリズムまたはベルマンフォードアルゴリズムを拡張することで可能です。[引用が必要]
歴史
1957 年以来、 k最短経路ルーティング問題に関する多くの論文が発表されてきました。基礎研究のほとんどは 1960 年代から 2001 年の間に行われました。それ以降、ほとんどの研究は問題の応用とその変種に関するものになりました。2010 年に、Michael Günther らは、確率過程代数ツール CASPA を使用したk最短経路と関連尺度の記号計算に関する本を出版しました。[1]
アルゴリズム
ダイクストラのアルゴリズムは、 k 個の最短経路を見つけるために一般化できます。[引用が必要]
バリエーション
k最短経路ルーティング問題には、主に 2 つのバリエーションがあります。1 つのバリエーションでは、パスは同じノードを複数回訪問できるため、ループが作成されます。もう 1 つのバリエーションでは、パスは単純でループがないことが要求されます。ループのあるバージョンは、Eppstein のアルゴリズム[2]を使用して解決でき、ループのないバージョンはYen のアルゴリズム[ 3]で解決できます。[4]
ループ型
この変種では、経路がループレスである必要がないため、問題が簡素化される。[4] 1975 年に BL Fox が示した解決策では、k最短経路がO ( m + kn log n )の 漸近時間計算量で決定される（big O記法を使用） 。[5] 1998 年にDavid Eppstein は、経路の暗黙的な表現を計算することで漸近計算量をO ( m + n log n + k )に抑えるアプローチを報告した。この暗黙的な表現はそれぞれO ( n ) の追加時間で出力できる。[2] [4] 2015 年に Akibaらは、 Eppstein のアルゴリズムの大幅に高速な代替手段として、インデックスと呼ばれるデータ構造をグラフから構築し、任意の頂点ペア間の上位k距離を迅速に取得できるインデックス作成方法を考案した。[6]
ループなしの変種
ループなしの変種では、経路にループを含めることは禁止されており、これにより複雑さがさらに増す。[4]これは、 nノードの非負距離ネットワークで固定ノードから他のすべてのノードへのすべての最短経路の長さを見つけるために、Yen のアルゴリズム[3] [4]を使用して解決できる。この手法では、2 n 2 回の加算とn 2 回の比較のみが必要であり、他の利用可能な最短経路アルゴリズムよりも少ない。実行時間の複雑さは擬似多項式で、O ( kn ( m + n log n ))である(ここで、mとn はそれぞれ辺と頂点の数を表す)。[3] [4] 2007 年に、John HershbergerとSubhash Suri は、Lawler [7]と Yen のアルゴリズムのより効率的な実装である置換経路アルゴリズムを提案した。これは、多数のグラフに対してO ( n ) の時間改善を実現したが、すべてのグラフに対してではない (したがって、Yen のアルゴリズムの漸近境界は変更されない)。[8]
いくつかの例と説明
例1
次の例では、Yen のモデルを使用して、通信するエンド ノード間のk最短パスを検索します。つまり、最短パス、2 番目に短いパスなど、K番目の最短パスまでを検索します。詳細については、ここを参照してください。この例で提供されるコードは、単方向リンクと双方向リンクの組み合わせを含む 15 ノード ネットワークの k最短パス ルーティング問題を解決しようとします。
例2
もう 1 つの例は、k最短経路アルゴリズムを使用して複数のオブジェクトを追跡することです。この手法では、k最短経路ルーティング アルゴリズムに基づいて複数のオブジェクト トラッカーを実装します。入力として、確率的占有マップのセットが使用されます。オブジェクト検出器が入力を提供します。
詳細は「Computer Vision Laboratory – CVLAB」をご覧ください。
例3
k最短経路アルゴリズムのもう 1 つの用途は、公共交通機関の乗客の体験を向上させる交通ネットワークを設計することです。このような交通ネットワークの例は、移動時間を考慮することで構築できます。移動時間に加えて、経済的および地理的な制限に応じて他の条件が考慮される場合があります。パラメータの変動にもかかわらず、k最短経路アルゴリズムは、ほぼすべてのユーザーのニーズを満たす最適なソリューションを見つけます。このようなk最短経路アルゴリズムのアプリケーションは一般的になりつつあり、最近、Xu、He、Song、および Chaudhry (2012) は、交通ネットワーク システムにおけるk最短経路問題を研究しました。[9]
アプリケーション
k最短パス ルーティングは、次のような場合に適した代替手段です。
- 地理的経路計画
- ネットワーク ルーティング、特に通常の最短経路アルゴリズムでは解決できない追加の制約がある光メッシュ ネットワークの場合。
- 計算言語学における仮説生成
- バイオインフォマティクスにおける配列アライメントと代謝経路の発見
- 上記のように複数のオブジェクトを追跡する
- 道路ネットワーク: 道路のジャンクションはノード (頂点) であり、グラフの各エッジ (リンク) は 2 つのジャンクション間の道路セグメントに関連付けられます。
関連する問題
- 幅優先探索アルゴリズムは、検索が 2 つの操作のみに制限されている場合に使用されます。
- フロイド・ワーシャルアルゴリズムは、すべてのペアの最短経路を解きます。
- ジョンソンのアルゴリズムはすべてのペアの最短経路を解き、疎グラフではフロイド・ワーシャルのアルゴリズムよりも高速になる可能性があります。
- 摂動理論は（最悪の場合でも）局所的に最短の経路を見つけます。
Cherkasskyら[10]は、さらに多くのアルゴリズムと関連する評価を提供している。
参照
注記
- ^ Günther, Michael; Schuster, Johann; Siegle, Markus (2010-04-27). 「確率過程代数ツール CASPA による k 最短経路と関連尺度の記号計算」 確率過程代数ツール CASPA による k 最短経路と関連尺度の記号計算。ACM。pp. 13–18。doi :10.1145/1772630.1772635。ISBN 978-1-60558-916-9。
- ^ ab Eppstein, David (1998). 「k 最短経路の探索」(PDF) . SIAM J. Comput. 28 (2): 652–673. doi :10.1137/S0097539795290477.
- ^ abc Yen, JY (1971). 「ネットワーク内のk最短ループレスパスの検出」.経営科学. 1 7 (11): 712–716. doi :10.1287/mnsc.17.11.712.。
- ^ abcdef Bouillet, Eric; Ellinas, Georgios; Labourdette, Jean-Francois; Ramamurthy, Ramu (2007). 「パス ルーティング - パート 2: ヒューリスティック」。メッシュ光ネットワークにおけるパス ルーティング。John Wiley & Sons。pp. 125–138。ISBN 9780470015650。
- ^ Fox, BL (1975). 「K番目の最短経路と確率ネットワークへの応用」. ORSA/TIMS 合同全国会議. 23 : B263. CiNii 全国記事ID : 10012857200。
- ^ 秋葉 拓也、林 孝典、野里 望、岩田 洋一、吉田 雄一 (2015 年 1 月)。「プルーニングされたランドマーク ラベリングによる大規模ネットワークでの効率的なトップ k 最短パス距離クエリ」。第 29 回 AAAI 人工知能会議の議事録。テキサス州オースティン:人工知能推進協会。pp. 2–8。
- ^ Lawler, Eugene L. (1972-03-01). 「離散最適化問題に対する K 最適解を計算する手順と最短経路問題へのその応用」. Management Science . 18 (7): 401–405. doi :10.1287/mnsc.18.7.401. ISSN 0025-1909.
- ^ Hershberger, John ; Maxel, Matthew; Suri, Subhash (2007). 「k 最短単純パスの検出: 新しいアルゴリズムとその実装」(PDF) . ACM Transactions on Algorithms . 3 (4). 記事 45 (19 ページ). doi :10.1145/1290672.1290682. S2CID 10703503.
- ^ Xu, Wangtu; He, Shiwei; Song, Rui; Chaudhry, Sohail S. (2012). 「スケジュールベースのトランジットネットワークにおけるk最短経路の検索」。Computers & Operations Research。39 ( 8): 1812–1826. doi :10.1016/j.cor.2010.02.005. S2CID 29232689。
- ^ Cherkassky, Boris V.; Goldberg, Andrew V .; Radzik, Tomasz (1996). 「最短経路アルゴリズム: 理論と実験的評価」.数学プログラミング. 73 (2): 129–174. doi :10.1007/BF02592101. ISSN 0025-5610. S2CID 414427.
外部リンク
- 円のアルゴリズムの実装
- Yen のアルゴリズムと最速 k 最短単純経路アルゴリズムの実装
- http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/#more-2432
- K 最短経路アルゴリズムを使用した複数オブジェクトの追跡技術: http://cvlab.epfl.ch/software/ksp/
- コンピュータビジョン研究所: http://cvlab.epfl.ch/software/ksp/