アルゴリズム入門（6）（動的計画法））（動的計画法）

(1)

宮崎修一

京都大学　学術情報メディアセンター

アルゴリズム入門（ 6 ）

（動的計画法）

(2)

2

動的計画法の考え方：

　元の問題から、よりサイズの小さい「部分問題」を定義する。

　部分問題を解いた結果を表にまとめておき、

　より大きなサイズの部分問題を解くときに、表の結果を利用する。

　小さい部分問題から順番に解いて行って、最後の部分問題が　元の問題そのものである。（よって、最後には元の問題が　解けたことになる。）

(3)

3

行列の掛け算

６　　１０　　２

８　　１　　６０　　１　　２２　　０　　０

２ × ３行列　　　　　３ × ４行列

２６　９　３０＝

１６　３６　４　２４２ × ４行列

（４ × ８）＋（０ × ０）＋（２ × ２）

　　３回の掛け算

掛け算の回数は全体で（２ × ４） × ３回

問題：掛け算は　　全部で何回？

(4)

4

。。。。。。。

。。。。。。。。。。

（ p×q ）行列　　　　　　（ q×r ）行列

＝。。。。。。。。。。

。。。。。。。。。。

（ p×r ）行列

掛け算の回数は全体で p×q×r 回

q

p q

r

r p

(5)

5

４つの行列の掛け算

Ａ　　_１× 　Ａ　　_２ × 　Ａ　　_３ × _４　Ａ

（５０ × ２）　　（２ × ８０）　　（８０ × ３）　　（３ × ２０）

　・掛け算結果は、順番に依らない。

　・掛け算回数は、順番に大きく依存する。

Ａ　 × Ａ　　→　５０_１ _２ × 　２ × ８０＝　８０００回　^{結果は５０} ^× ^８０行列Ａ　 × Ａ　　→　８０_３ _４ × 　３ × ２０＝　４８００回　^{結果は８０} ^× ^２０行列

　　 × 　　　 →　５０ × ８０ × ２０＝８００００回　　　　　　　計　９２８００回

Ａ　 × Ａ　　→　　２_２ _３ × ８０ × 　３＝　　４８０回　^{結果は　２} ^× ^３行列Ａ　 × 　　　→　５０_１ × 　２ × 　３＝　　３００回　^{結果は５０} ^× ^３行列

　　 × Ａ　　→　５０４ × 　３ × ２０＝　３０００回　　　　　　　計　　３７８０回

問題：これより少ない回数で出来る？

(6)

6

（　　　　）

（　　　　） n 個の行列が与えられたとき

Ａ　　 _１× 　Ａ　　_２ × 　・・・　 × _ｎ　Ａ

どういう順番で掛けていくのが、掛け算回数が最も少ないか？

Ａ　_１Ａ　_２Ａ　_３Ａ　_４

Ａ　_１Ａ　_２Ａ　_３Ａ　_４Ａ　_１Ａ　_２Ａ　_３Ａ　_４

（　　　　　　）（　　　　）（　　　　）Ａ　（　　　　　　）１Ａ　_２Ａ　_３Ａ　_４

Ａ　（　　　　）Ａ　_２Ａ　_３Ａ　_４（　　　　）２Ａ　_３Ａ　_４Ａ　_１Ａ　_２Ａ　_３Ａ　_１Ａ　_２Ａ　_３

４８００回４８０回８０００回４８０回

４８０＋１２０回３２００＋

４８００回１２０００＋

８０００回

８０００回４８００回

３００＋４８０回

６００回７８０回

２０００＋

６００回８０００＋

４８００＋

８００００回

７８０＋３０００回

２６００回

(7)

7

n 個の場合、場合分けは≧４ⁿ

木全体を計算していたのでは、多項式時間では収まらない。

　　　　　　　↓ 　　　　　　動的計画法

(8)

8

動的計画法の考え方（ n ＝６の場合の例）

Ａ　_１Ａ　_２Ａ　_３Ａ　_４Ａ　_５Ａ　_６

１、２－６１－２、３－６１－３、４－６１－４、５－６１－５、６

２、３－６２－３、４－６２－４、５－６２－５，６

３－６を計算する最小値

４－６を計算する最小値

木のサイズは大きいのだけど、

同じものが何度も出てくる。

　　　　　　↓

