ORWiki - 利用者の投稿記録 [ja]

利用者:Albeit-Kun/最短路検索

2009-11-17T12:35:36Z

Albeit-Kun: /* 階層メッシュ疎化法 */

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表1に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center; margin:0 auto"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である<ref>Doran,J.: An approach to automatic problem-solving, ''Machine Intelligence'', Vol.1 (1967), 105--127.</ref>,<ref>Hart,P.E., Nilsson,N.J. and Raphael,B.: A formal basis for the heuristic determination of minimum cost paths, ''IEEE Transactions on System Science and Cybernetics'', Vol.~4 (1968), 100--107.</ref>．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある<ref>Goldberg,A.V. and Harrelson,C.: Computing the shortest path: A search meets graph theory, in ''Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms'', 2005, SIAM</ref>．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
(これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ)．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図1にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．

[[画像:3-way-g.png|thumb|center|500px|図1: ダイクストラ法とA*法の探索範囲]]

ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける<ref>Köhler,E., Möhring,R.H. and Schilling,H.: Acceleration of shortest path and constrained shortest path computation, in ''Experimental and Efficient Algorithms'', Vol. 3503 of ''LNCS'', Springer, 2005.</ref>．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である<ref>Sanders,P. and Schultes,D.: Highway hierarchies hasten exact shortest path queries, in ''Proceedings of the 13th European Symposium on Algorithms'', Vol. 3669 of ''LNCS'', Springer, 2005</ref>．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)</math>の平均<math>)\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている<ref>Bast,H., Funke,S., Sanders,P. and Schultes,D.: Fast Routing in Road Networks with Transit Nodes, ''Science'', Vol. 316 (2007), 566</ref>．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である<ref>宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法, 情報処理学会研究報告, 第AL-119巻, 2008</ref>．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\mathbb{R}^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \mathbb{R}^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \mathbb{R}^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図2は残った枝を正方形の大きさごとに示した例である．

<gallery caption="図2: 抽出された枝の例" widths="200px" heights="200px" perrow="2">
画像:3-g.png
画像:4-g.png
画像:5-g.png
画像:6-g.png
</gallery>

この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図3に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．

[[画像:ny-d.png|thumb|center|500px|図3: 疎化ネットワーク上の最短路の例]]

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

<references />

利用者:Albeit-Kun/最短路検索

2009-11-17T12:34:25Z

Albeit-Kun: /* 階層メッシュ疎化法 */

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表1に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center; margin:0 auto"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である<ref>Doran,J.: An approach to automatic problem-solving, ''Machine Intelligence'', Vol.1 (1967), 105--127.</ref>,<ref>Hart,P.E., Nilsson,N.J. and Raphael,B.: A formal basis for the heuristic determination of minimum cost paths, ''IEEE Transactions on System Science and Cybernetics'', Vol.~4 (1968), 100--107.</ref>．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある<ref>Goldberg,A.V. and Harrelson,C.: Computing the shortest path: A search meets graph theory, in ''Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms'', 2005, SIAM</ref>．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
(これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ)．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図1にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．

[[画像:3-way-g.png|thumb|center|500px|図1: ダイクストラ法とA*法の探索範囲]]

ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける<ref>Köhler,E., Möhring,R.H. and Schilling,H.: Acceleration of shortest path and constrained shortest path computation, in ''Experimental and Efficient Algorithms'', Vol. 3503 of ''LNCS'', Springer, 2005.</ref>．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である<ref>Sanders,P. and Schultes,D.: Highway hierarchies hasten exact shortest path queries, in ''Proceedings of the 13th European Symposium on Algorithms'', Vol. 3669 of ''LNCS'', Springer, 2005</ref>．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)</math>の平均<math>)\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている<ref>Bast,H., Funke,S., Sanders,P. and Schultes,D.: Fast Routing in Road Networks with Transit Nodes, ''Science'', Vol. 316 (2007), 566</ref>．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である<ref>宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法, 情報処理学会研究報告, 第AL-119巻, 2008</ref>．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\mathbb{R}^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \mathbb{R}^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \mathbb{R}^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図2は残った枝を正方形の大きさごとに示した例である．

<gallery caption="図2: 抽出された枝の例" widths="300px" heights="300px" perrow="2">
画像:3-g.png
画像:4-g.png
画像:5-g.png
画像:6-g.png
</gallery>

この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図3に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．

[[画像:ny-d.png|thumb|center|500px|図3: 疎化ネットワーク上の最短路の例]]

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

<references />

利用者:Albeit-Kun/最短路検索

2009-11-17T12:33:28Z

Albeit-Kun: /* 階層メッシュ疎化法 */

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表1に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center; margin:0 auto"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である<ref>Doran,J.: An approach to automatic problem-solving, ''Machine Intelligence'', Vol.1 (1967), 105--127.</ref>,<ref>Hart,P.E., Nilsson,N.J. and Raphael,B.: A formal basis for the heuristic determination of minimum cost paths, ''IEEE Transactions on System Science and Cybernetics'', Vol.~4 (1968), 100--107.</ref>．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある<ref>Goldberg,A.V. and Harrelson,C.: Computing the shortest path: A search meets graph theory, in ''Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms'', 2005, SIAM</ref>．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
(これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ)．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図1にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．

[[画像:3-way-g.png|thumb|center|500px|図1: ダイクストラ法とA*法の探索範囲]]

ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける<ref>Köhler,E., Möhring,R.H. and Schilling,H.: Acceleration of shortest path and constrained shortest path computation, in ''Experimental and Efficient Algorithms'', Vol. 3503 of ''LNCS'', Springer, 2005.</ref>．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である<ref>Sanders,P. and Schultes,D.: Highway hierarchies hasten exact shortest path queries, in ''Proceedings of the 13th European Symposium on Algorithms'', Vol. 3669 of ''LNCS'', Springer, 2005</ref>．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)</math>の平均<math>)\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている<ref>Bast,H., Funke,S., Sanders,P. and Schultes,D.: Fast Routing in Road Networks with Transit Nodes, ''Science'', Vol. 316 (2007), 566</ref>．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である<ref>宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法, 情報処理学会研究報告, 第AL-119巻, 2008</ref>．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\mathbb{R}^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \mathbb{R}^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \mathbb{R}^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図2は残った枝を正方形の大きさごとに示した例である．

<gallery caption="図2: 抽出された枝の例" widths="150px" heights="150px" perrow="4">
画像:3-g.png
画像:4-g.png
画像:5-g.png
画像:6-g.png
</gallery>

この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図3に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．

[[画像:ny-d.png|thumb|center|500px|図3: 疎化ネットワーク上の最短路の例]]

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

<references />

ファイル:5-g.png

2009-11-17T12:32:18Z

Albeit-Kun:

ファイル:6-g.png

2009-11-17T12:30:36Z

Albeit-Kun:

利用者:Albeit-Kun/最短路検索

2009-11-17T12:29:33Z

Albeit-Kun: /* 階層メッシュ疎化法 */

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表1に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center; margin:0 auto"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である<ref>Doran,J.: An approach to automatic problem-solving, ''Machine Intelligence'', Vol.1 (1967), 105--127.</ref>,<ref>Hart,P.E., Nilsson,N.J. and Raphael,B.: A formal basis for the heuristic determination of minimum cost paths, ''IEEE Transactions on System Science and Cybernetics'', Vol.~4 (1968), 100--107.</ref>．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある<ref>Goldberg,A.V. and Harrelson,C.: Computing the shortest path: A search meets graph theory, in ''Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms'', 2005, SIAM</ref>．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
(これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ)．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図1にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．

[[画像:3-way-g.png|thumb|center|500px|図1: ダイクストラ法とA*法の探索範囲]]

ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける<ref>Köhler,E., Möhring,R.H. and Schilling,H.: Acceleration of shortest path and constrained shortest path computation, in ''Experimental and Efficient Algorithms'', Vol. 3503 of ''LNCS'', Springer, 2005.</ref>．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である<ref>Sanders,P. and Schultes,D.: Highway hierarchies hasten exact shortest path queries, in ''Proceedings of the 13th European Symposium on Algorithms'', Vol. 3669 of ''LNCS'', Springer, 2005</ref>．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)</math>の平均<math>)\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている<ref>Bast,H., Funke,S., Sanders,P. and Schultes,D.: Fast Routing in Road Networks with Transit Nodes, ''Science'', Vol. 316 (2007), 566</ref>．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である<ref>宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法, 情報処理学会研究報告, 第AL-119巻, 2008</ref>．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\mathbb{R}^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \mathbb{R}^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \mathbb{R}^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図2は残った枝を正方形の大きさごとに示した例である．

