X - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第13回
最長共通部分系列
(Longest Common Subsequence)
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
S3=GTCGTCGGAAGCCGGCCGAA
• 系列 A が系列 B の部分系列であるとは，B から
0 個以上の要素を取り去ると A になること
• S3 は S1 と S2 両方の部分系列の中で最長
• 最長共通部分系列を動的計画法で求める
2
1. 最長共通部分系列の特徴付け
• LCS(X, Y) を力づく (brute-force) で解く場合
– X の全ての部分系列を生成し，それらが Y の
部分系列になっているか1つずつ調べる
– X の長さを m とすると，部分系列の数は 2m 個
– 遅すぎる
• X = <x1, x2, …, xm> とする
• X の i 番目の接頭語 (prefix) を
Xi = <x1, x2, …, xi> と定義する
3
• 定理 (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である
4
証明: (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 以上のものが作れ，
矛盾．
5
(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問題
は部分構造最適性を持つ．
6
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 のとき
7
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
8
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) 時間
9
文字列の編集距離
• 文字列 X と Y の編集距離 (edit distance) とは，
X に以下の編集操作を繰り返して Y に変換する
際の最小の操作回数である．
– 挿入: xi と xi+1 の間に文字 c を入れる
– 削除: xi を削除
– 置換: xi を文字 c で置き換える
X = ACGTT
A を削除
CGTT
C を挿入
編集距離 = 3
CGCTT
T を A に置換
Y = CGCAT
10
• X の文字を削除する代わりに，Y に gap (空白)
を入れる
• X に文字を挿入するときは必ず Y の文字を入れる
ことになる ⇒ X に gap を入れる
• X と Y に gap を入れた X’ と Y’ で，ミスマッチの数
を最小にする問題と等価
• LCS問題に似ている
X = ACGTT
Y = CGCAT
X’ = ACGTT
Y’ = CGCAT
ミスマッチ = 3
11
• 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|)
12
• 「↑」は 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
13
レポート問題
• 以下の問題からいくつか (好きなだけ) 選び
解答すること．
• 提出期限 8月20日(月)
• 提出先 [email protected] までメール
– 受理メールが来ない場合は再送してください
スライドは http://researchmap.jp/sada/ の資料公開
14
問1. (キー, データ) のペアを格納するデータ構造 D
について，以下の操作を行うことを考える
• search(D, k): D からキーが k である要素を得る
• insert(D, x): D にペア x を格納する
• delete(D, x):ペア x のポインタが与えられたとき，
D から x を格納する
なお，キーには全順序があるとする．
これらを実現するデータ構造として，
• 既ソート一方向連結リスト
• 未ソート一方向連結リスト
• 既ソート双方向連結リスト
15
• 未ソート双方向連結リスト
• 既ソート配列
• 未ソート配列
• 2色木
が考えられる．これらの各データ構造それぞれに
ついて，D の要素数が n の時の上の3つの操作の
最悪時間計算量を求めよ．データ構造の簡単な説明
も行うこと．(40点)
16
問2. ソートされた整数の配列に対し，以下の操作を
実現するプログラムを作成せよ．
(a) 指定されたキーが存在するかどうかを判定する
(b) 指定されたキーの順位 (小さい方から何番目か)
を求める．なお，指定されたキーが複数ある場合
は全ての順位を求める．
(40点)
17
問3. n 個の数をソートする場合，比較に基づくどんな
ソートアルゴリズムも (n log n) 回の比較が必要で
あることを示せ．(20点)
18
問4. n 個の整数をソートするクイックソート，マージ
ソート，挿入ソートのプログラムを実行し，n と実行
時間の関係を表すグラフを描き，考察せよ．
(40点)
19
実行時間測定の方法(C言語)
#include <stdio.h>
#include <time.h>
s2 = time(NULL);
int main(void)
x = 0.0;
{
for (i=0; i<1000; i++) {
clock_t s1, e1;
for (j=0; j<1000000; j++) {
time_t s2, e2;
x = x + (double)j;
double t1, t2;
}
int i, j;
}
double x;
e2 = time(NULL);
s1 = clock();
t2 = (double)e2 - (double) s2;
x = 0.0;
printf("x = %f time %f s.\n", x, t2);
for (i=0; i<1000; i++) {
}
for (j=0; j<1000000; j++) {
x = x + (double)j;
}
}
注: time は秒単位の
e1 = clock();
時間しかわからない
t1 = ((double)e1 - (double) s1) / CLOCKS_PER_SEC;
printf("x = %f time %f s.\n", x, t1);
20
実行時間測定の方法(Fortran)
program main
integer t1, t2, t_rate, t_max, diff
real t3, t4
integer i, j
real x
call system_clock(t1)
x = 0.0
do i = 1, 1000
do j = 1, 1000000
x=x+j
end do
end do
call system_clock(t2, t_rate, t_max)
if ( t2 < t1 ) then
diff = t_max - t1 + t2
else
diff = t2 - t1
endif
print "(A, F10.3)", "time ", diff/dble(t_rate)
call cpu_time( t3 )
x = 0.0
do i = 1, 1000
do j = 1, 1000000
x=x+j
end do
end do
call cpu_time( t4 )
print *, "time", t4-t3
end program
21
問5. 以下の問に答えよ
(a) 安定なソートとは何か
(b) 安定ではない任意のソートアルゴリズムが
与えられたとき，それを時間計算量を変化させ
ずに安定なソートアルゴリズムにする方法を
与えよ．(ヒント:各要素に何らかの情報を付加)
(30点)
22
問6. 2色木のプログラムを次のように改変せよ．
現在のプログラムでは z が左の子の場合と右の子
の場合で左右対称なほぼ同じコードが書かれている．
これを1つにまとめよ．
(ヒント: 左右の子をサイズ2の配列を使って表す)
(40点)
23
問7. 以下の問に答えよ
(a) n 個の数に対しランダムに構成された2分探索
木の高さが O(log n) であることを示せ
(b) 2色木の高さが O(log n) であることを示せ
(20点)
24
問8. 2つの文字列の編集距離を計算するプログラム
を作成せよ．
(40点)
25
最小木問題
• 節点集合 V = {1,2,…,n} と枝集合 {e1,e2,…,em}
をもつ連結無向グラフ G = (V,E) に対して，G と
同じ節点集合 V を持ち，E の部分集合 T を枝集合
とするグラフ G’ = (V,T) を考える
• 各節点 i V は少なくとも1つの枝 ej T の端点に
なっているとする
• G’ が閉路を含まない連結グラフ，すなわち木に
なっているならば， G’ を G の全域木という
• 各枝 ei E に長さ ai が与えられているとき，  ai
ei T
を全域木の長さと定義する
26
• 長さ最小の全域木を求める問題
貪欲 (greedy) アルゴリズム
• アルゴリズムの各ステップで，その時点で最善と
思われる選択を常に行うアルゴリズム
• 局所的に最善な選択が大局的に最善な解を導く
場合には最適解を与える
• 貪欲アルゴリズムで解ける問題は比較的簡単な
問題といえる
27
クラスカル法
•
•
枝を長さの短い順に1つずつ選ぶ
それを前に選んだ枝の集合に付け加えたときに
閉路を生じないならば，その枝を付け加える
(0) グラフ G の枝を短い順に並べ，枝の番号を付け
替える． A = {e1}, k = 2 とおく．
(1) 枝集合 A  {ek} が閉路を含まないならば，
A := A  {ek} とする
(2) A が G の全域木になっていれば計算終了．
さもなければ k := k + 1 としてステップ(1)へ戻る
28
3
12
8
3
11
12
9
10
8
11
9
10
15
15
3
12
8
11
9
10
3
15
8
3
11
9
10
12
8
12
15
11
9
10
15
29
• クラスカル法の計算途中では，枝集合 T は一般に
複数の木の集まりになっている．このような集合を
森と呼ぶ．
• どの枝を付け加えても閉路ができてしまうような森
を，全域森と呼ぶ．
• クラスカル法の正当性を背理法で証明する．
• 得られた全域木を T  el1 , el2 , , eln1 とし，枝は
el1 , el2 ,  , eln1 の順に付け加えられたとする．
• al1  al2    aln1が成り立つ
• T より長さの短い全域木 T *  eq1 , eq2 , , eqn1
が別に存在したとする．
aq1  aq2    aqn1 とする
30




• T* の長さは T よりも短いので， aqi  ali となる
i が存在する．
• そのような i の中で最小のものを r とすると
 a q1



a qr 1
 a qr

a l1

 a lr 1


a lr

~
• 枝集合 T  el1 ,, elr1 , eq1 ,, eqr からなる部分
~
グラフ G を考える．
~
ただし， T には枝が重複して含まれている可能性
~
もある．また，一般に G は連結とは限らない．
31
e ,, e 
~
は部分グラフ G の
• 命題：枝集合
l
l
全域森である．
• 証明：枝集合 el , , el  に枝を付け加える段階で，
eq1 ,  , eqr ではなくそれより長い el が選ばれている
ということは， eq1 ,  , eqr のどれを追加しても閉路が
できることを意味する．よって証明された．
~
• 枝集合 el , , el  が G の全域森であるため，
~
G の任意の森は r 本以上の枝を含まない
• 一方， eq1 ,  , eqr は G に対する全域木 T* の枝
~
の一部であり， G でも森になっている．しかしその
枝数は r であるため，矛盾．
• 以上より，クラスカル法で得られた T は最小木．32
r 1
1
r 1
1
r
1

r 1

アルゴリズムの効率的な実現
• 以下の操作を効率的に実現する必要がある
枝集合 A  {ek} が閉路を含まないならば，
A := A  {ek} とする
• ek = (u,v) の両端点 u, v が A の異なる連結成分
に属している ⇔ A  {ek} は閉路を含まない
• 「互いに素な集合のためのデータ構造」を用いる
33
互いに素な集合のためのデータ構造
• 互いに素な動的集合の集合S={S1, S2,…, Sk}を扱う
• make_set(x):唯一の要素xをもつ新しい集合を作る
– x がすでに別の集合に含まれていてはいけない
• union(x, y): x と y を含む集合 Sx と Sy を合併し，
それらの和集合を作る．元の集合はSから取り除く．
• find_set(x): x を含む集合の代表元へのポインタを
返す
• make_setの回数 n と全操作の総実行回数 m で
評価する．
– unionの回数は n1 以下
34
連結リストによる表現
• 各集合を連結リストで表現する
• リストの先頭のオブジェクトがその集合の
代表元の役割をする
• 各オブジェクトは集合の要素，次のオブジェク
トへのポインタ，代表元に戻るポインタを持つ
• 各リストは代表元へのポインタ head とリスト
の最後の要素へのポインタ tail を持つ
head(L)
tail(L)
9
16
4
35
• make_set(x) と find_set(x) は簡単で O(1) 時間
• union(x,y) は?
• x のリストを y のリストの最後に追加する場合
– x のリストにあった各オブジェクトの代表元への
ポインタを書き換える必要がある
– x のリストの長さに比例する時間がかかる
• (m2) 時間かかる長さ m の操作列が存在
– 初めに n 回の make_set を実行
– 次に n1 回の union を実行 (m = 2n1)
36
• このアルゴリズムはどこが悪いのか
– union(x,y) で常に x を y の末尾に追加しているので，
x が長いと時間がかかる
• x と y の短いほうを長いほうの末尾に追加すれば
計算量を抑えられる?
– 長さ n/2 同士のリストの併合は (n) 時間かかるので
最悪計算量は同じ
• ならし計算量(amortized time complexity)で評価
– m 回の操作全体での計算量で評価する
• 定理: 長さ m の make_set, union, find_set 操作の
列の実行の計算量は，その中の n 回が make_set
のとき，O(m + n log n) である．
37
証明：n 個の各要素に対し，代表元へのポインタが
更新される回数の上界を求める．
ある要素 x において，その代表元ポインタが更新
されるとき，x は常に小さい方の集合に属している．
従って，最初に x の代表元ポインタが更新された
時，得られる集合のサイズは2以上．
代表元ポインタが k 回更新された後に得られる
集合は，少なくとも 2k 個の要素を持っている．
要素は n 個しかないので，k  log n.
38
(続き)
n 個のオブジェクトを更新するのにかかる総時間は
O(n log n).
make_set と find_set 操作は1回あたり O(1),
m 回の操作全体で O(m).
従って，列全体に対する総時間計算量は
O(m + n log n).
15
2
50
4
30
20
10
1
5
80
3
15
39
クラスカルのアルゴリズム
mst_kruskal(G, w)
1. A := 
2. for v V(G)
3.
make_set(v)
4. 重み w の順に E の辺をソートする
5. for (u,v) E (重みの小さい順)
6.
if find_set(u)  find_set(v) then
7.
A := A  {(u,v)}
8.
union(u,v)
9. return A
40
クラスカル法の計算量
•
•
•
•
•
•
辺のソート: O(m log m)
make_set: n 回
find_set: 2m 回
union: n1 回
素な集合の操作全体で O(m + n log n)
m = O(n2) より
クラスカル法の計算量は O(m log n)
41

Download Report