同じ部分は１度だけ計算して表に蓄えておいて、後で使う。

　　　　 | |

動的計画法の考え方

４－６を計算する最小値

(9)

9

m[i, j] ：　　　　　　を計算するのに、掛け算回数を

　　　　　一番少なくした場合の掛け算回数。

Ａ_１ p０

p_１

Ａ_２ p１

p_２

Ａ_n p_n

－１

p n

・・・

Ａ　_i Ａ　_i+1・・・Ａ　_j-1Ａ　_j

つまり、求めたいのは m[1, n] 。

(10)

10

第１ステップ：

m[i, i]=0 （全ての i に対して）

　つまり、　　を求めるのに掛け算回数は０回。Ａ　_i 第２ステップ：

m[i, i+1] を求める（ 1≦i≦n-1 ）

　つまり、　　　　　を求める掛け算回数。Ａ　_i Ａ　_i+1

Ａ_i pi －１

p i

Ａ_i+1 p_i

p_i+1 m[i, i+1]= p p p_i-1 _i _i+1

(11)

11

第３ステップ：

m[i, i+2] を求める（ 1≦i≦n-2 ）

　つまり、　　　　　　　　を求める掛け算回数。

pi－１

p i+1

p i+2

Ａ　_i Ａ　_i+1Ａ　_i+2

Ａ　_iＡ　_i+1 Ａ　_i+2

（　　　　　）（　　　　　　）Ａ　_i Ａ　_i+1Ａ　_i+2

Ａ　_iＡ　_i+1 Ａ　_i+2 p

i －１

pi

p i

p i+2

Ａ　_i Ａ　_i+1Ａ　_i+2

m[i, i+2]= min{m[i, i+1] + m[i+2, i+2] + p p p , m[i, i] + m[i+1,i+2] + p p p }_i-1 ^i-1_i ⁱ⁺¹_i+2 ⁱ⁺²

この２通りのうち、少ない方。

(12)

12

第 k ステップ：

m[i, i+k-1] を求める（ 1≦i≦n-k+1 ）Ａ　_iＡ　_i+1Ａ　_i+2

m[i, i+k-1]= min{m[i, i]+ m[i, i+k-1]+ p p p ,

m[i, i+1]+m[i+2, i+k-1]+ p p p , ・・・

m[i, i+k-3]+m[i+k-2,i+k-1]+p p p , m[i, i+k-2]+m[i+k-1,i+k-1] + p p p }

i

i-1 i+k-1

Ａ　_i+k-2Ａ　_i+k-1

・・・

（　　　　　）Ａ　_i Ａ　_i+1Ａ　_i+2・・・Ａ　_i+k-2Ａ　_i+k-1

（　　　　）Ａ　_iＡ　_i+1 Ａ　_i+2・・・Ａ　_i+k-2Ａ　_i+k-1

（　）

・・・

（　　　　）Ａ　_iＡ　_i+1Ａ　_i+2・・・Ａ　_i+k-2 Ａ　_i+k-1

（）

Ａ　_iＡ　_i+1Ａ　_i+2 Ａ　_i+k-2Ａ　_i+k-1

（）・・・Ａ　_i+k-3

i+1

i-1 i+k-1

i+k-3

i-1 i+k-1

i+k-2

i-1 i+k-1

(13)

13

同様に進めて、第 n ステップで m[1, n] が求まる。

計算時間は O(n ) 。³

m[i, j] は O(n ) 。

１つを計算するのに O(n) 。

2

(14)

14

最大独立頂点集合問題（以前やった）

　入力：グラフ G=(V, E )

独立頂点集合：間に枝のない頂点集合

(15)

15

最大独立頂点集合問題（以前やった）

　入力：グラフ G=(V, E )

問題：最大サイズの独立頂点集合を求めよ。

(16)

16

重み付き最大独立頂点集合問題

　入力：グラフ G=(V, E ) 　（各頂点に重みが付いている）

1

2

3 3

4 1

6 8

問題：最大サイズの独立頂点集合を求めよ。

　　　　（ただしここでは、「サイズ」とは頂点の重みの和。）

(17)

17

重み無しの場合は、木では貪欲アルゴリズムで多項式時間で解けることを見た。

重み付きの場合は、貪欲アルゴリズムはうまく働かない。

