数理解析研究所講究録
第 1799 巻 2012 年 92-99

92

格子グラフ上の最短経路問題のための劣線形領域アルゴリズム
今井 達也 *

藤 哲郎 \dag er

野口 俊輔 \dag er

概要
本論文では，格子グラフ上の二頂点間の最短経路を頂点数$n$リズムについて述べる．提案アルゴリズムは，自然数パラメータよび$O(n \frac{2^{l}(l+2)}{2^{l+1}-1})$の劣線形サイズの作業領域で求めるアルゴ
$l$

をとって，

$O(n^{\frac{2^{l}}{2+1-1}})$の空間計算量，おの時間計算量で動作する．

1 序論
グラフの最短経路問題は数多くの応用を持っ非常に重要な問題の一つである．これまでに，理論的なもの
や汎用的なものから，問題固有の性質を利用したヒューリスティックなものまで，数多くの最短経路アルゴ
リズムが提案されてきた．

近年では社会の複雑化に伴って，より巨大なグラフに対する最短経路問題の解決が求められるようになってきている．しかし，巨大なグラフに対する最短経路問題を実際に計算機の上で解くためには，グラフの大きさに伴った多くのメモリが必要になる．これまでに提案されてきた最短経路アルゴリズムはグラフの頂点数に比例する空間計算量を必要とするものが多く，劣線形領域のアルゴリズムはほとんど知られていな
い．そのような中にあって，Asano と Doeff は格子グラフに対する劣線形領域の最短経路アルゴリズムを提案した [1]. このアルゴリズムは，自然数パラメータ をとり，グラフの頂点数 に対して入カグラフや得られた最短経路を表すために使用される領域を除いて 1,
$l$

$n$

$o(n^{\iota_{l}} \neq\frac{1}{+1})$の空間計算量，および$O(n^{2+_{f}^{l}-\frac{l(l+1)}{4(2l+1)}})$の時間計算量で動作するアルゴリズムである．

本研究では，Asano らのアルゴリズムを元に，同じく自然数パラメータ をとって，$l$

計算量，および$O(n) \frac{2^{l}(l+2)}{z^{l+1}-1}$$O(n \frac{2^{l}}{2^{l}+\iota-1})$の空間の時間計算量を持っ最短経路アルゴリズムを提案した．以下，Asano らのアル

ゴリズム，我々のアルゴリズムの順に，その詳細を述べていく．なお以降の全ての議論では，入力される格子グラフが正方形状であることと，辺のコストが全て有限の正の値であること，始点が格子グラフの左下
端，終点が右上端の頂点であることを仮定して話を進めていく．これらの仮定は [1] で述べられている方法
によって容易に緩和できるが，本論文ではその方法については言及しない．

2 Asano, Doerr の非再帰版省メモリ最短経路アルゴリズム
Asano らのアルゴリズムは，Dijkstra 法 [2] などと同様に，始点から各頂点までの最短距離を計算していき，それを利用して始点から終点への最短経路を求めるアルゴリズムである．このアルゴリズムは，特定の$\dagger$

東京工業大学大学院情報理工学研究科数理・計算科学専攻
東京工業大学理学部情報科学科

1 入力が書き込み不可能なメモリに保存されている場合や，入力が，格子グラフの縦横の頂点数と，辺を与えるとそのコストを返す関数の対によって与えられている場合などを想定している．また，出力に関しては，最短経路が通過する頂点を順次画面に書き出して捨ててしまうような場合を想定している．

93
頂点への最短距離だけを覚えておくことによって使用メモリの削減を達成した．より具体的には，最短距離が保存される頂点は，自然数パラメータに基づいて図 1 のように個に分割された小格子グラフ$(S[1], \cdots,S[k^{2}])$ のふち部分の頂点 (黒丸で表された頂点) である．以降は黒丸の頂点を境界頂点と呼ぶ．
境界頂点は複数の小格子グラフに含まれる場合がある．
$k\in \mathcal{N}$$k^{2}$

以下，始点からの最短距離を求める部分と最短経路を求める部分とに分けてアルゴリズムを解説する．

