アルゴリズム入門（6）

宮崎修一

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

アルゴリズム入門（ 6 ）

（動的計画法）

2

動的計画法の考え方：

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

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

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

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

解けたことになる。）

3

行列の掛け算

３ ６ １ ４ ０ ２

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

＝

１７ ２６ ９ ３０ １６ ３６ ４ ２４

２×４行列

問題：掛け算は

全部で何回？

4

。。。。。。。

。。。。。。。

。。。。。。。

。。。。。。。。。。

。。。。。。。。。。

。。。。。。。。。。

。。。。。。。。。。

。。。。。。。。。。

（

×

）行列 （

×

）行列

＝

。。。。。。。。。。

。。。。。。。。。。

。。。。。。。。。。

（

×

）行列

掛け算の回数は全体で

×

×

回

q

p q

r

r p

5

４つの行列の掛け算

Ａ

× Ａ

× Ａ

× Ａ

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

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

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

Ａ × Ａ

５０× ２×８０＝ ８０００回

Ａ × Ａ

８０× ３×２０＝ ４８００回

×

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

Ａ × Ａ

２×８０× ３＝ ４８０回

Ａ ×

５０× ２× ３＝ ３００回

× Ａ

５０× ３×２０＝ ３０００回 計 ３７８０回

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

6

（ ）

（ ）

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

Ａ

× Ａ

× ・・・ × Ａ

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

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

（ Ａ

Ａ

Ａ

） （ ）（ ） （ Ａ

Ａ

Ａ

） Ａ

Ａ

（ Ａ

Ａ

） （ Ａ

Ａ

） Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

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

４８０＋

１２０回 ３２００＋

４８００回 １２０００＋

８０００回

８０００回 ４８００回

３００＋

４８０回

６００回 ７８０回

２０００＋

６００回 ８０００＋

４８００＋

８００００回

７８０＋

３０００回

２６００回

7

n

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

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

↓

動的計画法

8

動的計画法の考え方（

＝６の場合の例）

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

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

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

３－６を計算 する最小値

３－６を計算 する最小値

４－６を計算 する最小値

４－６を計算 する最小値

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

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

↓

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

| |

動的計画法の考え方

４－６を計算 する最小値

４－６を計算 する最小値

9

m[i, j]

： を計算するのに、掛け算回数を

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

Ａ

p １

Ａ

p ２

Ａ

p n

・・・

Ａ

Ａ

・・・ Ａ

Ａ

つまり、求めたいのは

。

10

第１ステップ：

m[i, i]=0

（全ての

に対して）

つまり、 Ａ

を求めるのに掛け算回数は０回。

第２ステップ：

m[i, i+1]

を求める（

）

つまり、 Ａ

Ａ

を求める掛け算回数。

Ａ

p i

Ａ

p_i+1

m[i, i+1]= p p p

i

i-1 i+1

11

第３ステップ：

m[i, i+2]

を求める（

）

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

pi－１

p i+1

p i+1

p i+2

Ａ

Ａ

Ａ

Ａ

Ａ

Ａ

（ ） Ａ

（ Ａ

Ａ

）

Ａ

Ａ

Ａ

i－１

pi

p i

p 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+2

i-1 i i+2

第

ステップ：

m[i, i+k-1]

を求める（

） Ａ

Ａ

Ａ

・・・ Ａ

Ａ

（ ）

Ａ

Ａ

Ａ

・・・ Ａ

Ａ

（ ）

Ａ

Ａ

Ａ

・・・ Ａ

Ａ

（ ）

・・・

（ Ａ

Ａ

Ａ

・・・ Ａ

） Ａ

（ ）

Ａ

Ａ

Ａ

Ａ

Ａ

（ ・・・ Ａ

）

12

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+1

i-1 i+k-1

i+k-3

i-1 i+k-1

i+k-2

i-1 i+k-1

13

同様に進めて、第

ステップで

が求まる。

計算時間は

。

m[i, j]

は

。

１つを計算するのに

。

2

14

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

入力：グラフ

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

15

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

入力：グラフ

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

16

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

入力：グラフ

（各頂点に重みが付いている）

1

2

3 3

4 1

6 8

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

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

17

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

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

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

18

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

多項式時間で解ける。

T(v): v

を根とする 部分木

v

19

A(v):

「

を選ぶ」という条件の下での、

T(v)

の最大独立頂点集合のサイズ。

B(v):

「

を選ばない」という条件の下での、

T(v)

の最大独立頂点集合のサイズ。

5

問題：今の場合の

A(v)

、

、

を求めよ

C(v):

（何の条件もなく）、

の最大独立頂点集合のサイズ。

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

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

v

6 3

1 3

1

20

A(v):

「

を選ぶ」という条件の下での、

T(v)

の最大独立頂点集合のサイズ。

B(v):

「

を選ばない」という条件の下での、

T(v)

の最大独立頂点集合のサイズ。

C(v):

（何の条件もなく）、

の最大独立頂点集合のサイズ。

根を

とすると、

元の問題の最終的な

答えは

r

21

動的計画法の方針： 葉から根に向かって、

、

、

を 計算していく。

v

が葉の場合

T(v)

は

個からなるので、

以降、頂点

の重みを

と書くことにする。

v

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)

（

を選ぶとすると、

は選べない。）

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

（

を選ばないとすると、

は選んでも選ばなくても良い。）

23

v

x y z

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

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

間にはお互いに枝がなく、また

とも枝が

ないので、それぞれ独立に計算できる。

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

個の表参照と

回の足し算

個の表参照と