問題：貪欲アルゴリズムがうまく働かない木の例を挙げよ。

9

1 1

(18)

18

動的計画法を使うと、重み付きでも（木に限定すれば）

多項式時間で解ける。

T(v): v を根とする　　　部分木

v

(19)

19

A(v): 「 v を選ぶ」という条件の下での、

　　　　 ^T(v) の最大独立頂点集合のサイズ。

B(v): 「 v を選ばない」という条件の下での、

5

問題：今の場合の

A(v) 、 B(v) 、 C(v) を求めよ

C(v): （何の条件もなく）、 T(v) の最大独立頂点集合のサイズ。

A(v)=9 B(v)=10

C(v)=max{A(v), B(v)}=10

v

6 3

1 3

1

(20)

20

A(v): 「 v を選ぶ」という条件の下での、

B(v): 「 v を選ばない」という条件の下での、

C(v): （何の条件もなく）、 T(v) の最大独立頂点集合のサイズ。

根を r とすると、

元の問題の最終的な

答えは C(r) v

r

(21)

21

動的計画法の方針：葉から根に向かって、 A(v) 、 B(v) 、 C(v) を　計算していく。

v が葉の場合

T(v) は v1 個からなるので、 A(v)= w(v), B(v)=0, C(v)=max{A(v), B(v)}= w(v).

以降、頂点 v の重みを w(v) と書くことにする。

v

(22)

22

v が葉でない場合

v

x y z

A(v)=

B(v)=

C(v)=max{A(v), B(v)}

　　　 w(v)+B(x)+B(y)+B(z)

（ v を選ぶとすると、 x, y, z は選べない。）

　　　 C(x)+C(y)+C(z)

（ v を選ばないとすると、 x, y, z は選んでも選ばなくても良い。）

(23)

23

v

x y z

T(x) T(y) T(z)

T(x), T(y), T(z) 間にはお互いに枝がなく、また v とも枝がないので、それぞれ独立に計算できる。

(24)

24

A(v)= w(v)+B(x)+B(y)+B(z) B(v)=C(x)+C(y)+C(z)

C(v)=max{A(v), B(v)}

計算時間

d(v)-1 個の表参照と d(v)-1 回の足し算 d(v)-1 個の表参照と d(v) 回の足し算

1 回の大小比較頂点 v に関する表計算に O(d(v)) 時間

全体では、 Σd(v) = 2|E| = 2(n-1)

d(v) ：頂点 v の次数

（木は |E| = n-1 ）よって、計算時間は O(n)

(25)

25

最短経路問題

　入力：重みつきグラフ G=(V, E) 　　　　　 V の 2 頂点 s と t

　出力： s から t への最短経路

4

3

10

7

s 8 例： t

2

5 2

1

2+2+5+1=10 v₁

v₂

v₃

v₄

問題： s から t への最短経路は？

　　　　その距離は？

(26)

26

単純な方法

　　・全ての s-t パスを列挙。

　　・それぞれの経路のコストを計算。

　　・最も短い経路を解として出力。

s v₁ v₃ t

s v₂ v₄ t

s v₁ v₄ t

12 16 11

s v₁ v₂ v₄ t 10

… …

原理的には最適解が求まる。しかし。。。

　・全てのパスを簡単に列挙できる？

　・出来たとしても、そもそもパスが指数個あったら、

　　多項式時間アルゴリズムにはならない。

(27)

27

問題： s から t へのパスの数が（頂点数の）指数個ある例はあるか？

s … t

k 個頂点数： n=5k+1

s-t パスの数： ^k4 = 4^n-1⁵

前ページのアルゴリズムは多項式時間では終了しない。

（もちろん、上記の例だけに対応するのは簡単。

　各コンポーネントでの最短経路を繋ぎ合わせれば良い。）

(28)

28

Dijkstra （ダイクストラ）のアルゴリズム

ステップ 1 ： L=Φ （空集合）とする。

　　　　　　　各頂点（ v ）に値（ δ(v) ）をつける。

δ(s)=0

δ(v)=∞ （ s 以外の頂点 v ）

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

∞

(29)

29

ステップ 2 ： L に頂点 s を加える。

　　　　　　　 s に隣接する頂点の値を d(s,v) に更新

　　　　　　　（更新された頂点は、 s にリンクを張る）

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

