K-Best Enumeration (K Shortest Path編)
Eppsteinのサーベイ読んでる。
とりあえずK Shortest Pathの部分だけ簡単にまとめる。
数字はサーベイの引用してるやつ。
- K-Best 最適化問題としてめっちゃ研究されてるのがK Shortest Path探索問題
めっちゃ引用してた(40本くらい)
- 応用が色々ある→K-bestで最適解が欲しいような問題とか
- 生物学の配列アラインメント[27, 143, 166, 167, 181]
- 0-1ナップサック問題[187]
EppsteinのKSPの論文にはDAGに落とし込んで求める方法が載ってた
マルコフモデルからグラフ作ってパス探索する？(自然言語処理に造詣がないためわからない)
なんかK-Best ビームサーチテクニックが用いられるらしい(かっこいい)
- 代謝経路の再構築[6]
- 遺伝子調節ネットワーク[171]
- モーション追跡[17]
- 通信ネットワークにおけるメッセージ経路決定[11,12,15,130,180]
- 家系図？(うまく訳せなかった)[66]
- 電力線配置[44]
- 車両と輸送計画[90,110,137,186]
- 避難計画の構築[113]
- 回路のタイミング解析[8,189]
- タスクスケジューリング[59,101]
- 通信と輸送ネットワーク設計[24, 26, 58, 61, 129]
- 他の組合せ最適化問題[19,33,51,53,79,105]のためのサブルーチン
→めちゃくちゃいっぱいあるな……(組合せ最適化問題の辺りはちょっと読んでみたい
- 基本的に、重み付き有向グラフと始点・終点、数値kが与えられるから、可能な最小の重みでs-tまでのk個の異なるウォーク(同じ頂点があってもよいパス)を見つけるってのが問題
→ウォークであることに注意(ループがあるかもしれないということ)
- EppsteinのアルゴリズムはO(m+nlogn+k)の時間計算量
最短路木作って、迂回シーケンスってのをバイナリヒープで表現するんだけどそれをうまい永続的なデータ構造テクニック使ってゴニョゴニョする
→この辺は普通に元論文を読みましょう……
- サイクルを有するグラフだと、サイクルに入らないやつ、サイクルに1回入るやつ、サイクルに2回入るやつ……みたいにサイクルをぐるぐる廻る経路が出てきちゃう
入力が無向グラフのときに、2本の有向辺使って有向グラフに変換すると自明にループがいっぱい出てくるかもね
- ClarkeとかKrikorian、Rausen[49]とかが、s-t k shortest "simple" pathsを求めるアルゴリズム開発してる
loopありに負けず劣らず引用されてる すごい[18, 30, 40, 98, 104, 132, 151, 158, 178, 188]
- この手の問題だと、Yenのアルゴリズムがいい時間計算量なんだよね
→1～k-1番目までのパスのdeviation Pathを求めて、その中のコスト最小のパスをk番目のパスにするやつ
deviation Pathを求めるために辺とかノードを削除してる
best-solution partitioningの一般的な形式に従うとこの方法の時間計算量はO(Kn(m+nlogn))だよね
→best solution partitioningってK-Best Optimization界隈では有名なのか……？
ただ、これはヒューリスティックに基づくから時々Yenのアルゴリズムと同じ計算量になっちゃうんだ
- 無向グラフの場合はもっと速くなって、O(K(m+nlogn))になるよ[89, 115, 117]
- Minieka[138]とFox[72]が、k-最短経路問題の全点対変形を考えたよ。
全点対K最短路を列挙するんやね
Eppsteinのアルゴリズムってのは前処理段階において、各頂点ごとに1つのO(n)個のコピーしか必要としないよ、んで、その後各パスを探すために一定の時間がかかるんで、計算時間はO(mn+n^2logn+kn^2)だよ
- 最短路木のK-best版とかの研究もあるっぽい、すごいな[165]
- 2つの端点が与えられたときに、その間に経路は43987439734798個くらいあると思うんだけど、そこから完全に互いに疎なペアK個を、重みが最小になるように取り出す問題もあるんだって[32, 144]
最小費用流を使って解けるっぽい→ただ、EppsteinはK-Best Enumerationっぽくないンゴねぇ……(成約が多くて列挙っぽくないから)って言ってた
200本くらい引用しててひっくり返った、他にも楽しそうなことしてるのでちょっと色々読んでみよ
追伸:
・今考えてる問題と関係してるから色々調べたけど、他の方法結構テクニカルだし""最適""の基準を変えるの難しいのでは……
→そのアルゴリズムへの深い造詣でカバー😁
