情報知能学科「アルゴリズムとデータ構造」 ８章　動的計画法 杉原厚吉．（２００１）.「データ構造とアルゴリズム」. 東京：共立出版. 2010/07/09-13 情報知能学科「アルゴリズムとデータ構造」 担当：白井英俊

本章の目的 多くの可能な組み合わせの中から、最適な組み合わせを見つけるという問題においては、「ありえない組み合わせ」を早い段階で除外するのが常套手段 最適性の原理が成り立つ問題において、上記の方法を実現する「動的計画法」を学ぶ

最適性の原理(principle of optimality) 最適性の原理：最適解は、その一部を取り出しても、それ自体（対応する小問題の）最適解である、という性質 例：グラフG=(V,E)で、各辺e∊Eが、非負の長さをもつ場合 vsからvtまでの黒線が最短路とすれば、 v1からv2まではp2が最短路 vt v1 p2 v2 p3 p1 vs p’2

動的計画法(dynamic programming) 最適性の原理が成り立つ場合において、小問題の最適解を積み重ねることで大問題の最適解を解く技法 代表例 　　グラフG=(V, E)のすべての頂点対の間の最短路の長さを計算するアルゴリズム All-Shortest-Paths

All-Shortest-Paths 頂点の集合 V={v1, v2, …, vn} グラフG=(V, E)のすべての頂点対の間の最短路の長さを計算するアルゴリズム 頂点の集合 V={v1, v2, …, vn} l(vi,vj): 辺eの両端点がvi、vjの時の辺eの長さ 　dk(i,j)：k番目以下の頂点のみを途中で経由してもよいという条件のもとでの、viからvjへの最短路の長さ 計算量はO(n3) 初期値の設定 for 1 ≦i<j≦n do d0(i,j) ← l(vi,vj); for k ← 1 until n do for 1 ≦i<j≦n do dk(i,j) ← min{dk-1(i,j) , dk-1(i,k)+dk-1(k,j)}; 元の値とk番目頂点経由の値と比較

All-Shortest-Pathsの例 v2 for 1 ≦i<j≦n do d0(i,j) ← l(vi,vj); for k ← 1 until n do for 1 ≦i<j≦n do dk(i,j) ← 　　　　　 min{dk-1(i,j) , dk-1(i,k)+dk-1(k,j)}; 2 2 8 8 5 5 v1 v3 1 1 1 1 4 4 すべての(i, j) の組み合わせ v4 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) k=0 2 5 1 8 4 1 7 7 3 3 1 k=1 2 5 1 7 3 1 k=2 5 1 2 1 1 7 3 k=3 2 5 2 k=4 4

All-Shortest-Pathsの計算量 頂点対はO(n2)あるので、ここの計算量はトータルでO(n2) for 1 ≦i<j≦n do d0(i,j) ← l(vi,vj); for k ← 1 until n do for 1 ≦i<j≦n do dk(i,j) ← 　　　　　 min{dk-1(i,j) , dk-1(i,k)+dk-1(k,j)}; 網掛の部分の計算量はO(1). 頂点対はO(n2)あるので、 大きい網掛の部分の 計算量はトータルでO(n2) kが1からnまで変化するので、計算量はトータルでO(n3)

All-Shortest-Pathsの演習 v2 2 8 6 5 v5 9 v3 v1 1 1 1 4 v4 2

8.2 弾性マッチング 弾性マッチング(elastic matching) 前提：列A=(a1,a2,…,am)と列B=(b1,b2,,…,bn)があり、これらの要素aiとbjの間に対応コスト(実数)cijが与えられている。 ２つの列の要素の対(ai, bj)の集合Tが弾性マッチングと呼ばれるための条件： (i) 2つの列の各要素は、Tの中の少なくとも一つの対に含まれる (ii) Tの中の列は列の順序を乱さない。つまり、 (ai, bj)∊T, (ak, bl) ∊Tかつi<kならば、j≦l AもBもすべての要素がどれかに対応 対応する要素が交差(図8.5(b))することはない

弾性マッチングのイメージ a1,　a2, a3 a4 a5 a6 … am b1 b2 b3 b4 …. bn

コスト最小弾性マッチング 弾性マッチングTのコスト：Tに属す対のコストの和 コスト最小弾性マッチング：列Aと列Bの弾性マッチングのうち、コスト最小のもの コスト最小弾性マッチングのイメージ：2本のゴムを部分的に伸ばしたり縮めたりして、最も小さいコストで対応のとれるところを探す

コスト最小弾性マッチングの応用 例8.1: 両眼立体視 例8.2: 単語音声認識 （両目で見るように）２台のカメラで対象をとらえることによって、奥行を計測する。それには、２台のカメラがとらえた映像の対応点を決定する必要がある。対応点が分かれば、幾何学的に奥行を計算できる 例8.2: 単語音声認識 　 入力音声の波形データを、コンピュータに蓄積された音声データと比較して、どの単語かを認識する。音声データを一定間隔に区切ったものを音素単位とみなす。それらの対応点とコスト(例えば、周波数分析し周波数成分の大きさの差の合計)からコスト最小な標本データ⇒入力された単語を求める