∞ ∞

∞ 2 ∞

∞ 10

d(s,v) ：枝 (s,v) の重み

(30)

30

ステップ 3 ： t が L に入るまで、以下を繰り返す。

　　　　・ L に入っていない頂点の中で、値が最小のものを v とする。

　　　　・ v を L に加える。

　　　　・ L に入っていない、 v に隣接する全ての頂点 u に対して、

　　　　　　　　　 δ(u)= min {δ(u), δ(v)+d(v,u) } とする。

　　　　・値が更新されたものはリンクを更新する。

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2 ∞

10

∞9

∞ 4 10

(31)

31

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2 ∞

10 4

9 8

9

(32)

32

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

∞ 11 ステップ 3 ： t が L に入るまで、以下を繰り返す。

(33)

33

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

111 0 ステップ 3 ： t が L に入るまで、以下を繰り返す。

(34)

34

1 0

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

(35)

35

1 0

ステップ 4 ：この時点で t についている値が、 s から t までの　　　　　　　最短距離。

　　　　　　　 t にその値を付けるに至った経路が最短経路。

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

(36)

36

正しさの証明

アルゴリズムの任意の時点で、

　　「 L に入っている頂点の値は、 s からそこまでの最短距離」

を証明する。

つまり、

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

9

10

∞

(37)

37

帰納法で証明する

最初：　　 L に入っているのは s のみ。

　　 s の値は 0 。

　　 s から s までの最短距離は 0 。　　　　よって成り立つ。

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

∞

(38)

38

あるステップで正しいとする

s 0

1

2 2

4 5

6

このとき、新たに加えられた頂点についても正しいことを示す。

11

∞

→8

→9

(39)

39

いま x≦y, x≦z が成り立っている。（ v が選ばれたのだから）

x=min{a+d, c+e} である。（ x の値の決め方から）

d s

0 e

a

b c

x y

z v

s から v への最短距離が x でないとして、矛盾を導く。

x より短い s － v パスがあったとする。その長さを x’ < x とする。

*

v₁ v₂

v₃

v₄

v₅

(40)

40

d s

0 e

a

b c

x y

z v

x’= （ s から v までの経路） +d x≦a+d

x’<x

なので、（ s から v までの経路） < a となる。

ということは、 s から（ L の中にある） v への最短距離が a であること（つまり帰納法の仮定）に矛盾。

場合 (1) ：最後に使われた枝が、 L の中の頂点から v に向かう。

v₁

v₅ v₄

*

1

1 1

(41)

41

d s

e 0

a

b c

x

y v

場合 (2) ：最後に使われた枝が、 L の外の頂点から v に向かう。

f

v から逆にたどって、初めて L に入るところ。

w

s から u への最短経路は、帰納法の仮定より c 。

なので、紫の道も、その最短路を通っているはず。

（さもなければ、 s から v へ、紫よりも短い道がある。）

*

v₁

u

*

(42)

42

d s

e 0

a

b c

x

y v

場合 (2) ：最後に使われた枝が、 L の外の頂点から v に向かう。

f

s→u→w 路は、 x’ より短い。（紫が x’ なのだから）つまり c+r < x’ 。 w は u につながっているので、 u が L に入った時点で δ(w) は

c+r 以下であるはず。

δ(w)≦c+r < x’< x 　つまり δ(w)<x 。

したがって、次のステップで v が L に入れられるのはおかしい。

矛盾。

r

*

u w

*

(43)

43

直観的には

s 0

1

2 2

4 5

8

これは確定

4 より短くなりようがない

（他の頂点へ、赤の中から行くのは、

4 以上かかるから）

こいつは確定してはいけない 8 より短い道があるかも

1

(44)

44

計算時間　頂点は n 個あり、それぞれが高々 n 回しか更新されない。

　　 O(n )

　枝は m 本あり、それぞれ 1 回しか走査されない。

　　 O(m)

　よって全体で O(n +m) 。

2

(45)

45

問題：次のグラフの最短経路とその値を求めよＡ

Ｂ

Ｃ

Ｅ

Ｆ

4 2

4 9

2 1

1

5

2 7

5 s

D 1

t 5

アルゴリズム入門（6）（動的計画法））（動的計画法）

宮崎修一

京都大学 学術情報メディアセンター