d - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第12回
最短路問題とダイクストラ法
• 有向グラフ G = (V, E) を考える
– V: 節点集合, 節点数 n
– E: 枝集合, 枝数 m
• グラフ G の各枝 (i,j)  E は長さ aij を持つ
• ある節点 s  V から別の節点 t  V への路の中で，
最も長さの短いものを見つける問題を最短路問題
15
という
2
4
50
30
20
10
1
5
80
3
15
2
• 下のネットワークで節点 1 を s, 節点 5 を t とすると，
s から t へは 1245, 1235,1345,
12345,135 の5つの路がある
• 路の長さはそれぞれ 95, 85, 120, 110, 95 なので，
最短路は 1235 である
• 大規模なネットワークでは全ての路を数え上げる
方法は実用的ではない
15
2
50
4
30
20
10
1
5
80
3
15
3
最適性の原理
• 節点 s から t への最短路 P が得られているとする
• 路 P に含まれる節点を1つ任意に選び, r とする
• 路 P は s から r までの部分 P1 と， r から t への
部分 P2 に分割できる．このとき，P1 は s から r へ
の最短路で，P2 は r から t への最短路となる
– もし P1 より短い s から r への路 P1’が存在するなら，
P1’と P2 をつないだ路は P2 より短くなる
• このような性質を最適性の原理と呼ぶ
P1
P
r
2
s
P1’
t
4
• ある節点 s からネットワークの他の全節点への最
短路を求める問題を考える
• ダイクストラ法は，枝の長さに関する非負条件
aij  0 ((i,j)  E) の仮定の下で，節点 s から各節
点 i  V への最短路の長さの上限値 d(i) を更新し
ていく反復アルゴリズム
• 計算の途中では，d(i) の値が s から i への真の最
短路の長さに等しいことがわかっている節点が存
在する．そのような節点の集合を S で表す
• S は S の補集合 V  S を表す
5
ダイクストラ (Dijkstra) 法
(0) S := , S := V, d(s) := 0, d(i) :=  (i  V  {s})
とおく
(1) S = V なら計算終了．そうでないなら，
d (v)  min d (i) | i  S  である節点 v  S を選ぶ
(2) S : S  {v}, S : S  {v} とし，(v,j) E かつ j  S
であるような全ての枝 (v,j) に対して
d(j) > d(v) + avj ならば d(j) = d(v) + avj, p(j) := v
とする．ステップ (1) に戻る
p(i) は，s から i までの最短路において i の直前に
6
位置する節点を示すために用いられる
[初期化]
(0) S   , S  {1,2,3,4,5}
50
1
d(1)=0
d(2)=
2
20
80
d(4)=
4
15
30
10
3
d(3)=
d(5)=
5
15
7
[反復1]
(1) S  {1,2,3,4,5}
min d (i) | i  S   0 より v = 1
(2) S  {1}, S  {2,3,4,5}
d(2) =  > d(1) + a12 =50 より d(2) = 50, p(2) = 1
d(3) =  > d(1) + a13 =80 より d(3) = 80, p(3) = 1
50
1
d(1)=0
d(2)=50
2
20
d(4)=
4
15
30
10
5
80
3
d(3)=80
d(5)=
15
8
[反復2]
(1) S  {2,3,4,5}
min d (i) | i  S   50 より v = 2
(2) S  {1,2}, S  {3,4,5}
d(3) = 80 > d(2) + a23 =70 より d(3) = 70, p(3) = 2
d(4) =  > d(2) + a24 =65 より d(4) = 65, p(4) = 2
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=
15
9
[反復3]
(1) S  {3,4,5}
min d (i) | i  S   65 より v = 4
(2) S  {1,2,4}, S  {3,5}
d(5) =  > d(4) + a45 =95 より d(5) = 95, p(5) = 4
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=95
15
10
[反復4]
(1) S  {3,5}
min d (i) | i  S   70 より v = 3
(2) S  {1,2,3,4}, S  {5}
d(5) = 95 > d(3) + a35 =85 より d(5) = 85, p(5) = 3
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
11
[反復5]
(1) S  {5}
自動的に v = 5
(2) S  {1,2,3,4,5}, S  
[反復6]
(1) S = V なので終了
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
12
• アルゴリズムが終了したときの d(i) は，節点 1 から
i への最短路の長さを与えている
• 枝の集合 {(p(i),i)} が各節点への最短路を表す
これを最短路木と呼ぶ
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
13
アルゴリズムの正当性の証明
• ダイクストラ法で，S は出発点 s からの最短路の
長さがわかっている節点の集合であることを確認
• 以下のことを帰納法で示す
– 全ての i に対し, d(i) = [S に含まれる節点のみを経由
して s から i に至る最短路の長さ]
(3.3)
(S に含まれる節点のみを経由するのでは到達できな
い場合は d(i) = )
– i  S ならば，d(i) = [s から i への最短路の長さ]
14
• [反復1] 終了後 S = {s}, d(s) = 0
• S の点 s では，s から s への最短距離は 0 で，d(s)
と等しい
• Sの点から1本の枝で到達できる S の点(2 と 3)では
d(i) = [S に含まれる節点のみを経由して s から i
に至る最短路の長さ] が成り立つ
• それ以外の点では d(i) =  で，命題は成立
50
1
d(1)=0
d(2)=50
2
20
d(4)=
4
15
30
10
5
80
3
d(3)=80
d(5)=
15
15
• 帰納法の仮定：ある反復に入った時点で命題成立
• ステップ(1)で v  S が選ばれたときに，v に対し
d(v) = [S に含まれる節点のみを経由して s から v に至る
最短路の長さ]
= [s から v への最短路の長さ]
(3.4)
それ以外の点に対して (3.3) が成り立つことを示す
• (3.4) を背理法で示す．sから v への最短路をP*とし，
その長さが d(v) と異なるとする
• アルゴリズムの構成法より，各節点 i に対し，d(i)
は s から i へのある路の長さを表しているので，
上の仮定は d(v) > [路 P* の長さ] を意味する
16
• v  S なので，(3.3) より，s から v への真の最短路
P* は，途中で S の点を少なくとも1つ経由する
• P* において初めて現れる S の点を u とすると，P*
*
*
は P1 と P2 に分解できる
• 最適性の原理より， P1* は s から u への最短路
• P1* は S の点のみを経由しているので，(3.3) より
*
d(u) = [路 P1 の長さ] が言える
S
S
p(v)
v
P2*
s
u
P1*
17
• 各枝の長さは非負なので，
*
[路 P* の長さ]  [路 P1 の長さ]
• よって，d(v) > d(u)
• ところが，d (v)  min d (i) | i  S  と u  S より
d(v)  d(u) となり，矛盾
• よって，d(v)は s から v への最短路の長さに等しい
• (3.3) より，その路は S の節点のみを経由するので，
S
S
(3.4) が成り立つ
p(v)
v
P2*
s
u
P1*
18
•
•
•
反復が終了した時点で (3.3) が保たれていること
を示す
反復終了時の S を S   S  {v} と書く
アルゴリズムのステップ(2) を実行したとき
+ に含まれる節点のみを経由して
[S
j  S  d ( j) 
s から j に至る最短路の長さ]