2.1 最短距離を求めるアルゴリズム
入力された格子グラフを $G=(V, E)$ , 始点を $s\in V$ , グラフの一辺の分割数を$k\in \mathcal{N}$とおく．また，頂点 $v\in V$ から頂点 $v’\in V$

への最短距離を $d(v,v’)$ とおく．

このアルゴリズムはまず， から各境界頂点への最短距離 (の上を保存する配列を用意し，各要素を十分大きな数で初期化す
$s$

界

$C$

$)$

る $(C[s]$ は $0)$

. 次に$k^{2}$

個の小格子グラフそれぞれに対して，小格子グラフの各境界頂点を始点とする多始点最短経路アルゴリズムを走らせる．使用する多始点最短経路アルゴリズムは Dijkstra 法の応用であり，厳密には次の手順で行われる．まず始めに Dijkstra 法と

図 1:$k^{2}$個に分割された格子グラフ(太線は最短経路の一例)

同様に，小格子グラフに含まれる各頂点への最短距離を保存する配列 $T$ を用意し，各要素を十分大きな数で初期化する．次に，始点，すなわち対象としている小格子グラフの各境界頂点の $T$ の値を $C$ の値で置き換える．後は Dijkstra 法の前半部分と同様に，最も小さな未確定の最短距離を持つ頂点を一つ選び，その頂点の最短距離を確定，隣接頂点に距離を伝搬する，という処理を頂点の個数だけ繰り返す．全ての頂点への最短距離が求まったら，最後に各境界頂点の の値を に書き入れる． 個のグラフに対して上記のアルゴリズムを走らせるこの処理を走査と呼ぶ．また本論文では走査
中の各小格子グラフに対する上記の処理を多始点版 Dijkstra 法と呼ぶこととする．各走査の際の小格子グ
ラフの選択順序に依らず，回数が高々境界頂点の個数に達するまで走査を繰り返すと， に各境界頂点へ
$C$

$T$

$k^{2}$$C$の最短距離が正しく定まる．
このアルゴリズムの擬似コードを Algonthml に示す．なお，boundary $(G)$ は格子グラフ $G$ のふち部分の頂点の集合を表す．また，Dijkstra-distance $(G,T)$ は，格子グラフ$G$に対して Dijkstra 法の前半部分を走らせる処理である． は最短距離の上界を保存するための既に初期化された配列である．
$T$$Algorithm11\cdot\forall v\in\bigcup_{i}$最短距離を S 求] めるアルゴリズム$2:C[s]arrow 0$ ;3: for 1, ...,

boundary(S[i])l do
do$\forallv\in
V(S[j]),$$T[v]arrow\infty$
5:;
6:
boundary $(Sb]),$ $T[v]arrow C[v]$ ;7:
Dijkstra-distance;8:
v boundary $(S[j]),$ $C[v]arrow T[v]$ ;9;end for
10: end for
11: retum $C$ ;4:$| \bigcup_{i}$for $jarrow 1,$$k^{2}$$\ldots,$$\forall v\in$$(S\triangleright], T)$$\forall$$\in$$AD_{-}distance(G,s,k)$94
このアルゴリズムの正しさは次の理由からなる．まず，任意の境界頂点 について，入カグラフに対する仮定より明らかに， から までの最短経路が少なくとも一っ存在する．議論を簡単にするため，ここではそれぞれの境界頂点への最短経路は一っずっしかないと仮定しよう． から への最短経路と各格子$C[v_{i}]=d(s,v_{i})$ か$v_{t}(v_{0}=s, v_{t}=v)$ とすると，グラフの境界頂点の交点を から近い順に
$v$

$v$

$s$

$v$

$s$

$s$

$v_{0},$ $v_{1},$ $v_{2},$$\ldots,$の両方を含む小格子グラフに対して多始点版 Dijkstra 法を走らせのとき， と$C[v_{i+1}]=d(s,v_{i+1})$
れば，となる．全ての境界頂点への最短距離がまだ求まっていない場合，上記の との関係にある頂点が必ず一つ以上存在する．よって走査の中で多始点版 Dijkstra 法を走らせる小格子
つ $C[v_{i+1}]>d(s, v_{i+1})$$v_{i}$$v_{i+1}$$v_{i}$$v_{i+1}$