回の足し算

1

回の大小比較 頂点

に関する表計算に

時間

全体では、

d(v)

：頂点

の次数

（木は

）

よって、計算時間は

25

最短経路問題

入力：重みつきグラフ

の

頂点

と

出力：

から

への最短経路

4

3

10

7

s 8

例：

2

5 2

1 v₁

v₂

v₃

v₄

問題：

から

への最短経路は？

その距離は？

26

単純な方法

・全ての

パスを列挙。

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

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

s v₁ v₃ t

s v₂ v₄ t

s v₁ v₄ t

12 16 11

s v₁ v₂ v₄ t 10

… …

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

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

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

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

27

問題：

から

へのパスの数が（頂点数の）指数個ある例はあるか？

28

Dijkstra

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

ステップ

：

（空集合）とする。

各頂点（

）に値（

）をつける。

δ(s)=0

δ(v)=∞

（

以外の頂点

）

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

∞

∞

∞

∞

∞

29

Dijkstra

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

ステップ

：

に頂点

を加える。

s

に隣接する頂点の値を

に更新

（更新された頂点は、

にリンクを張る）

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

∞ ∞

∞ 2 ∞

∞ 10

d(s,v)

：枝

の重み

30

Dijkstra

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

ステップ

：

が

に入るまで、以下を繰り返す。

・

に入っていない頂点の中で、値が最小のものを

とする。

・

を

に加える。

・

に入っていない、

に隣接する全ての頂点

に対して、

δ(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

∞ 10 4

31

Dijkstra

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

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2 ∞

10 4

9 8

9

ステップ

：

が

に入るまで、以下を繰り返す。

・

に入っていない頂点の中で、値が最小のものを

とする。

・

を

に加える。

・

に入っていない、

に隣接する全ての頂点

に対して、

δ(u)= min {δ(u), δ(v)+d(v,u) }

とする。

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

32

Dijkstra

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

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

∞ 11

ステップ

：

が

に入るまで、以下を繰り返す。

・

に入っていない頂点の中で、値が最小のものを

とする。

・

を

に加える。

・

に入っていない、

に隣接する全ての頂点

に対して、

δ(u)= min {δ(u), δ(v)+d(v,u) }

とする。

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

33

Dijkstra

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

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

1110

ステップ

：

が

に入るまで、以下を繰り返す。

・

に入っていない頂点の中で、値が最小のものを

とする。

・

を

に加える。

・

に入っていない、

に隣接する全ての頂点

に対して、

δ(u)= min {δ(u), δ(v)+d(v,u) }

とする。

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

34

10

Dijkstra

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

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

ステップ

：

が

に入るまで、以下を繰り返す。

・

に入っていない頂点の中で、値が最小のものを

とする。

・

を

に加える。

・

に入っていない、

に隣接する全ての頂点

に対して、

δ(u)= min {δ(u), δ(v)+d(v,u) }

とする。

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

35

10

Dijkstra

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

ステップ

：この時点で

についている値が、

から

までの 最短距離。

t

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

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

8

9

36

正しさの証明

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

「

に入っている頂点の値は、

からそこまでの最短距離」

を証明する。

つまり、

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

2

4

9

10

∞

37

帰納法で証明する 最初：

L

に入っているのは

のみ。

s

の値は

。

s

から

までの最短距離は

。 よって成り立つ。

4

3

10

7

s 8

t 2

5 2

1 v₁

v₂

v₃

v₄ 0

∞

∞

∞

∞

∞

38

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

s 0

1

2 2

4 5

6

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

11

∞

→8

→9

39

いま

が成り立っている。（

が選ばれたのだから）

x=min{a+d, c+e}

である。（

の値の決め方から）

d

s

e 0

a

b c

x y

z v

s

から

への最短距離が

でないとして、矛盾を導く。

x

より短い

－

パスがあったとする。その長さを

とする。

*

*

*

*

v1

v2

v3

v4

v5

40

d

s

e 0

a

b c

x y

z v

x’=

（

から

までの経路）

x’<x

なので、（

から

までの経路 ）

となる。

ということは、

から（

の中にある）

への最短距離が

であること（つまり帰納法の仮定）に矛盾。

場合

：最後に使われた枝が、

の中の頂点から

に向かう。

v1

v5

v4

*

*

1

1 1

41

d

s

e 0

a

b c

x

y v

場合

：最後に使われた枝が、

の外の頂点から

に向かう。

f

v

から逆にたどって、初めて

に入るところ。

w

s

から

への最短経路は、帰納法の仮定より

。

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

（さもなければ、

から

へ、紫よりも短い道がある。）

*

*

*

v1

u

*

42

d

s

e 0

a

b c

x

y v

場合

：最後に使われた枝が、

の外の頂点から

に向かう。

f

s→u→w

路は、

より短い。（紫が

なのだから） つまり

。

は

につながっているので、

が

に入った時点で

は

c+r

以下であるはず。

δ(w)≦c+r < x’< x

つまり

。

したがって、次のステップで

が

に入れられるのはおかしい。

矛盾。

r

*

u w

*

*

43

直観的には

s 0

1

2 2

4 5

8

これは確定

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

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

4以上かかるから）

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

1

1

44

計算時間

頂点は

個あり、それぞれが高々

回しか更新されない。

O(n )

枝は

本あり、それぞれ

回しか走査されない。

O(m)

よって全体で

。

2

2

45

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

Ｂ

Ｃ

Ｅ

Ｆ

4 2

4 9

2 1

1

5

2 7

5 s

D 1

t 5