•
を示す
S+ に含まれる節点のみを経由して s から j に至
る最短路は次の3つの場合が考えられる
(a) v を経由しない，つまり S の節点のみを経由
(b) j に到達する直前に v を経由
(c) v を経由し，その後さらに S の節点をいくつか通って
19
j に到達
• (c) はありえない．なぜなら，そのような路が最短路
の場合，j の直前の節点を k とすると，最適性の原
理より，その路の k までの部分は sから kの最短路
• k はそれ以前の反復で S に入っているので，S の
節点のみを経由する s から k への最短路が存在
するはず
• よって，s から j への最短路は(a) か (b) のどちらか
• ステップ(2)で，d(j) > d(v) + avj ならば d(j) を
d(v) + avj で置き換えるが，これは (a) よりも(b)の方
が路が短いときに最短路を置き換えることに対応
• 以上より
+ に含まれる節点のみを経由して

[S
j  S  d ( j) 
20
s から j に至る最短路の長さ]
• 次の反復に入ったときも命題が成り立つことが示さ
れた
• 各反復が終了するたびに， S のどれか1つの節点
が S に入るので，アルゴリズムの反復の回数は
節点数 n に等しい
• ステップ(1) の計算量は各反復で O(log n)，
全体で O(n log n)
• ステップ(2) では，ネットワークの各枝はアルゴリズ
ムを通して高々1回だけ処理されるのでステップ(2)
の計算量は全体で O(m log n) (m: 枝数)
• 以上より，ダイクストラ法の計算量は O(m log n)
21
• d の更新を挿入と削除ではなく，フィボナッチヒープ
のdecrease_keyで行うと，総計算量は
O(m + n log n)
22
動的計画法
(Dynamic Programming)
• 分割統治法と同様，部分問題の解を統合する
ことによって問題を解く．
• 分割統治法では問題を独立な部分問題に分割し，
部分問題を再帰的に解き，それらの解を組み合わ
せて元の問題の解を得る．
• 動的計画法では部分問題が独立でないときに用い，
計算量を削減する．
23
動的計画アルゴリズムの開発
1.
2.
3.
4.
最適解の構造を特徴付ける
最適解の値を再帰的に定義する
ボトムアップ方式で最適解の値を計算する
計算された情報からある最適解を構成する
24
ビタビ (Viterbi) アルゴリズム
• 層状グラフでの最短路を求めるアルゴリズム
– 音声認識などで用いられる
• 層状 (layered) グラフ
– 各節点にはレベルがある
– グラフの枝はレベル i の節点からレベル i+1 の節点へ
50
15
2
20
1
10
4
30
10
6
20
10
8
80
3
30
5
15
7
15
25
• レベル数を l, 各レベル内の節点数を k とすると
– n = kl
– m = k2l
• 始点から終点までのパスの数は kl
• 始点からレベル i+1 の節点までの最短路は，
始点からレベル i のある節点までの最短路に
枝を1つ追加したもの
• レベル i+1 の全節点への最短路は O(k2) 時間で
求まる
• 全レベルでO(k2l) = O(m) 時間
• ダイクストラ法よりも簡単で計算量も小さい
26
最長共通部分系列
(Longest Common Subsequence)
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
S3=GTCGTCGGAAGCCGGCCGAA
• 系列 A が系列 B の部分系列であるとは，B から
0 個以上の要素を取り去ると A になること
• S3 は S1 と S2 両方の部分系列の中で最長
• 最長共通部分系列を動的計画法で求める
27
1. 最長共通部分系列の特徴付け
• LCS(X, Y) を力づく (brute-force) で解く場合
– X の全ての部分系列を生成し，それらが Y の
部分系列になっているか1つずつ調べる
– X の長さを m とすると，部分系列の数は 2m 個
– 遅すぎる
• X = <x1, x2, …, xm> とする
• X の i 番目の接頭語 (prefix) を
Xi = <x1, x2, …, xi> と定義する
28
• 定理 (LCSの部分構造最適性)
X = <x1, x2, …, xm> と Y = <y1, y2, …, yn> のLCSを
Z = <z1, z2, …, zk> とすると
1. xm= yn ならば
zk= xm= yn かつ Zk1 は Xm1 と Yn1 のLCSである
2. xm yn かつ zk xm ならば
Z は Xm1 と Y のLCSである
3. xm yn かつ zk yn ならば
Z は X と Yn1 のLCSである
29
証明: (1) zk xm を仮定すると，Z に xm= yn を付け
加えて X と Y の共通部分系列で長さ k+1 のものを
得られるが，これは Z = LCS(X,Y) という仮定に矛盾．
接頭語 Zk1 は Xm1 と Yn1 の長さ k1 の共通部分
系列だが，これが最長であることを背理法で示す．
長さが k 以上の Xm1 と Yn1 の共通部分系列 W が
存在すると仮定する．W に xm= yn を付加すると X と
Y の共通部分系列で長さ k+1 以上のものが作れ，
矛盾．
30
(2) zk xm ならば， Z は Xm1 と Y の共通部分系列
である．Xm1 と Y の共通部分系列 W で長さが k+1
以上のものが存在すると仮定すると，W は Xm と Y
の共通部分系列でもあるから，Z = LCS(X,Y) という
仮定に矛盾．
(3) (2) と同様．
2つの系列のLCSは，その一部としてそれらの接頭語
のLCSを含んでいることがわかる．従って，LCS問題
は部分構造最適性を持つ．
31
2. 再帰的な解
• X = <x1, x2, …, xm> と Y = <y1, y2, …, yn> のLCSを
求めるとき
• xm= yn ならば Xm1 と Yn1 のLCSが必要
• xm yn ならば2つの部分問題を解く必要がある
– Xm1 と Y のLCS
– X と Yn1 のLCS
– 得られた2つのLCSの長い方が X と Y のLCS
• Xi と Yj のLCSの長さを c[i,j] とすると
0