グラフの順序に依らず，走査を行うたびに少なくとも一つの頂点の最短距離が新たに求まる．従って高々境界頂点の個数だけ走査を行えば全ての境界頂点への最短距離が $C$ に定められる．

本節の最後に，各多始点 Dijkstra 法では力任せの方法で次に値を決定する頂点を探すものとして，このア
ルゴリズムの計算量を求める．このアルゴリズムの時間計算量は，アルゴリズムの定義より，走査の時間計
算量の境界頂点数倍である．多始点版 Dijkstra 法の時間計算量は Dijkstra 法と同等であるため，各小格子グ
ラフに $O(n/k^{2})$ 個の頂点が存在することから，多始点版 Dijkstra 法の時間計算量は $O(n^{2}/k^{4})$ である．よって，一回の走査の時間計算量は$O(n^{2}/k^{2})$である．各小格子グラフには$O(\sqrt{n}/k)$個の境界頂点が含まれ，グラフ全体の境界頂点の数は $O(k\sqrt{n})$ であるので，このアルゴリズム全体の時間計算量は $O(n^{2}\sqrt{n}/k)$ となる．また，配列
間計算量は

$C$

の要素数は $O(k\sqrt{n}),$$O(k\sqrt{n}+n/k^{2})$$T$の要素数は $O(n/k^{2})$ であることから，このアルゴリズムの空となる．

使用メモリの削減に主眼をおく場合，空間計算量を最小化する$k=n^{1/6}$$k$を$k^{*}$とおくと，$k^{*}=\Theta(n^{1/6})$となる．

を代入すると空間計算量は $O(n^{2/3})$ となり，時間計算量は $O(n^{2+1/3})$ となる．

2.2 最短経路を出力するアルゴリズム$G=(V, E),$ $s\in V,$$k\in \mathcal{N},$ $d$$G,$ $s,k$ の他に終点 $t\in V$ を入力とする．
は 21 節と同様に定義し，このアルゴリズムは， から$s$に対して， から
$v_{t}$$v_{t-1}$$t$

へのある最短経路上のいくつかの境界頂点への最短経路，$v_{t-1}$

から $v_{t-2}$ への最短経路，
．
．
．
， から
$v_{1}$

界頂点の間の最短経路を順に出力していくアルゴリズムである． から$t$き，$v_{i-1}$$v_{0},v_{1},$ $\ldots,$$v_{i}$$v_{0}$$v_{t}(v_{0}=s, v_{t}=t)$への最短経路，と境までの経路が出力されていると$v_{i-l}$ は，の決定，および， から $v_{i-1}$ への最短経路の出力は次のようにして行われる．まず，$v_{i}$

を満たし， を含むいずれかの小格子グラフに含まれていなければならない．よって，このアルゴリズムはまず， を含む各小格子グラフの境界頂点 に関して $d(s,v)$ を計算す

$d(s,v_{i-1})+d(v_{i},v_{i-1})=d(s, v_{i})$$v_{i}$$v$$v_{i}$

るために，AD-distance $(G, s, k)$ を走らせる．次に，$d(v_{i},v)$

対して
きい

$v$

$v_{i}$

を計算するために$v_{i}$

を含む各小格子グラフにを始点として Dijkstra 法の前半部分を走らせる．そして上記の式を満たす中で $d(v_{i}, v)$ が最も大を $v_{i-1}$ に定め，Dijkstra 法と同様のやり方で力される経路の向きを考えて，$d(v_{i},v)$$v_{i}$から $v_{i-1}$ への最短経路を出力する．このとき，出を求める際に計算した値を捨てて最短距離の計算もやり直さなければならない．

以上をまとめ，このアルゴリズムの疑似コードを Algonthm2 に示す．ただし，Dijkstra$(G, s,t)$ はグラ
フ $G$ の頂点 $s\in V(G)$ から $t\in V(G)$ への最短経路を Dijkstra 法に基づいて出力するサブルーチンである．