<gallery caption="図2: 抽出された枝の例" widths="150px" heights="150px" perrow="4">
画像:3-g.png
画像:4-g.png
画像ル:5-g.png
画像:6-g.png
</gallery>

この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図3に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．

[[画像:ny-d.png|thumb|center|500px|図3: 疎化ネットワーク上の最短路の例]]

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

<references />

ファイル:4-g.png

2009-11-17T12:28:01Z

Albeit-Kun:

ファイル:Ny-d.png

2009-11-17T12:26:54Z

Albeit-Kun:

ファイル:3-way-g.png

2009-11-17T12:25:21Z

Albeit-Kun:

ファイル:3-g.png

2009-11-17T12:23:37Z

Albeit-Kun:

利用者:Albeit-Kun/最短路検索

2009-11-17T10:42:41Z

Albeit-Kun:

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表1に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center; margin:0 auto"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である<ref>Doran,J.: An approach to automatic problem-solving, ''Machine Intelligence'', Vol.1 (1967), 105--127.</ref>,<ref>Hart,P.E., Nilsson,N.J. and Raphael,B.: A formal basis for the heuristic determination of minimum cost paths, ''IEEE Transactions on System Science and Cybernetics'', Vol.~4 (1968), 100--107.</ref>．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある<ref>Goldberg,A.V. and Harrelson,C.: Computing the shortest path: A search meets graph theory, in ''Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms'', 2005, SIAM</ref>．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
(これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ)．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図1にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．

[[画像:3-way-g.png|thumb|center|500px|図1: ダイクストラ法とA*法の探索範囲]]

ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける<ref>Köhler,E., Möhring,R.H. and Schilling,H.: Acceleration of shortest path and constrained shortest path computation, in ''Experimental and Efficient Algorithms'', Vol. 3503 of ''LNCS'', Springer, 2005.</ref>．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である<ref>Sanders,P. and Schultes,D.: Highway hierarchies hasten exact shortest path queries, in ''Proceedings of the 13th European Symposium on Algorithms'', Vol. 3669 of ''LNCS'', Springer, 2005</ref>．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)</math>の平均<math>)\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている<ref>Bast,H., Funke,S., Sanders,P. and Schultes,D.: Fast Routing in Road Networks with Transit Nodes, ''Science'', Vol. 316 (2007), 566</ref>．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である<ref>宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法, 情報処理学会研究報告, 第AL-119巻, 2008</ref>．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\mathbb{R}^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \mathbb{R}^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \mathbb{R}^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図2は残った枝を正方形の大きさごとに示した例である．

<gallery caption="図2: 抽出された枝の例" widths="150px" heights="150px" perrow="4">
ファイル:3-g.png
ファイル:4-g.png
ファイル:5-g.png
ファイル:6-g.png
</gallery>

この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図3に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．

[[画像:ny-d.png|thumb|center|500px|図3: 疎化ネットワーク上の最短路の例]]

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

<references />

利用者:Albeit-Kun/最短路検索

2009-11-17T10:18:33Z

Albeit-Kun:

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表1に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である<ref>Doran,J.: An approach to automatic problem-solving, ''Machine Intelligence'', Vol.1 (1967), 105--127.</ref>,<ref>Hart,P.E., Nilsson,N.J. and Raphael,B.: A formal basis for the heuristic determination of minimum cost paths, ''IEEE Transactions on System Science and Cybernetics'', Vol.~4 (1968), 100--107.</ref>．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

===== アルゴリズム ======

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある<ref>Goldberg,A.V. and Harrelson,C.: Computing the shortest path: A search meets graph theory, in ''Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms'', 2005, SIAM</ref>．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
\footnote{これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ}．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図1にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．

[[画像:3-way-g.png|thumb|center|500px|図1: ダイクストラ法とA*法の探索範囲]]

ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける<ref>Köhler,E., Möhring,R.H. and Schilling,H.: Acceleration of shortest path and constrained shortest path computation, in ''Experimental and Efficient Algorithms'', Vol. 3503 of ''LNCS'', Springer, 2005.</ref>．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である<ref>Sanders,P. and Schultes,D.: Highway hierarchies hasten exact shortest path queries, in ''Proceedings of the 13th European Symposium on Algorithms'', Vol. 3669 of ''LNCS'', Springer, 2005</ref>．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)\text{の平均})\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている<ref>Bast,H., Funke,S., Sanders,P. and Schultes,D.: Fast Routing in Road Networks with Transit Nodes, ''Science'', Vol. 316 (2007), 566</ref>．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である<ref>宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法, 情報処理学会研究報告, 第AL-119巻, 2008</ref>．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\mathbb{R}^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \mathbb{R}^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \mathbb{R}^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図2は残った枝を正方形の大きさごとに示した例である．

<gallery caption="図2: 抽出された枝の例" widths="200px" heights="200px" perrow="4">
ファイル:3-g.png
ファイル:4-g.png
ファイル:5-g.png
ファイル:6-g.png
</gallery>

この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図3に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．

[[画像:ny-d.png|thumb|center|500px|図3: 疎化ネットワーク上の最短路の例]]

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

<references />

利用者:Albeit-Kun/最短路検索

2009-11-17T08:53:08Z

Albeit-Kun:

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s</math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表~\ref{table}に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である~\cite{Doran1967,Hart1968}．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

===== アルゴリズム ======

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>\\
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある~\cite{Goldberg2005}．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
\footnote{これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ}．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図~\ref{fig:landmark}にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．
\begin{figure}[htb]
\begin{center}
\includegraphics[width=8cm,clip]{3-way-g.eps}
\end{center}
\caption{ダイクストラ法とA*法の探索範囲}
\label{fig:landmark}
\end{figure}
ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける~\cite{Kohler2005}．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である~\cite{Sanders2005}．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)\text{の平均})\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている~\cite{Bast2007b}．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である~\cite{Miyamoto2008}．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\Real^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \Real^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \Real^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図~\ref{fig:4level}は残った枝を正方形の大きさごとに示した例である．
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4cm,clip]{3-g.eps}
\includegraphics[width=4cm,clip]{4-g.eps}
\includegraphics[width=4cm,clip]{5-g.eps}
\includegraphics[width=4cm,clip]{6-g.eps}
\end{center}
\caption{抽出された枝の例}
\label{fig:4level}
\end{figure}
この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図~\ref{fig:lms}に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．
\begin{figure}[htb]
\begin{center}
\includegraphics[width=8cm,clip]{ny-d.eps}
\end{center}
\caption{疎化ネットワーク上の最短路の例}
\label{fig:lms}
\end{figure}

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

%\bibliographystyle{jorsj}
%\bibliography{../../bib/all}

\begin{thebibliography}{1}

\bibitem{Bast2007b}
Bast,~H., Funke,~S., Sanders,~P. and Schultes,~D.: Fast Routing in Road
Networks with Transit Nodes, {\em Science}, Vol. 316 (2007), 566.

\bibitem{Doran1967}
Doran,~J.: An approach to automatic problem-solving, {\em Machine
Intelligence}, Vol.~1 (1967), 105--127.

\bibitem{Goldberg2005}
Goldberg,~A.~V. and Harrelson,~C.: Computing the shortest path: A search meets
graph theory, in {\em
%SODA '05:
Proceedings of the 16th annual ACM-SIAM
symposium on Discrete algorithms},
%Philadelphia, PA, USA,
2005,
%Society for Industrial and Applied Mathematics.
SIAM.

\bibitem{Hart1968}
Hart,~P.~E., Nilsson,~N.~J. and Raphael,~B.: A formal basis for the heuristic
determination of minimum cost paths, {\em IEEE Transactions on System Science
and Cybernetics}, Vol.~4 (1968), 100--107.