ci, j   ci  1, j  1  1
max ci, j  1, ci  1, j 

i  0　または　j  0のとき
i, j  0 かつ　xi  y j のとき
i, j  0 かつ　xi  y j のとき
32
3. LCSの長さの計算
• 前述の漸化式をそのまま解くと指数時間かかる
• しかし，異なる部分問題が (mn) 個しかないので
動的計画法で解をボトムアップに計算できる
j 0
1
2
3
4
5
6
• O(mn) 時間
i
y
B
D
C
A
B
A
j
0
xi
1
A
2
B
3
C
4
B
5
D
6
A
7
B
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
1
1
2
2
0
1
1
2
2
2
2
0
1
1
2
2
3
3
0
1
2
2
2
3
3
0
1
2
2
3
3
4
33
0
1
2
2
3
4
4
4. LCSの構成
• c[m,n] の値が X と Y のLCSの長さを表す
• 表中の矢印がLCSの解を表す
– 「↑」はLCSに xi を含めないことを表す
– 「←」はLCSに yj を含めないことを表す
– 斜めはLCSに xi = yj を含めることを表す
• [m,n] のマスから矢印をたどれば解が求まる
• O(m+n) 時間
• 全体で O(mn) 時間
34
文字列の編集距離
• 文字列 X と Y の編集距離 (edit distance) とは，
X に以下の編集操作を繰り返して Y に変換する
際の最小の操作回数である．
– 挿入: xi と xi+1 の間に文字 c を入れる
– 削除: xi を削除
– 置換: xi を文字 c で置き換える
X = ACGTT
A を削除
CGTT
C を挿入
編集距離 = 3
CGCTT
T を A に置換
Y = CGCAT
35
• X の文字を削除する代わりに，Y に gap (空白)
を入れる
• X に文字を挿入するときは必ず Y の文字を入れる
ことになる ⇒ X に gap を入れる
• X と Y に gap を入れた X’ と Y’ で，ミスマッチの数
を最小にする問題と等価
• LCS問題に似ている
X = ACGTT
Y = CGCAT
X’ = ACGTT
Y’ = CGCAT
ミスマッチ = 3
36
• Xi = <x1, x2, …, xi> と Yj = <y1, y2, …, yj> の
編集距離を c[i,j] とする
• xi と yj をマッチさせる場合
– xi= yj ならば c[i,j] = c[i1,j1]
– xi yj ならば c[i,j] = c[i1,j1]+1
• xi の次に gap を入れ yj とマッチさせる場合
– c[i,j] = c[i,j1]+1
• yj の次に gap を入れ xi とマッチさせる場合
– c[i,j] = c[i1,j]+1
• c[i,j] はこれら３つの中の最小値
• O(mn) 時間 (m = |X|, n= |Y|)
37
• 「↑」は Y に gap を入れることを表す
• 「←」は X に gap を入れることを表す
• 斜めは一致または置換を表す
X’ = ACGTT
Y’ = CGCAT
X = ACGTT
Y = CGCAT
j
i
0
xi
1
A
2
C
3
G
4
T
5
T
0
yj
1
C
2
G
3
C
4
A
5
T
0
1
2
3
4
5
1
1
2
3
4
5
2
1
2
3
4
5
3
2
1
2
3
4
4
3
2
2
3
3
5
4
3
3
3
3
38

Download Report