用いられる配列およびその要素数は ADldi-stance と同じであることから，このアルゴリズムの空間計算量は $O(k\sqrt{n}+n/k^{2})$ であり， を代入するとこの式は $O(n^{2/3})$ となる．また，時間計算量 $O(n^{2}\sqrt{n}/k)$ の$k^{*}$

AD-distance および$O(n^{2}/k^{4})$リズムの時間計算量は$k$の Dijkstra-distance, Dijkstra を高々 $O(k\sqrt{n})$ 回繰り返すため，このアルゴによらず $O(n^{3})$ である．

95

:owrhitihlemt2$Alg1$

最短経路を出力するアルゴリズム $AD_{-}path(G, s,t, k)$$\neq$

2:

C

3:

for t

$arrow$

AD-distance $(G, s, k)$ ;$\in$boundary(S[i]) を満たす do$i$塗$\forall v\in V(S[i]),$ $T[v]arrow\infty;T[v]=0$

5:

Dijkstra.distance $(S[i], T)$ ;if $C[v’]+T[v’]=C[t]$ を満たす

丘

7:

$Varrow$8:$jarrow i$

上記

$v’$

$\in$

;

boundary $(S[i])$ が存在する ffien
boundary $(S[i])$ の中で $T[v’]$ が最も大きい ;$v^{l}\in$

$v’$

;

end if
IO:
end for11:
Dijkstra $(S[j], v,t)$ ;$tarrow v$ ;12:
13: end while
9:3 提案アルゴリズム
2 節のアルゴリズムでは，境界頂点への最短経路を記憶する配列と，小格子グラフーつ分の頂点数と等しいサイズの作業領域だけを使用することによって，空間計算量が削減されている．Asano らは [1] において，
2 節のアルゴリズムに加え，AD-distance で使われている Dijkstra.distance の代わりに再帰的に Asano らのアルゴリズムを適用することで，作業領域を更に削減し，より少ないメモリで最短距離を求めるアルゴ
リズムを提案した．

この先行研究を基に，我々は次の改善を行うことによって Asano らのアルゴリズムよりも時間・空間計
算量の効率が良い最短経路アルゴリズムを提案した．

.
.

非再帰のアルゴリズムの時間計算量を改善．

再帰時の格子グラフの分割方法を改善．

以下，それぞれのアルゴリズムを順に解説する．

3.1 高速に最短距離を求めるアルゴリズム
Asano らの始点から各境界頂点への最短距離を求めるアルゴリズムは，Dijkst-ra 法と同様に始点からの最短距離が短い順に最短距離を定めていくことによって高速化することができる．より正確には，最初に始点から始点への最短距離を 0 で初期化し，
1. 始点からの最短距離が未確定の境界頂点のうち最小のもの$v_{\min}$を探す．始点から$v_{m}in$への最短距離は現在の値で確定する．

2.

を含む全ての小格子グラフに対して多始点版 $Dijk_{S}ffa$ 法を適用し，それらの小格子グラフに含まれる境界頂点への最短距離を更新する．

$v_{mn}i$という処理を境界頂点の個数だけ繰り返すことによって，Asano らのアルゴリズムよりも高速に始点から各境界頂点までの最短距離を正しく求めることができる．このアルゴリズムの擬似コードを Al-gonffim 3 に示す．

96
Algoni$h$

3 より高速に最短距離を求めるアルゴリズム $(G, s,k)$boundary(S[i]), $C[v]arrow\infty;C[s]arrow 0$ ;boundary(S[i]), $D[v]arrow$ false;2:
boundary $(S[i])|$ do
3: for 1, ...,
$v_{\min}arrow
D[v]=$
bomdary $(S[i])$ の中で $C[v]$ が最小のもの;
4:
false を満たす
1:$\forall v\in\bigcup_{i}$$\forall v\in\bigcup_{t}$$| \bigcup_{i}$$v \in\bigcup_{i}$

true;

5:

$D[v_{\min}]arrow$

6:

for $j\in$ { $i|v_{\min}\in$ boundary $(S[i])$ } do