\bibitem{Kohler2005}
K{\"o}hler,~E., M{\"o}hring,~R.~H. and Schilling,~H.: Acceleration of shortest
path and constrained shortest path computation, in {\em Experimental and
Efficient Algorithms}, Vol. 3503 of
%{\em Lecture Notes in Computer Science},
{\em LNCS},
Springer, 2005.

\bibitem{Miyamoto2008}
宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法,
情報処理学会研究報告, 第AL-119巻, 2008.

\bibitem{Sanders2005}
Sanders,~P. and Schultes,~D.: Highway hierarchies hasten exact shortest path
queries, in {\em Proceedings of the 13th European Symposium on Algorithms},
Vol. 3669 of
%{\em Lecture Notes in Computer Science},
{\em LNCS},
Springer, 2005.

\end{thebibliography}

\end{document}

== 参考文献 ==

利用者:Albeit-Kun/最短路検索

2009-11-17T08:52:17Z

Albeit-Kun:

'''【さいたんろけんさく（shotest path query）】'''

==概要==

与えられたネットワーク上での2 地点間最短路検索を最短路検索とよぶ．

ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2地点間最短路検索を最短路検索とよぶ．
ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

=== 最短路検索とは ===

枝重み付きネットワーク上で始点<math>s<math>から終点<math>t\, </math>に至る経路のうち，その枝重み和が最小となる経路を<math>st\, </math>-最短路とよぶ．
（本稿では<math>st\, </math>-最短路長を<math>d(s,t)\, </math>で表す．）
最短路検索は<math>st\, </math>-最短路を高速に検索することを主な目的とする．
その厳密な定義はないがおおむね以下の通りである．
<blockquote>
入力データとして与えられた枝重み付きネットワーク<math>G=(V,E)\, </math>に'''前処理'''を施して，付加データを生成する．
始点<math>s\, </math>，終点<math>t\, </math>の問い合わせに対して入力データと付加データを使って<math>st\, </math>-最短路（あるいは<math>d(s,t)\, </math>）を'''検索'''する．
</blockquote>
ネットワークデータは滅多に変化しないが<math>st\, </math>-最短路の問い合わせは頻繁にあるような，交通におけるナビゲーションなどを主な応用とする．

交通ネットワークなどを応用とする多くの最短路検索においては，入力の枝重みが非負であることが多い．
本稿では枝重みが非負の最短路検索のみを扱う．

最短路検索手法として，最適解を出力するとは限らない，近似的な解を出力する手法も考えられる．
本稿では最適解のみを出力する手法を扱う．
また，計算幾何の手法を用いて連続領域における最短路を検索する手法の研究もあるが，本稿ではネットワークを入力データとする最短路検索のみを扱う．

例えば，前処理を全くせずに，始点・終点の問い合わせに対して'''ダイクストラ（Dijkstra）法'''を実行し最短路を出力するのも最短路検索手法の一つと言える．
本稿で紹介する手法はいずれも，道路ネットワークなどが入力データとして与えられた場合には，検索速度はダイクストラ法に比べて大幅に速くなるが，最悪の場合の計算量は単純にダイクストラ法を実行する手法と変わらない．

=== 代表的な手法の効率の比較 ===

最短路検索手法の性能に関する重要な要素は，検索時の応答の速さ，付加するデータの大きさ，前処理にかかる時間，の３つである．
表~\ref{table}に，次節以降で紹介する代表的な手法のおおまかな比較を示す．
入力データが全米道路ネットワーク（約2300万点，約5800万枝）程度の大きさであることを想定している．

{| border="1" style="text-align:center"
|+ 表1: 各最短路検索手法の比較
! 手法 !! 検索 !! 付加データ !! 前処理
|-
! A*+ランドマーク
| 数十倍 || 数百％ || 数十秒
|-
! ビットベクトル
| 数百倍 || 数百％ || 数日
|-
! ハイウェイ
| 数万倍 || 百数十％ || 数十分
|-
! トランジット
| 数十万倍 || 数百％ || 数時間
|-
! 階層メッシュ
| 数千倍 || 数％ || 数時間
|}

ここで「検索」はダイクストラ法で最短路を計算する場合に比べて何倍速いか，
「付加データ」は高速化のために追加される付加データの大きさは入力データの何％程度か，
「前処理」は前処理にかかる時間が2009年現在の高性能なパソコンでどのくらいか，
を表す．

===A*法===

'''A*（A-star）法'''は各点<math>v \in V\, </math>と終点<math>t\in V\, </math>との最短路長の下界<math>\overline{d(v,t)}\, </math>を用いて，探索点の数を節約する方法である~\cite{Doran1967,Hart1968}．

====A*法のアルゴリズム====

枝<math>(v,w)\in E\, </math>の重みを<math>l(v,w)\, </math>とする．
始点<math>s\, </math>から点<math>v \in V\, </math>への最短距離の暫定値を<math>d(v)\, </math>とする．

===== アルゴリズム ======

1: <math>d(s):=0,\ d(v):=\infty,\ \forall v\in V\setminus \{s\}\, </math>
2: <math>S:=V\, </math>\\
3: '''while'''<math>S \neq \emptyset\, </math> '''do'''
4: <math>d(v)+\overline{d(v,t)}\, </math>が最小の点<math>v\in S\, </math>を選択
5: '''if''' <math>v=t\, </math> '''then'''
6: '''finish'''
7: '''end if'''
8: <math>S:=S\setminus\{v\}\, </math>
9: '''for''' '''all''' <math>(v,w)\, </math> '''do'''
10: '''if''' <math>d(v)+l(v,w)<d(w)\, </math> '''then'''
11: <math>d(w):=d(v)+l(v,w)\, </math>
12: <math>S:=S\cup\{w\}\, </math>
13: '''end if'''
14: '''end for'''
15: '''end while'''

アルゴリズム終了時の<math>d(t)\, </math>が<math>st\, </math>-最短路の長さである．

ダイクストラ法との違いは4行目と12行目である．
4行目ですべての<math>v\in V\, </math>に関して<math>\overline{d(v,t)}:=0\, </math>とすれば，ダイクストラ法と挙動が同じになる．
A*法とダイクストラ法を比べた場合，A*法の長所は探索点を少なくできること，短所は一度探索した点を再び探索する可能性があることと一探索あたりの計算が（下界を考慮する分）若干複雑であることである．

====ランドマークを用いた下界の強化====

例えば，入力データのネットワークがユークリッド平面上に埋め込まれたもので，枝重みが枝の両端点のユークリッド距離であるとき，点対間のユークリッド距離は点対間の最短路長の下界となる．
この下界をA*法で利用するのはもっとも単純な工夫の一つである．
より強いA*法の下界として，'''ランドマーク（landmark）'''とよばれる点の集合<math>K\subseteq V\, </math>を用いる方法がある~\cite{Goldberg2005}．
一般に枝重み付きネットワーク<math>G=(V,E)\, </math>の3点<math>k,u,v \in V\, </math>に関して，
三角不等式<math>d(u,v) \ge d(k,v)-d(k,u)\, </math>が成り立つ
\footnote{これは最短路長に関する三角不等式なので，枝重みに関して三角不等式が成り立たなくても，必ず成り立つ}．
ランドマークを用いた工夫では，すべての<math>k\in K\, </math>，すべての<math>v\in V\, </math>に関して<math>d(k,v)\, </math>を前処理で計算し<math>\overline{d(v,t)}:=\max\{d(k,t)-d(k,v)~|~k\in K\}\, </math>とする．
図~\ref{fig:landmark}にダイクストラ法およびA*法で探索される範囲の例を示す．
最短路は右下（始点）から左上（終点）への太線である．
薄いものから順に，ダイクストラ法で探索される範囲，下界としてユークリッド距離を用いたA*法で探索される範囲，ランドマーク16個を用いたA*法で探索される範囲である．
\begin{figure}[htb]
\begin{center}
\includegraphics[width=8cm,clip]{3-way-g.eps}
\end{center}
\caption{ダイクストラ法とA*法の探索範囲}
\label{fig:landmark}
\end{figure}
ランドマークをまばらに配置すれば，その数は十数個で十分な性能を発揮することが知られている．
このとき付加データの大きさは入力データの数倍程度である．
ランドマークを用いる長所は付加データの生成が，最短路木をランドマークの数だけ作ればよいので，かなり高速であることである．
短所は，ランドマークをいくら増やしても検索時の計算時間はあまり減らないことである．

===ビットベクトル法===

'''ビットベクトル（bit vector）法'''は，最短路を探索する際の探索方向を終点方向に強く限定する手法である．
そのために付加データとして各枝にバイナリベクトルを対応づける~\cite{Kohler2005}．
前処理では，まず入力ネットワーク<math>G=(V,E)\, </math>の点集合<math>V\, </math>を<math>N\, </math>個の部分集合<math>V_1,\dots,V_N\, </math>に分割する．
（ここで<math>N\, </math>はビットベクトル法を調整するためのパラメータである．）
そしてネットワークの各枝<math>e\in E\, </math>に付随するベクトルの第<math>i\, </math>成分を
「終点が<math>V_i\, </math>に含まれる最短路に<math>e\, </math>が含まれるならば1，そうでないならば0」
に設定する．
検索時には，始点からダイクストラ法で最短路を探索するが，終点が<math>V_j\, </math>に含まれるならば，付随するベクトルの第<math>j\, </math>成分が1である枝のみを探索に用いればよい．

分割<math>V_1,\dots,V_N\, </math>の各部分集合<math>V_i\, </math>が近い場所にまとまっていると枝に付随するベクトルの1成分が少なくなるため効率がよい．
よって一般には（超）平面に埋め込まれた点集合を平面上の矩形分割に対応して分割することが多い．
点集合<math>V\, </math>の分割数が<math>N\, </math>のとき，枝に付随するベクトルはそれぞれ<math>N\, </math>次元ベクトルになる．
よって，例えば32ビットコンピューターであれば<math>N\, </math>は32の倍数が適切である．
<math>N\, </math>が数十でも十分な性能を発揮する．

長所は，パラメータ<math>N\, </math>の設定範囲が広いことである．
<math>N\, </math>が点数に近くなると，各点に関して（終点に向かう）最短路木を保持することに近くなる．
短所は，前処理時間の短縮が難しいことである．

===ハイウェイヒエラルキー法===

'''ハイウェイヒエラルキー（highway hierarchy）法'''は，最短路でよく使われる枝（ハイウェイとよばれる）を階層的に抽出しておいて，検索時にそれを用いる方法である~\cite{Sanders2005}．

点<math>v\in V\, </math>の近傍<math>N(v)\, </math>を「<math>v\, </math>に最も近い<math>x\, </math>点」と定義する．
（ここで<math>x\, </math>はハイウェイヒエラルキー法を調整するためのパラメータである．）
枝<math>e\in E\, </math>は，それを含む<math>st\, </math>-最短路が存在して<math>N(s)\, </math>にも<math>N(t)\, </math>にも接続しないとき，ハイウェイであると見なされる．

検索時には始点から<math>x\, </math>点までは入力データを，それ以降は付加データであるハイウェイのみを探索に使う．
終点付近でも入力データを使う必要があるため，双方向探索をする必要がある．

また，ハイウェイのみからなるネットワークからさらに上位のハイウェイを同様に抽出することによって階層的なハイウェイを構築し，大幅な効率化を図れる．
近傍の点数は数十程度，ハイウェイの階層は数層で十分な性能を発揮する．
長所は，定義通りに計算すると時間がかかりそうなハイウェイの抽出（前処理）が，アルゴリズムの工夫により高速にできることである．
短所は，双方向探索しかできないことと，それに伴い探索が若干複雑であることである．

===トランジットノード法===

トランジットノード（transit node）法は「遠い地点間を結ぶ最短路の多くは重要な交差点を通る」という経験則に基づいた手法である．

'''トランジットノード'''の集合<math>T\, </math>を「ある程度長い最短路は必ず<math>T\, </math>のいずれかを通るような<math>T\subset V\, </math>」と定義する．
トランジットノードの集合<math>T\, </math>をひとたび定めると，ある程度長い<math>st\, </math>-最短路上にはトランジットノードが複数含まれることがある．
これらのトランジットノードのうち，始点<math>s\, </math>から最初に訪れる可能性があるものの集合を<math>T_\text{out}(s)\, </math>で表す．
同様に終点<math>t\, </math>の直前に訪れる可能性があるものの集合を<math>T_\text{in}(t)\, </math>で表す．
前処理では，各点<math>v\, </math>に対応する<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度で抑えられるような，そして<math>T\, </math>の大きさもなるべく小さくなるようなトランジットノードの集合を見つける．
そしてすべての<math>v\in V\, </math>に関して<math>d(v,w), \forall w\in T_\text{out}(v)\, </math>および<math>d(w,v), \forall w\in T_\text{in}(v)\, </math>を計算・記憶し，すべての<math>v,w\in T\, </math>に関して<math>d(v,w)\, </math>を計算・記憶する．

検索時には，与えられた<math>s,t\, </math>に対して，<math>\min\{d(s,v)+d(v,w)+d(w,t)~|~v\in T_\text{out}(s) ,w\in T_\text{in}(t)\}\, </math>を計算すれば<math>st\, </math>-最短路長がわかる．
（ただし<math>s\, </math>と<math>t\, </math>が近い場合にはトランジットノードを利用できない．）
<math>T_\text{out}(v),T_\text{in}(v)\, </math>の大きさが平均的に定数程度に抑えられていれば，検索における計算は非常に短かい時間で終了する．

付加データの大きさはトランジットノードの数に依存し，おおむね
<math>|T|^2+|V|\times(T_\text{out}(v),T_\text{in}(v)\text{の平均})\, </math>程度である．
トランジットノードの集合<math>T\, </math>の大きさは数百から数千で十分な性能を発揮する．
このとき付加データの大きさは入力データの数倍程度になる．

欠点は，
あまり長くない<math>st\, </math>-最短路ではトランジットノードを利用できないことである．
トランジットノードを利用できない場合には，別の手法で<math>st\, </math>-最短路を見つけなければならない．

ハイウェイヒエラルキー法の最上位ハイウェイの点をトランジットノードとする手法が提案されており，良好な結果が報告されている~\cite{Bast2007b}．

===階層メッシュ疎化法===

階層メッシュ疎化法は，遠い地点間の最短路では絶対に使われない枝を省いた疎なネットワークを前処理で生成し，それを検索時に利用して高速化する手法である~\cite{Miyamoto2008}．
前処理および検索においてグラフの点の座標を用いることが特徴であり，結果として付加データの軽減に成功している．
付加データの大きさは入力データの数％で十分な性能を発揮する．
以下，グラフは（超）平面に埋め込まれているとする．

前処理では，平面を矩形分割し，各矩形に含まれる枝のうち，その矩形から遠いところ同士を結ぶ最短路で使われない枝を省く．
例えば，2次元平面<math>\Real^2\, </math>を一辺の長さ<math>c\, </math>の正方形領域<math>R_{i,j}:=\{(x,y)\in \Real^2~|~ic\le x < (i+1)c,~jc\le y < (j+1)c\}\, </math>に分割する．
そして，領域<math>R_{i,j}\, </math>に含まれる枝のうち，領域<math>\{(x,y)\in \Real^2~|~(i-1)c\le x < (i+2)c,~(j-1)c\le y < (j+2)c\}\, </math>（これは<math>R_{i,j}\, </math>を中心として9倍の面積を持つ正方形である）の外側に始点・終点をもつ最短路では一度も使われないものを省く．
正方形が大きければ，残された枝は入力データに比べて疎なものとなる．
図~\ref{fig:4level}は残った枝を正方形の大きさごとに示した例である．
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4cm,clip]{3-g.eps}
\includegraphics[width=4cm,clip]{4-g.eps}
\includegraphics[width=4cm,clip]{5-g.eps}
\includegraphics[width=4cm,clip]{6-g.eps}
\end{center}
\caption{抽出された枝の例}
\label{fig:4level}
\end{figure}
この例では，正方形の一辺の長さを2の冪乗に限定している．
これにより，大きな正方形で残される枝の計算に，小さな正方形で残された枝のみを利用できるので前処理が効率的に行える．