コスト最小弾性マッチングの解法 列A=(a1,a2,…,am)と列B=(b1,b2,,…,bn)のコスト最小弾性マッチングを図8.8のように表して求める　　 水平方向に左からa1,a2,…,amを並べ、 垂直方向に左からb1,b2,…,bnを並べる これらのデータを通る垂直、水平の直線を延ばして、格子構造を作る 対応(ai, bj)は格子点 弾性マッチングはこの格子点を 左下から右上までつないだ線 bn このような線はいろいろある が最小コストのものを求める … b3 最適性原理が成り立つ ⇒動的計画法が使える b2 b1 a1 a2 a3 … am

参考：コスト最小弾性マッチングと最短路探索の関係 最小弾性マッチング問題は、格子点を「グラフの頂点」とみなす と、m*n個の頂点からなるグラフにおいて、(a1, b1)から(am , bn) への最短路探索問題とみなせる bn … b3 b2 b1 a1 a2 a3 … am ただ、最小弾性マッチングの『グラフ』は頂点の個数が多く、辺の個数が少ない （向きを考えれば各頂点に対して高々３本）。そのため、解き方が異なる。

アルゴリズムElastic-Matching 列A=(a1,a2,…,am)と列B=(b1,b2,,…,bn)の最小コスト弾性マッチングを求める。c(i,j)は(ai, bj)の対応コスト. d(i,j) :列Aの最初の方の部分列(a1,a2,…,ai)と列Bの最初の方の(b1,b2,,…,bj)のコストの最小値 対応コスト 上に直線を延ばす d(1,1) ← c(1,1); for j ← 2 until n do d(1,j) ← d(1,j-1) +c(1,j); for i ← 2 until m do for j ← 1 until n do d(i,j) ← min{d(i-1,j-1), d(i-1,j), d(i,j-1)}+c(i,j); 斜め上に直線を延ばす 右に直線を延ばす 上に直線を延ばす

アルゴリズムElastic-Matchingの計算量 計算量はO(nm) 計算量はO(n) d(1,1) ← c(1,1); for j ← 2 until n do d(1,j) ← d(1,j-1) +c(1,j); for i ← 2 until m do for j ← 1 until n do d(i,j) ← min{d(i-1,j-1), d(i-1,j), d(i,j-1)}+c(i,j); 計算量はO(n　　) *m

アルゴリズムElastic-Matchingの例 d(1,1) ← c(1,1); for j ← 2 until n do d(1,j) ← d(1,j-1) + c(1,j); for i ← 2 until n do for j ← 1 until n do d(i,j) ← min{d(i-1,j-1), d(i-1,j), d(i,j-1)} +c(i,j); a1 a2 a3 a4 b1 2 5 8 3 b2 6 b3 7 1 4 2 5 8 3 6 3 2 6 7 1 5 4 j 3 12 6 11 13 5 2 8 9 15 1 7 15 18 d(i,j) i 1 2 3 4

動的計画法の練習課題 出欠課題（２） S1 S２ 下図のラインで、車を組立てる最短時間とその順路を求めよ。 車を組み立てる ２つのライン がある。 各ラインには n個のステーション S1,j 、 S2,j がある。 ステーションSi,jでは組立にai,j時間、ラインを変えるにはti,j時間かかる。またラインとの引き渡しにはStartでbi, Goalでci時間かかる 下図のラインで、車を組立てる最短時間とその順路を求めよ。 (下図ではn=6。 ai,j、 bi 、 ci 、 ti,j それぞれの値を確認せよ） S1 7 9 3 4 8 4 3 2 3 1 3 4 2 Goal Start 2 1 2 2 1 4 2 S２ 8 5 6 4 5 7 1 　 2 　3 4 5 6

練習問題を解くために 以下の表を参考にせよ S1 S２ S1 S２ 18 4+8= 2+7= 12 9 < 9+9 12+9+2 7 問題訂正版 以下の表を参考にせよ S1 18 S２ 計算： 4+8= 2+7= 12 9 1 　2 3 4 5 6 Goal 9+9 < 12+9+2 S1 7 9 3 4 8 4 3 2 3 1 3 4 2 Goal Start 2 1 2 2 1 4 2 S２ 8 5 6 4 5 7 1 　 2 　3 4 5 6

プログラム演習 宿題とする。締切りは７月１８日！ All-Shortest-Pathsのアルゴリズムをプログラムとして実現せよ。そのプログラムを教科書p.89, 演習問題8.2の問題に適用し、正解が得られることを確かめよ。 最小コスト弾性マッチングのアルゴリズムをプログラムとして実現せよ。そのプログラムを教科書p.89, 演習問題8.4の問題に適用して、正解が得られることを確かめよ。 最小コスト弾性マッチングのアルゴリズムを改変し、最小コストだけではなくどの部分列同士がマッチングしているかの記録も残すようにせよ。 宿題とする。締切りは７月１８日！