7:$\forall v\in V(sb]),T[v]arrow\infty$

8:$\forall v\in$

9:

10:

;

boundary $(Sb]),$ $T[v]arrow C[v]$ ;Dijkstra.distance $(Sb],T)$ ;boundary $(Sb]),$ $C[v]arrow T[v]$ ;$\forall v\in$end for
12: end for
13: retum $C$ ;11:

正しさの証明このアルゴリズムの正しさは Dijkstra 法と同様に証明できる．境界頂点の中で，始点からの最短距離が 1 番

とおく．最短経路の性質より明らかに，始点からの両方を含む小格のうちのいずれかの頂点 VpreV への最短経路に，Vprev とへの最短経路は，から子グラフだけを通るような Vprev
への最短経路を付け加えたものである．よって，擬似コードのに回目の)Lx– プにおいて $(j=1, \ldots,i)$ ,が選ばれ，5 行目に到達した時点で $C[v_{\min}]=d(s,v_{\min})$には $d(s,v_{i+1})$ が保持されておとなっていたならば，$(i+1)$ 回目のループの頭に到達した時点で，目から $(i+1)$ 番目に短い頂点をそれぞれ$v_{1},$$\ldots,$$v_{1},$$v_{i+1}$$\ldots,$ $v_{i+1}$$v_{i+1}$$v_{i}$$i$$v_{i+1}$$v_{\min}$$v_{j}$$C[v_{i+1}]$

り，5 行目では$v_{\min}$に $v_{i+1}$ が選ばれる．

計算量$k=k^{*}$ のこのアルゴリズムの空間計算量は Asano らのアルゴリズムと同じく $O(k\sqrt{n}+n/k^{2})$ であり，ときには $O(n^{2/3})$ となる．また，本アルゴリズムのループの各段階と多始点 Dijkstra 法のそれぞれにおいて，最小要素の探索を力任せに行う場合，このアルゴリズムの時間計算量は $O(k\sqrt{n}\cross(k\sqrt{n}+n^{2}/k^{4}))$ で$k=k^{*}$ のときは第二項が支配的になり，時間計算量はとなる．
ある．
$O(n^{2})$3.2 Asano らの再帰アルゴリズムおよび分割方法の改善
入力された格子グラフを $G=(V, E)$ , 始点を $s\in V$ とおく．Asano らの再帰アルゴリズムにおいて，格子グラフの分割はパラメータ $k,$ $l\in N$ によって図 2 のように行う．まず $G$ を$k^{2}$

個の小格子グラフに分割

し，これらを 1 段目の小格子グラフと呼ぶ．再帰アルゴリズムでは，1 段目の各小格子グラフに対する走査の中で，小格子グラフ (図 2 では右上のグラフ$S_{1}[2]$) に多始点版 Dijkst-ra 法を走らせる代わりに小格子グ

ラフを更に分割して 2 段目の小格子グラフ群 図では$($$S_{2}[1],$$\ldots,$$S_{2}[4])$を作り，再帰的に最短距離を求める

アルゴリズムを適用する．同様にして分割と最短距離アルゴリズムの適用を 回繰り返すと，1 段目から個ずっ作られる．段目の各小格子グラフに対して，21 節のアルゴリ
段目までの格子グラフがそれぞれズムと同様に境界頂点の個数と同じ回数だけ走査を繰り返すと，段目の元になった $(l-1)$ 段目のある小格$l$$k^{2}$

$l$

$l$

$l$

子グラフに対して多始点版 Dijkstra 法を走らせた場合と同じ結果が得られる．また，この操作を $(l-1)$ 段

97目の各格子グラフについて行うと，$(l-1)$ 段目の各小格子グラフに対する一回の走査に相当する結果が得られる．同様に，これらの処理を再帰的に行うことで 1 段目の各境界頂点までの からの最短距離が求まる．
$s$

頂点数瓦の格子グラフを$k^{2}$