検索時には，始点・終点に近いところでは小さな正方形に含まれている枝を，遠いところでは大きな正方形に含まれている枝のみを使って最短路探索すればよい．
図~\ref{fig:lms}に階層メッシュ疎化法の検索で用いられる疎なネットワークの例を示す．
\begin{figure}[htb]
\begin{center}
\includegraphics[width=8cm,clip]{ny-d.eps}
\end{center}
\caption{疎化ネットワーク上の最短路の例}
\label{fig:lms}
\end{figure}

長所は，疎なネットワークを抽出しているだけなので，検索時の探索法の選択に自由度があること，それゆえに実装が簡単であることである．
短所は，グラフを（超）平面に埋め込む必要があること，前処理時間の短縮が難しいことである．

== 参考文献 ==

%\bibliographystyle{jorsj}
%\bibliography{../../bib/all}

\begin{thebibliography}{1}

\bibitem{Bast2007b}
Bast,~H., Funke,~S., Sanders,~P. and Schultes,~D.: Fast Routing in Road
Networks with Transit Nodes, {\em Science}, Vol. 316 (2007), 566.

\bibitem{Doran1967}
Doran,~J.: An approach to automatic problem-solving, {\em Machine
Intelligence}, Vol.~1 (1967), 105--127.

\bibitem{Goldberg2005}
Goldberg,~A.~V. and Harrelson,~C.: Computing the shortest path: A search meets
graph theory, in {\em
%SODA '05:
Proceedings of the 16th annual ACM-SIAM
symposium on Discrete algorithms},
%Philadelphia, PA, USA,
2005,
%Society for Industrial and Applied Mathematics.
SIAM.

\bibitem{Hart1968}
Hart,~P.~E., Nilsson,~N.~J. and Raphael,~B.: A formal basis for the heuristic
determination of minimum cost paths, {\em IEEE Transactions on System Science
and Cybernetics}, Vol.~4 (1968), 100--107.

\bibitem{Kohler2005}
K{\"o}hler,~E., M{\"o}hring,~R.~H. and Schilling,~H.: Acceleration of shortest
path and constrained shortest path computation, in {\em Experimental and
Efficient Algorithms}, Vol. 3503 of
%{\em Lecture Notes in Computer Science},
{\em LNCS},
Springer, 2005.

\bibitem{Miyamoto2008}
宮本裕一郎, 宇野毅明, 久保幹雄：最短路高速検索のための階層メッシュ疎化法,
情報処理学会研究報告, 第AL-119巻, 2008.

\bibitem{Sanders2005}
Sanders,~P. and Schultes,~D.: Highway hierarchies hasten exact shortest path
queries, in {\em Proceedings of the 13th European Symposium on Algorithms},
Vol. 3669 of
%{\em Lecture Notes in Computer Science},
{\em LNCS},
Springer, 2005.

\end{thebibliography}

\end{document}

== 参考文献 ==

利用者:Albeit-Kun/最短路検索

2009-11-17T07:56:35Z

Albeit-Kun:

利用者:Albeit-Kun/最短路検索

2009-11-07T06:33:32Z

Albeit-Kun:

利用者:Albeit-Kun/最短路検索

2009-11-07T06:25:01Z

Albeit-Kun:

'''【さいたんろけんさく（shotest path query）】'''

== 概要 ==

与えられたネットワーク上での2 地点間最短路検索を最短路検索とよぶ．ネットワークデータへの前処理を含む，多くの問い合わせに高速に応答するための，データ構造とアルゴリズムの工夫を紹介する．

== 詳説 ==

== 参考文献 ==

利用者:Albeit-Kun/最短路検索

2009-11-07T06:24:21Z

Albeit-Kun: ページの白紙化

利用者:Albeit-Kun/最短路検索

2009-11-07T06:23:42Z

Albeit-Kun: 新しいページ: ''''【さいたんろけんさく（shotest path query）】''' == 概要 == 与えられたネットワーク上での2 地点間最短路検索を最短路検索とよぶ...'

利用者:Albeit-Kun

2009-11-07T06:23:29Z

Albeit-Kun: ページの白紙化

利用者:Albeit-Kun

2009-11-06T02:17:13Z

割引き

2008-11-14T00:55:57Z

Albeit-Kun:

'''【わりびき (discount)】'''

将来に発生する費用, 利得, 効用などを現在価値に評価する際に用いる操作. 例えば, 離散時間では割引き因子を <math>\beta \in [0, 1)\,</math> として, <math>n\,</math> (<math>= 0, 1, 2, \cdots\,</math>) 期後に発生する費用 <math>c\,</math> を現在価値 <math>\beta^{n} c\,</math> と評価する. 単に <math>\beta = 1/ (1 + \,</math>[無リスク利子率]<math> ) \, </math> とすることも多いが, 抽象的に, 意思決定者の時間選好, 異時点間の代替性のパラメータとみなすことも少なくない. 動的最適化を行う際の評価規範として, 割引きのある評価規範を用いることが多い.

[[category:確率と確率過程|わりびき]]

割当問題

2008-11-14T00:55:28Z

Albeit-Kun:

'''【わりあてもんだい (assignment problem)】'''

<math>|V^+| = |V^-|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\textstyle \sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

[[Category:グラフ･ネットワーク|わりあてもんだい]]

割当て市場ゲーム

2008-11-14T00:55:02Z

Albeit-Kun:

'''【わりあてしじょうげーむ (assignment game)】'''

プレイヤーが売り手と買い手の2つの集合に分割され, 売り手が初期財として1つの非分割財を保有し, 買い手は1つの財のみ欲するような市場ゲーム. 各提携の特性関数の値は,その提携における割当て問題の最適解で与えられる. 割当て市場ゲームのコアは, 全員提携の割当て問題に相当する線形計画問題の双対問題の解で与えられる.

[[category:ゲーム理論|わりあてしじょうげーむ]]

ワグナー・ウィッティンモデル

2008-11-14T00:54:38Z

Albeit-Kun:

'''【わぐなーうぃってぃんもでる (Wagner-Whitin model)】'''

動的ロットサイズ決定問題のこと.
在庫管理のモデルの一種で, 各期の需要は確定的に既知であるが必ずしも一定でない場合を考える. すなわち, 計画期間<math>T\,</math>中の各期<math>t\,</math>の需要を<math>d_{t}\,</math>, 製品1個あたりの発注費用を<math>c_{t}\,</math>, 発注量に無関係に必要な発注費用を<math>K_{t}\,</math>, 製品1個の1期間あたりの在庫維持費用<math>h_{t}\,</math>が所与のとき, 計画期間の開始時の在庫が0として, 総費用を最小化するような各期の発注量を求める問題.

詳しくは[[《動的ロットサイズ決定問題》|基礎編：動的ロットサイズ決定問題]]を参照.

[[category:生産・在庫・ロジスティクス|わぐなーうぃってぃんもでる]]

論理推論

2008-11-14T00:53:52Z

Albeit-Kun:

'''【ろんりすいろん (logical inference)】'''

記号論理を用いた推論のこと. 公理と推論規則, およびそれらから導出される(つまり証明される)定理のみによって推論が行われる. 各記号論理体系ごとに推論規則が存在するが, 例えば一階述語論理ではモーダスポーネンス(2つの任意の論理式とこれら論理式間の関係が与えられたとき, ある論理式から他方を導く推論規則)が唯一の推論規則である.

[[category:近似・知能・感覚的手法|ろんりすいろん]]

ロボティックセルスケジューリング

2008-11-14T00:53:28Z

Albeit-Kun:

'''【ろぼてぃっくせるすけじゅーりんぐ (robotic cell scheduling)】'''

数台のマシニングセンタと機械間のジョブ搬送を行う1台のロボットからなる小規模のFMSをロボティックセル(またはFMS)という. ロボティックセルにおいては機械間の仕掛け用バッファを置かない場合が多いので, 処理順序とともにロボットによるジョブ搬送経路も最適化することが求められる.

[[Category:スケジューリング|ろぼてぃっくせるすけじゅーりんぐ]]

ロバース数

2008-11-14T00:52:47Z

Albeit-Kun:

'''【ろばーすすう (Lovász number)】'''

与えられた無向グラフ<math>G\,</math>に対して定義される数値 (<math>\vartheta (G)\,</math>と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. <math>G\,</math>のクリーク数<math>w(G)\,</math>と彩色数<math>\chi (G)\,</math>に対し, <math>w(G) \leq \vartheta (\overline{G}) \leq \chi (G)\,</math> が成り立つ事が知られている, ただし <math>\overline{G}\,</math> は<math>G\,</math>の補グラフである.<math>w(G), \chi (G)\,</math> を求めるのはNP困難であるのに対し, <math>\vartheta (\overline{G})\,</math>は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.

[[Category:組合せ最適化|ろばーすすう]]

ロジットモデル

2008-11-14T00:51:29Z

Albeit-Kun:

'''【ろじっともでる (logit model)】'''

非集計行動モデルの中でもっとも広く利用されているモデル. 式の意味が理解しやすく, パラメータの推定も比較的に容易であり, 操作性に優れている. 効用関数の誤差項の確率分布としてガンベル分布を想定しており, 次の一般式が求められる. <math>\textstyle P_{in}={\mbox{exp}}(V_{in}) / \sum_{j=1}^{J_n}{\mbox{exp}}(V_{jn})\,</math>. ここで, <math>P_{in}\,</math>: 個人 <math>n\,</math> の選択肢 <math>i\,</math> の選択確率, <math>V_{in}\,</math>: 個人 <math>n\,</math> の選択肢 <math>i\,</math> の効用確定項, <math>J_n\,</math>: 個人 <math>n\,</math> の選択肢数.

[[category:予測|ろじっともでる]]

ロジスティックモデル

2008-11-14T00:50:54Z

Albeit-Kun:

'''【ろじすてぃっくもでる (logistic model)】'''

ロジスティックモデルは, 生態学モデルの中で最も単純な1種の個体群の時間変化を記述したモデルである. <math>N\,</math>を時刻<math>t\,</math>における個体数として, <math>N=k/(1+m \mbox {e}^{-\lambda t})\,</math>と表現する. ここで, <math>k\,</math>は飽和個体数であり, <math>\lambda\,</math>は定数である. ロジスティックモデルは, 生態学にとどまらず, 人口の増加過程, 新製品の普及過程など様々な社会的現象, ソフトウェア信頼度成長モデルなどの工学にも適用されている.

[[category:予測|ろじすてぃっくもでる]]

労働条件

2008-11-14T00:49:58Z

Albeit-Kun:

'''【ろうどうじょうけん (working condition)】'''

労働者の労働条件は, 労働基本法を始めとする労働関係法規により規定されている事項, 労使間で合意した就業規則, すでに慣行となっている事項に基づいて決めるもので, 職務内容, 労働時間, 賃金, 休日・休暇などが要素として含まれる. より良い労働条件を確立することで, 労働者の働く意欲を高め, ひいては組織の存続・成長につなげることができる.

[[category:企画・開発・プロジェクト・品質・ヒューマン|ろうどうじょうけん]]

連続時間ロットスケジューリング

2008-11-14T00:49:33Z

Albeit-Kun:

'''【れんぞくじかんろっとすけじゅーりんぐ (continuous time lot scheduling)】'''

各品種が一定の需要速度をもつとき, それら品種の製造連を連続時間軸上に割り付ける問題である. 生産速度が有限だと品種間に生産時期の干渉が起こり, 在庫量の時間変化が複雑となる. このため, 基本サイクリックスケジューリング方式を除いて, 問題は一般にNP困難である.

[[category:生産・在庫・ロジスティクス|れんぞくじかんろっとすけじゅーりんぐ]]

連続最適化問題

2008-11-14T00:49:11Z

Albeit-Kun:

'''【れんぞくさいてきかもんだい (continuous optimization problem)】'''

最適化問題(数理計画問題)

<table align="center">
<tr>
<td><math>\mbox{max.} \,</math></td>
<td><math>f(x) ( \,</math>あるいは, <math>\mbox{min.} \; f(x) ) \, </math> </td>
</tr>
<tr>
<td><math>\mbox{s.t.} \,</math> </td>
<td><math>x = (x_1,x_2,\ldots,x_n) \in F, \,</math> </td>
</tr>
</table>

において, 実行可能集合 <math>F\,</math> が連続関数 <math>g_i\,</math> <math>(i=1,2,\ldots,m)\,</math> と開集合 <math>S\,</math> を用いて,

<center>
<math>F = \{ x \in S : g_i(x) \leq 0 \ (i=1,2,\ldots,m) \} \, </math>
</center>

の様に表現され, 変数ベクトル <math>x\,</math> が実数値をとる問題.

[[Category:線形計画|れんぞくさいてきかもんだい]]

連続型分布

2008-11-14T00:48:44Z

Albeit-Kun:

'''【れんぞくがたぶんぷ (continuous distribution)】'''

累積分布関数が連続な分布.
累積分布関数が微分可能な場合には, その導関数を確率密度関数，あるいは単に密度関数，と呼ぶ. 確率密度関数をもつ分布のことを絶対連続型分布, あるいは単に連続型分布と呼ぶこともある.
連続型分布の代表的な例として, 正規分布, 指数分布, ガンマ分布, ベータ分布, <math>t</math>-分布, コーシー分布などがある.

[[category:確率と確率過程|れんぞくがたぶんぷ]]

連続型シミュレーション言語

2008-11-14T00:48:21Z

Albeit-Kun:

'''【れんぞくがたしみゅれーしょんげんご (continuous simulation language)】'''

微分方程式で記述されるモデルのシミュレーション専用の[[シミュレーションソフトウェア|コンピュータ言語]]のこと. CSSLやACSLが代表例としてあげられる.ルンゲ・クッタ(Runge-Kutta)法で微分方程式の初期値問題を解く機能が提供される. 連続型シミュレーションにおける時間の進め方は, 時間の刻み幅を定める単位時間(量子時間)制御方式であり, 短期的には等間隔で時間が進められる.刻み幅はユーザーの指定する精度に応じてアルゴリズムによって自動的に調整される.

[[category:シミュレーション|れんぞくがたしみゅれーしょんげんご]]

連続型シミュレーション

2008-11-14T00:47:58Z

Albeit-Kun:

'''【れんぞくがたしみゅれーしょん (continuous simulation)】'''

微分方程式系で規定されるシステムの[[シミュレーション]]のこと.ルンゲ・クッタ(Runge-Kutta)法等で微分方程式の初期値問題を解くことに相当する. 連続型シミュレーションは一連の静止画像を見て, あたかも連続的な動きをしているかのように感じる映画の原理と同じで,微小な時間の刻み幅を定め, 刻み幅にしたがってシステムの状態を更新することによってシミュレーションを進める.物理現象等, 理工学分野の応用例が多い.

[[category:シミュレーション|れんぞくがたしみゅれーしょん]]

連結度増大問題

2008-11-14T00:47:35Z

Albeit-Kun:

'''【れんけつどぞうだいもんだい (connectivity augmentation problem)】'''

与えられた無向(有向)グラフの辺連結度, あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題である. この問題は一般にはNP困難であるが, 付加辺の本数を最小にする場合には, 以下の問題に対して多項式時間の解法が知られている. %無向グラフの各点対間の局所辺連結度をそれぞれの目標値まで上げる問題, 無向(有向)グラフの辺連結度を目標値まで上げる問題, 無向グラフの点連結度を4以下の目標値に上げる問題, 有向グラフの点連結度を1だけ上げる問題.

[[Category:グラフ･ネットワーク|れんけつどぞうだいもんだい]]

連結度 (グラフの)

2008-11-14T00:47:11Z

Albeit-Kun:

'''【れんけつど (connectivity of graph)】'''

=== 概要 ===
無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.

=== 詳説 ===
　無向グラフ<math>G=(V,E)\, </math>において，<math>V\, </math>上の二項関係<math>R_1\, </math>を2点<math>u\, </math>と<math>v\, </math>の間に路が存在するとき<math>uR_1 v\, </math>と定めると<math>R_1\, </math>は同値関係となる．<math>R_1\, </math>による各同値類の誘導する部分グラフは連結成分 (component) と呼ばれる．また，<math>e\, </math>上の二項関係<math>R_2\, </math>を2本の辺<math>e\, </math>と<math>e'\, </math>を通る閉路が存在するとき<math>eR_2 e'\, </math>と定めると<math>R_2\, </math>は同値関係となる．<math>R_2\, </math>による各同値類の誘導する部分グラフは2連結成分(biconnected component) と呼ばれる．2つ以上の2連結成分に属する点は関節点 (articulation point) と呼ばれる (グラフからこの点を除くと非連結となる)．有向グラフ<math>G=(V,E)\, </math>において，<math>V\, </math>上の二項関係<math>R_3\, </math>を2点<math>u\, </math>と<math>v\, </math>の間に<math>u\, </math>から<math>v\, </math>への有向路と<math>v\, </math>から<math>u\, </math>への有向路とが存在するとき<math>uR_3 v\, </math>と定めると<math>R_3\, </math>は同値関係となる．<math>R_3\, </math>による各同値類の誘導する部分グラフは強連結成分 (strong component) と呼ばれる．無向(有向)グラフはそれ自体が１つの連結成分(強連結成分)であるとき連結 (connected)(強連結(strongly connected))であるという．

　無向 (有向) グラフの2点<math>s,t\, </math>に対し，<math>s\, </math>から<math>t\, </math>への辺素である (すなわち互いに辺を共有しない) 路の本数の最大値を<math>s,t\, </math>間の[[局所辺連結度]] (local edge connectivity) という．この値は，<math>s\, </math>から<math>t\, </math>への路をなくすために取り除くべき辺の本数の最小値に等しい(辺型のMengerの定理)．また，<math>s\, </math>から<math>t\, </math>への内素である(すなわち<math>s,t\, </math>以外では点を共有しない)路の本数の最大値を<math>s,t\, </math>間の[[局所点連結度]] (local vertex connectivity) という．この値は，<math>s\, </math>から<math>t\, </math>への辺が存在しないとき，<math>s\, </math>から<math>t\, </math>への路をなくすために取り除くべき<math>s,t\, </math>以外の点の個数の最小値に等しい(点型のMengerの定理)．

　無向(有向)グラフ<math>G\, </math>の辺の部分集合は，それを除去するとグラフが連結(強連結)でなくなるとき，辺カットという．<math>G\, </math>の点の部分集合は，それを除去するとグラフが2点以上をもち，かつ連結(強連結)でなくなるとき，点カットという．辺カット(点カット)の大きさの最小値を[[辺連結度]] (edge connectivity)([[点連結度]] (vertex connectivity))という．これらの値は辺(点)に重みが付いているときは重み和の最小値として定義することもある．辺連結度(点連結度)が<math>k\, </math>以上であるグラフを<math>k\, </math>辺連結(<math>k\, </math>点連結)であるという．重みなし無向グラフ<math>G=(V,E)\, </math>の点連結度<math>\kappa(G)\, </math>，辺連結度<math>\lambda(G)\, </math>，最小次数<math>\delta(G)\, </math>の間には，次の不等式が成り立つ．<math>\kappa(G)\leq \lambda(G)\leq \delta(G)\leq 2|E|/|V|\, </math>．

　グラフの辺連結度(点連結度)は全点対間の局所辺連結度(局所点連結度)の最小値に一致する．局所辺連結度や局所点連結度は，最大フロー・最小カット定理の特別な場合であるメンガーの定理により特徴づけされるので，これらの連結度(および連結度を決めている辺カットや点カットの１つ）はフローアルゴリズムをもちいて多項式時間で計算できる [3]．任意の無向グラフには２点間の局所辺連結度(局所点連結度)が一方の点の次数に等しい２点が存在し，そのような点対を線形時間で見つけることができる [8]．このような点対を繰り返し縮約していくことで辺連結度を容易に求めることもできる [9]．

　指定点<math>s\, </math>を持つ重みなし有向グラフに対し，<math>s\, </math>を含む点の真部分集合から残りの点の集合へ向かう有向辺の集合を<math>s\, </math>-カットと呼ぶとき，<math>s\, </math>-カットの大きさの最小値は，<math>s\, </math>を根とする有向全域出木(すなわち全域木に根から葉へ向かって辺に向きをつけたもの)の互いに辺素な集合の最大値に等しい(J.Edmondsの定理 [1] )．大きさ最小の<math>s\, </math>-カットを多項式時間で求めることができる．

　与えられた無向(有向)グラフの辺連結度，あるいは点連結度を指定された目標値まで大きくするためにグラフに最小費用の辺の集合を付加する問題を[[連結度増大問題]] (connectivity augmentation problem)と呼ぶ．この問題はNP困難であるが [2] ，付加辺の本数を最小にする場合には，以下の問題に対して多項式時間の解法が知られている．無向(有向)グラフの辺連結度を目標値まで上げる問題，無向グラフの点連結度を4以下の目標値に上げる問題，有向グラフの点連結度を１だけ上げる問題．

　無向(有向)グラフにおいて１つの点<math>s\, </math>を選び，<math>s\, </math>に接続する２本の (有向) 辺<math>(u,s),(s,v)\, </math>を1本の(有向)辺<math>(u,v)\, </math>に取り替える操作を辺分離という．このとき，次の[[辺分離定理]] (edge splitting theorem) が知られている．<math>s\, </math>に接続する２本の辺をうまく選ぶと辺分離後も，グラフの辺連結度(正確には<math>s\, </math>以外の２点間の局所辺連結度の最小値)を変化させずに保つことができる[5, 7]．特に，無向グラフに対しては(特殊な場合を除き)，辺分離後に<math>s\, </math>以外のすべての２点間の局所辺連結度を変化させない２本の辺の選択が存在する [6]．辺分離定理は連結度増大問題を解くアルゴリズムに使われている[4]．

----
'''参考文献'''

[1] J. Edmonds "Edge-disjoint branchings," ''Combinatorial Algorithms'', R. Rustin, eds., Algorithmics Press, New York (1973) 91-96.

[2] K. P. Eswaran and R. E. Tarjan, "Augmentation problems," ''SIAM Journal on Computing'', 5 (1976), 653-665.

[3] S. Even and R. E. Tarjan, "Network flow and testing graph connectivity," ''SIAM Journal on Computing'', '''4''' (1975), 507-518.

[4] A. Frank, "Augmenting graphs to meet edge-connectivity requirements," ''SIAM Journal on Discrete Mathematics'', '''5''' (1992), 25-53.

[5] L. Lovász, ''Combinatorial Problems and Exercises'', North-Holland 1979.

[6] W. Mader, "A reduction method for edge-connectivity in graphs," ''Ann. Discrete Math.'', 3 (1978), 145-164.

[7] W. Mader, "Konstruktion aller ''n''-fach kantenzusammenhängenden Digraphen," ''Europ. J. Combinatorics'', 3 (1982), 63-67.

[8] H. Nagamochi, "Graph algorithms for network connectivity problems," ''Journal of the Operations Research Society of Japan'', '''47''' (2004) , 199-223.

[9] H. Nagamochi and T. Ibaraki, "A linear-time algorithm for finding a sparse ''k''-connected spanning subgraph of a ''k''-connected graph," ''Algorithmica'', '''7''' (1992), 583-596.

[10] H. Nagamochi and T. Ibaraki, "Computing edge-connectivity in multigraphs and capacitated graphs," ''SIAM Journal on Discrete Mathematics'', '''5''' (1992), 54-66.

[11] アルゴリズムデータベース　http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/

[[Category:グラフ･ネットワーク|れんけつど]]

[[Category:組合せ最適化|れんけつど]]

連関図法

2008-11-14T00:46:34Z

Albeit-Kun:

'''【れんかんずほう (relation diagram)】'''

新QC七つ道具の1つで, 原因-結果, 目的-手段などが絡み合った問題について, その関係を論理的につないでいくことによって問題を解明する手法である. 原因や結果, 目的や手段などを1項目ずつカードに書き, それらの関係を矢線で結び, それらの関係を明確にする目的で作成する.

[[category:企画・開発・プロジェクト・品質・ヒューマン|れんかんずほう]]

レベル (計算幾何における)

2008-11-14T00:46:12Z

Albeit-Kun:

'''【れべる (level)】'''

<math>d\,</math>次元超平面アレンジメントにおいて, <math>x_d\,</math>軸に平行な直線で貫いたときに下から <math>k\,</math>番目となる交点をもつフェイス全体の集合を, <math>k\,</math>-レベル, または単にレベルという. 2次元の場合, 高々<math>k\,</math>までのレベルのサイズは<math>{\rm O}(kn)\,</math>であり, <math>k\,</math>-レベルのサイズは<math>{\rm O}(\sqrt{k}n)\,</math>となる. 双対性より, これは平面の<math>n\,</math> 点を直線で等分割する方法の数が<math>{\rm O}(n^{1.5})\,</math>であることも意味する. <math>k\,</math>-レベルを<math>{\rm O}(\sqrt{k}n(\log n)^2)\,</math>時間で求める平面走査法アルゴリズムが知られている.

[[Category:計算幾何|れべる]]

レバレッジ

2008-11-14T00:45:47Z

Albeit-Kun:

'''【ればれっじ (leverage)】'''

以下の状態をレバレッジ効果という.

:(1) 自己資産を担保にして資金を借り入れることにより, もとの資産より大きなポジションを取ること.

:(2) オプションや先物などを利用することで, 現物を保有するより低い費用で, 現物を保有しているときと同等のポジションを構築すること.

[[category:ファイナンス|ればれっじ]]

劣モジュラフロー問題

2008-11-14T00:45:26Z

Albeit-Kun:

'''【れつもじゅらふろーもんだい (submodular flow problem)】'''

劣モジュラフロー問題は, 最小費用フロー問題や共通マトロイド問題といった効率的に解くことのできる離散最適化問題の多くを含んだ広範な枠組である. 劣モジュラ関数の最小化を行う効率的な手続きの存在を仮定した上で, 最小費用フロー問題に関するアルゴリズムの拡張に当たる組合せ的な解法が開発されている.

[[Category:グラフ･ネットワーク|れつもじゅらふろーもんだい]]

劣モジュラシステム

2008-11-14T00:45:04Z

Albeit-Kun:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>\mathcal{D}\subseteq 2^{N}\,</math> に関して, <math>\emptyset,N\in \mathcal{D}\,</math> かつ <math>X,Y\in\mathcal{D}\Rightarrow X\cup Y, X\cap Y\in{\mathcal D}\,</math> が成り立つものとする. このとき, <math>{\mathcal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\mathcal D}\to{\mathbf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>(\mathcal{D},f)\,</math> を劣モジュラシステムという.

[[Category:グラフ･ネットワーク|れつもじゅらしすてむ]]

劣モジュラ関数

2008-11-14T00:44:30Z

Albeit-Kun:

'''【れつもじゅらかんすう (submodular function)】'''

分配束 <math>{\mathcal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\mathcal D}\,</math> に対して

<center>
<math>f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)</math>
</center>

を満たすとき, <math>f\,</math> を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.

[[Category:グラフ･ネットワーク|れつもじゅらかんすう]]

劣勾配法

2008-11-14T00:44:03Z

Albeit-Kun:

'''【れつこうばいほう (subgradient method)】'''

微分不可能な関数における非線形最適化手法の1つ. 最適解に近づくように, 解を改善する方向ベクトル(劣勾配)と, その方向に移動する距離とを求め, これを繰り返しながら解を改善する. 組合せ最適化問題(最小化とする)において, ラグランジュ緩和問題が簡単に解けるような場合には, 適切なラグランジュ乗数を決定する問題が, (微分不可能な)区分線形関数の最大値を求める問題になることから, よりよい下界値を求めるときに常套的に用いられる.

[[Category:組合せ最適化|れつこうばいほう]]

劣勾配

2008-11-14T00:43:39Z

Albeit-Kun:

'''【れつこうばい (subgradient)】'''

真凸関数 <math>f: {\mathbf R}^n \to (-\infty,+\infty)\,</math> に対して, 次式を満足するベクトル <math>\xi \in {\mathbf R}^n\,</math> を <math>f\,</math> の <math>x\,</math> における劣勾配といい, 劣勾配全体の集合を <math>\partial f(x)\,</math> と表す.

<center>
<math>f(y) \ge f(x) + \xi^{\top}(y-x) \quad\quad \forall \, y \in {\mathbf R}^n</math>
</center>

真凸関数はその実効定義域 <math>\mbox{dom} \, f := \{ x \, | \, f(x) < \infty \}\,</math> の任意の相対的内点において, 少なくとも1つの劣勾配をもつ. 特に, 凸関数 <math>f\,</math> が点 <math>x\,</math> において微分可能ならば, <math>f\,</math> の <math>x\,</math> における劣勾配は唯一存在し, 通常の勾配 <math>\nabla f(x)\,</math> に等しい.

[[Category:非線形計画|れつこうばい]]

列挙法

2008-11-14T00:43:16Z

Albeit-Kun:

'''【れっきょほう (enumerative method)】'''

組み合せ最適化問題や多段階決定問題などで, すべての可能な場合を列挙して最適解を求める方法. 全数列挙法(total enumeration method, brute force enumeration)ともいわれる. 分枝限定法の考え方の出発点である. 多段確率決定問題では1つの列挙法として決定樹表(ツリーテーブル)がある.

[[Category:動的・確率・多目的計画|れっきょほう]]

レオンティエフ逆行列

2008-11-14T00:42:51Z

Albeit-Kun:

'''【れおんてぃえふぎゃくぎょうれつ (Leontief inverse matrix)】'''

産業連関分析において, 産業の生産額を<math>X\,</math>, 投入係数表を<math>A\,</math>, 最終需要を<math>F\,</math>, 輸入を<math>M\,</math>とすれば, 生産と需要のバランスは<math>AX+F-M=X\,</math>となる. この式を<math>X\,</math>について解くと<math>X=(I-A)^{-1}(F-M)\,</math>と求められる. <math>I\,</math>は単位行列である. 行列<math>(I-A)^{-1}\,</math>をレオンティエフ逆行列と呼ぶ. この行列は逆行列が存在すれば<math>(I-A)^{-1} = I+A+A^2+\cdots\,</math>と展開することができる. 第1項は直接の需要の生産に, 第2項以降は波及的間接需要の生産に対応している.

[[category:公共システム|れおんてぃえふぎゃくぎょうれつ]]

レヴィー過程

2008-11-14T00:42:26Z

Albeit-Kun:

'''【れう゛ぃーかてい (Levy process) 】'''

実数値をとる連続時間[[確率過程]]<math>\{X(t)\}</math>が
独立かつ定常な増分をもつとき，
<math>\{X(t)\}</math>をレヴィー過程と呼ぶ．
例えば，[[ポアソン過程]]はレヴィー過程である．
一般に，
レヴィー過程は[[ブラウン運動]]と離散的にのみ変化するジャンプ過程の和として
表すことができる．

[[category:待ち行列|れう゛ぃーかてい]]

リンドレーの方程式

2008-11-14T00:42:00Z

Albeit-Kun:

'''【りんどれーのほうていしき (Lindley's equation)】'''

客の到着が再生過程にしたがう GI/G/1 モデルにおいて, 到着間隔分布とサービス時間分布をそれぞれ <math>F(t)\,</math>, <math>H(t)\,</math> と表すとき, 先着順サービスでの待ち時間の定常分布 <math>W(t)\,</math> に関する次の積分方程式をリンドレーの方程式という. ただし, <math>C(t)\,</math> は"サービス時間<math>-\,</math>到着間隔"を表す分布関数である.

<table align="center">
<tr>
<td rowspan="2"><math>W(t) =
\left\{
\begin{array}{l}
\\
\\
\\
\\
\end{array}
\right. \, </math></td>
<td><math>\int^{\infty}_{0-} C(t-x) \mbox{d} W(x) \, </math></td>
<td><math>(t \geq 0) \,</math></td>
</tr>
<tr>
<td><math>0 \, </math></td>
<td><math>(t < 0) \, </math></td>
</tr>
</table>

ただし, <math>\textstyle C(t)=\int^{\infty}_{x=0} H(t+x) \mathrm {d}F(x)\ \ \ -\infty < t < +\infty \,</math>である.

[[category:待ち行列|りんどれーのほうていしき]]