個に分割して作られた $(i+1)$ 段目の小格子グラフ群に関して，各小格子グラフには点が存在し，$O(\sqrt{N_{i}}/k)$$O(N_{i}/k^{2})$個の頂個の境界頂点が含まれる．また，元の格子グラフ全体での境界頂点の数はとなる．頂点数$O(k\sqrt{N_{i}})$$N_{i}$の格子グラフに対する最短距離計算の時間計算量を鶉とおくと，という漸化式が成り立っ．アル$i<l\#$ こ

ついて $T_{i}=O((k\sqrt{N_{i}})\cross k^{2}\cross T_{i+1})$

ゴリズム全体の時間計算量 $T=T_{0}$ は，$T_{l}=O((n/k^{2l})^{2})$ より(1)$T=T_{0}=O(( \frac{n}{k^{2l}})^{2}\cross\prod_{i=1}^{l}(k^{2-i}\sqrt{n}\cross k^{2}))$となり，これをまとめると$n^{2}$$k^{\overline{4l}^{\cross k^{4l-\Sigma_{i=1}^{\iota}i}\cross(\sqrt{n})^{l}}}$$=n^{2+\frac{l}{2}}\cross k^{4l-\frac{l(l+1)}{2}-4l}$

図 2: $k=2,l=3$ のときの格子グラ(2)$=n^{2+\frac{\iota}{2}/k^{\frac{l(l+1)}{2}}}$フの分割例となる．また，多始点版 Dijkstra 法のために使用する領域と，再帰の各段で境界頂点への最短距離を保存するための領域が必要となるため，このアルゴリズムの空間計算量は(3)$O(k \sqrt \mathcal{H}+\sqrt n+\frac{\sqrt{n}}{k}+\ldots+\frac{\sqrt{n}}{k^{l-2}}+\frac{n}{k^{2l}})$となる．(3) 式は，例えば(3)で上界が与えられ，最適な分割数は
計算量は$o(n^{2+\frac{l}{2}-\frac{l(l+1)}{4(2l+1)}})$(4)$\leq k\sqrt{n}+2\sqrt{n}+\frac{n}{k^{2l}}$となる．このときの空間計算量は$\Theta(n\frac{1}{2(2l+1)})$$O(n^{\frac{l+1}{2l+1}})$

であり，時間となる．

Asano らのアルゴリズムでは全ての段で同じ分割数を用いているが，それぞれの段において頂点数に応じた適切な分割数を設定することで，同じ段数 に対して使用メモリをさらに削減できる．言い換えれば，同じ空間計算量を達成するために必要な段数が少なくなるため，時間計算量が改善される．
にいま，段目の分割数を島，段目から 段目までの合計の空間計算量を とおくと，各 $i=1,$
$l$

$i$

$i$

$l$

$S_{i}$$l$$\ldots,$

ついて $N_{i-1}=O(k_{i}^{2}N_{i}),$

数 ,
$n$

$S_{i-1}=O(k_{i}\sqrt{N_{i}}+S_{i})$So はアルゴリズム全体の空間計算量

ここで，数列$a_{i}$$S$となる．ただし，$N_{0}$

は入力された格子グラフ $G$ の頂点である．

を用いて $Si=O(N_{i}^{a}$ りと表すと，$i\leq l$ に関して
(5)

$S_{i-1}=O(k_{i}\sqrt{N_{i-1}}+(N_{i-1}/k_{i}^{2})^{a_{i}})$と表せる$(S_{l}$は $O(N_{l}))$. これを極で微分することで，$S_{i-1}$を最小化する$k_{i}^{*}= \Theta(N_{i}\frac{2_{0}i-1}{2(2a_{i}+1),-1})$,$k_{i}^{*}$とそのときの $S_{i-1}$ は(6)$\underline{2\alpha\cdot}$(7)$S_{i-1}=O(N_{i-1}^{2a_{i+1}})$となる．以上より得られた$a_{i}$の漸化式を解く 2 と $a_{i}=2^{l-i}/(2^{l-i+1}-1)$ .

るような分割を行う場合の 段目の分割数$i$$k_{i}^{*}$

よって，使用メモリが最小とな

は $N_{i-1}$ を用いて$\frac{k_{i}^{*}}{2}=\Theta(N_{i1}^{=\iota_{-\+}^{1}}2(2-1))$$a_{i}=1/A_{i}$とおくと $A_{i-1}=1+ \frac{1}{2}A_{i}$ という漸化式が得られるため，これを解けばよい．

(8)

98
となる．このときのアルゴリズム全体の空間計算量

$S$

は

(9)

$S=S_{0}=O(N_{0}^{a_{0}})=O(n^{\frac{2^{l}}{2^{l+1}-1}})$となる．

次に，同様にして時間計算量を求める． 段目の小格子グラフに対する時間計算量を鶉とおくと，各$i$. ただし，To はアルゴリズム全体の時間計算量と表すと， に関して

$i=1,\ldots,l$ に対して

$T_{i-1}=O((k_{i}^{2}\sqrt{N_{i}})\cross k^{\dot{2}}\cross T_{l})$る．ここで，数列を用いて $T_{i}=O(N_{i}^{b_{*}})$$b_{i}$$T$であ$i\leq l$(10)$T_{1-1}=O(k_{i}\sqrt{N_{i-1}}\cross k_{i}^{2}\cross(N_{i-1}/k^{2})^{b:})$. これに $k=k^{*}$ を代入して得られた の漸化式を解く 3 と $b_{i}=\{2^{l-i}(l-i+3)-$$1\}/(2^{l-i+1}-1)$ . よって，使用メモリが最小となるような分割を行う場合のアルゴリズム全体の時間計算となる$(T_{l}$は $O(N_{l}^{2}))$$b_{l}$

量 $T$ は

(11)

$T=T_{0}=O(N_{0}^{b\mathfrak{p}})=O(n \frac{2^{l}(l+3)-1}{2^{l+1}-1})$となる．

3.3 二つの改善を合わせたアルゴリズムの性能評価
本節では，32 節の分割手法を用いた再帰アルゴリズムの各段に対する計算を 31 節の高速アルゴリズム
で置き換えた場合の時間計算量を考える．
段目の小格子グラフに対する時間計算量を$i$$T_{i}$とおくと，分割の段数が であるとき，各 $i=1,\ldots,l$ に$l$となる．括弧内の第一項は値が未確定の最小要素を力任せに探$T_{l-1}=O(N_{l-1}^{2})$ .
すための時間である．3.1 節の議論などにより，
ここで，数列 を用いて対して $T_{i-1}=O(k_{i}^{2}\sqrt{N_{i}}\cross(k_{i}^{2}\sqrt{N_{i}}+T_{i}))$$T_{l}=O(N_{l}^{2}),$$T_{i}=O(N_{i}^{C_{\backslash }})$

$c_{i}$

と表すと，
(12)

$T_{1-1}=O(k_{i}\sqrt{N_{i-1}}(k_{i}\sqrt{N_{*-1}}+(N_{i-1}/k^{\dot{2}})^{c:}))$となる．

このアルゴリズムの空間計算量は明らかに前節のアルゴリズムと等しいこどから，$k_{i}=k_{i}^{*}$

算量は最適化される．そして，上式にのときに空間計を代入して第一項と第二項を比較すると，のとき第二項が支配的になることが分かる．ci は明らかに 1 よりも常に大きく，また $2^{l-i}/(2^{l-i+1}-1)\leq 1$であるため，$h=k_{i}^{*}$$c_{\dot{2}}\geq 2^{l-i}/(2^{l-i+1}-1)$$k_{i}=k_{i}^{*}$

のとき

(13)

$T_{i-1}=O(k_{*}^{*}\sqrt{N_{i-1}}\cross(N_{*-1}/k_{i}^{*2})^{c:})$となる．
得られた $q$ の漸化式を解く 4 と $c_{i}=2^{l-i}(l-i+2)/(2^{l-i+1}-1)$. よって，使用メモリが最小となるような分割を行う場合のアルゴリズム全体の時間計算量 $T$ は(14)$T=T_{0}=O(N_{0}^{co})=O(n^{\frac{2^{l}(l+2)}{2^{\iota}+1_{-1}}})$となる．式 (11) を変形すると，(15)$T=O(n \frac{2^{l}(l+2)}{2^{\iota+1-1}}+_{2}\urcorner\frac{2^{\iota}-1}{+1-1})$となることから，このアルゴリズムは再帰の分割方法を変えただけのアルゴリズムよりも$O(n^{\frac{2^{l}-1}{2+1-1}})$速である．

図 3 は，Asano らのアルゴリズムと我々の提案アルゴリズムの計算量とパラメータの関係を表す．
$3l-i/(2^{l-:+1}-1)$ とおくと $B_{:-1}=B_{l}+1+1/2^{l-i+1}$ という漸化式が得られるためこれを解けばよい．
$4_{\alpha=2^{\iota-i}C_{i}}/(2^{l-i+1}-1)$とおくと $Ci- l=C_{i}+1$ という漸化式が得られるためこれを解けばよい．

倍高99
AD は Asano らの最短距離を求める再帰アルゴリズ

ム，32 は 32 節の分割数だけを改善したアルゴリズム，
33 は本節のアルゴリズムを表している．横軸は空間計
算量，縦軸は時間計算量を表し，図中の円はそれぞれ右下から $l=1,2,3,$$\ldots$のときの計算量を表す．

34 最短経路を出力する再帰アルゴリズム
最後に，最短距離を求めるのと同様の方法を用いて，最短経路を出力するアルゴリズムを改善する方法を示す．
22 節の Algorithmm12 において，AD.path は Dijkstra

$n$

0.5

$2l3$

$n^{0.6}$$n$space complexityと同等の動作をするため，各小格子グラフに対して図 3: 計算量とパラメータの関係
Dijkstra を用いる代わりに AD-path を再帰的に用いることができる．また，最短距離を求める場合と同様に，再帰の各段ごとに分割を変化させ，最短距離計算では我々の提案アルゴリズムを用いることによって，$Algori0n2$ では始点から各境界頂点へ
より効率の良い時間・空間計算量で計算を行うことができる．更に，の最短距離を求めるのに ADldistance を繰り返して用いているが，これは一度だけ実行すれば十分である．

に最このアルゴリズム全体の空間計算量は，32 節と同様に適切な分割数をとることにより,小化される．また，段目の小格子グラフに対する我々の再帰的最短距離アルゴリズムの時間計算量を
最短経路アルゴリズムの時間計算量をであると, 頂点数を, 分割数をとすると，分割の段数がについてき，各 $i=1,$$O(n^{\frac{2^{l}}{2+1_{-1}}})$$i$$TD_{i}$$TP_{i}$$N_{i}$$k_{i}$$l$$l$$\ldots,$$TP_{i-1}=O(k_{i}^{2}\sqrt{N_{i}}\cross(TD_{i}+TP_{i}))$となる．ただし，
ここで，$TD_{0},$$TP_{0}$(16)は各アルゴリズムの全体の時間計算量 $TD,$ $TP$ である．

$TD_{i-1}=O(k_{i}^{2}\sqrt{N_{i}}\cross TD_{i})$であり，$TP_{l}$$TD_{i}$ と $TP_{i}$と $TD_{l}$ がともに $O(N_{l}^{2})$ であることから，

はオーダの意味で等しくなる．よって，使用メモリが最小となるような分割を行う場合のアルゴリズム全体の時間計算量 $TP$ は $TD$ と同じく

$TP=O(n \frac{2^{l}(l+2)}{2^{l+1}-1})$となる．

4 結論と今後の課題
本研究では，格子グラフ上の二頂点間の最短距離を求めるための，既存手法よりも効率の良いアルゴリズ
ムを提案した．

今後の課題の一つとしては，提案アルゴリズムをより一般的な問題，例えば平面グラフ上の最短経路問題など，に拡張することが考えられる．

参考文献[1] Asano, T. and Doerr, B., ”MemoIy-Constrained Algorithms for Shortest Path Problems”, Proceedings of $23rd$

CCCG, 2011.
[2] Dijkstra, E. W., ”A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik 1, 1959.