Document

Basic Algorithms
• 再帰呼び出し
• 分割統治とバランス化
• グラフ探索
• 列挙法
• 動的計画
再帰呼び出し
サブルーチンを作る
• サブルーチンとは、いわばプログラムの部品
• プログラム実行中、そこに行き一定の処理をして、またもとの
場所に帰ってこれる
• 通常プログラムを作る際には、作業を階層的に「部品化」し、
設計をやりやすくする
－作業単位がわかる
－全体の見通しがよくなる
• サブルーチンを実行することを、呼び出すという
再帰呼び出し
• 通常の部品の概念では、部品の中に同じ部品が入ることはない
• しかし、サブルーチンは、自分自身を呼び出せる
(サブルーチンが自分自身を呼び出すことを再帰呼び出しという)
• 自分を呼び出すと、サブルーチンの最初から、呼び出すところま
でを繰り返すループになる
 for ループと同じものが作れる
sub (int i){
printf (“%d\n”, i); // i の値を表示
if ( i<100 ) sub(i+1);
}
練習問題
• 次のループを再帰呼び出しで書け。擬似コードでよい
－ 10 から 20 までを表示
－ 50 から 20 までの偶数を表示
－ 1,2,…,9,10,10,9,…,1という順番で数字を表示。ただし、ひ
とつのサブルーチンで
－ m×n の長方形を “#” で表示
複数回の再帰呼び出し
• for ループは単純に繰り返すだけだが、再帰呼び出しは、１つ
のサブルーチンが自分を複数回呼び出すことができる
sub (int i){
printf (“%d\n”, i); // i の値を表示
if ( i<100 ){
sub(i+1);
sub(i+1);
}
}
• どのように動くのだろうか？
 1レベル目が1回、2レベル目が2回、3レベル目が4回、と
指数的に実行解数が増える
２分木のような計算構造
• １つのサブルーチン実行を１つの点で書き、再帰的に呼び
出した関係があるところに線を引く
• ２分木の構造が得られる
• ３回呼び出せば３分木、
４回呼び出せば４分木、
• 呼び出しの回数が変化すれば、より複雑な構造になる
 いろいろな計算ができる
組合せ的な処理の例
• 例：8文字の○×△からなる文字列を全て表示
char s[9];
sub (int i){
if ( i = = 8 ){
s[8] = 0;
printf (“%s\n”, s); // ○×△ の表示
} else {
s[i] = ‘o’; sub(i+1);
s[i] = ‘x’; sub(i+1);
s[i] = ‘A’; sub(i+1);
}
}
組合せ的な検索
• 再帰呼び出しの計算構造は、（逆さにした）木のようである
• このような、計算の構造を表した木を計算木、あるいは再帰
木という
• このように、処理を分けることを分枝するという
分枝の例
• a[0],…,a[9] の組合せで、合計がちょうど b になるものを表示
int a[10], flag[10];
sub (int i, int s){
int j;
if ( i = = 10 ){
if ( s != b ) return;
for (j=0 ; j<10 ; j++ )
if (flag[j] = = 1) printf (“%d ”, a[j]); // 数の表示
printf (“\n”);
} else {
flag[i] = 1; sub(i+1, s+a[i]);
flag[i] = 0; sub(i+1, s);
}
}
分枝限定法
• 分枝操作を行うと、全ての組合せを検索できる
• しかし、全ての組合せのうち、一部しか見る必要がないのであ
れば、全て見るのは無駄
• 見る必要のない部分を省略したい
• 分枝作業をした後、「見る必要のない再帰呼び出し」は呼び出
さないようにしよう
• 必要（可能性）のない分枝を切ることを、限定操作という
限定操作をしながら分枝する方法を、分枝限定法という
限定操作の例
• a[0],…,a[9] の組合せで、合計が b 以下になるものを表示
int a[10], flag[10];
sub (int i, int s){
int j;
if ( s > b ) return; // 限定操作！
if ( i = = 10 ){
for (j=0 ; j<10 ; j++ )
if (flag[j] = = 1) printf (“%d ”, a[j]); // 数の表示
printf ("\n");
} else {
flag[i] = 1; sub(i+1, s+a[i]);
flag[i] = 0; sub(i+1, s);
}
}
分割統治とバランス化
問題の分割
• 人間が問題を解く（作業をする）場合、問題なりやることなりを
分割して、小さくしてやることがある
 見通しを良くする、という点と、やりやすくする、という点
• 例えば、部屋の片づけのしかた
－まず、各部屋にしまうものを分類
－次に各部屋の中を、個別に整理
• さらに各部屋の片づけをする際に、本棚や机、それぞれにし
まうものを集めてから、それぞれをやっつける
• このように再帰的に問題を分割して解く方法を分割統治法と
いう
分割統治法の構造
• 分割統治法を、手法としてしっかり見てみる
• 問題が与えられると、
－まず、問題を分割できるように整形する
－問題を分割する（できた問題を子問題という）
－各子問題を解く（再帰呼び出し）
－各子問題の解を合わせて、もとの問題の解を作る
• 問題によっては、必ずしも全ての手続きが必要なわけではない
分割統治法の例
• 先の、再帰呼び出しの例はだいたい分割統治法といってよい
• 合計がちょうど b になる組合せを求める
 i 番目の数を含む組合せを求める問題と、そうでない組合
せを求める問題に分割している
 整形と分割、統合に関して、複雑な処理が必要ない
ソート
• 分割統治法を使うと、効率良く解ける問題がいくつかある
• 基本的な例がソート
• 数値 a[0],…,a[n] を小さい順に並び替える問題を考える
• 戦略として、次の手順を考える
－まず、数値を a[0],…,a[k] と a[k+1],…,a[n]に分割する
－それぞれをソートする
－ソートしてできた列を合わせて、全体のソート列を得る
（この操作をマージ（合併・併合）という）
－この操作を再帰的に行うことで、ソートをする
マージの例
•例題 1,9,5,3,7,6,2,0,8,4
－ 1,9,5,3,7,6 と 2,0,8,4 に分割
－それぞれをソートする： 1,3,5,6,7,9 と 0,2,4,8
－マージする（両者を同時に先頭から見ていく）
1,3,5,6,7,9 と 0,2,4,8
0,1,2,3,4,5,6,7,8,9
•マージは線形時間でできる
マージをするプログラムの例
•配列 a,b の数列をマージして、配列 c に格納
•配列 a,b の最後に、大きな数 HUGEが入っているとする
{
int ia, ib=0, ic=0;
for ( ia=0 ; a[ia]<HUGE ; ia++){
while (b[ib]<a[ia] ){
c[ic] = b[ib]; ic++;
ib++;
}
c[ic] = a[ia]; ic++;
}
}
マージソートをするプログラムの例
•配列 a,b 両方に数列を格納しておくと、配列 a にソートした列が入る
merge_sort (int *a, int *b, int s, int t){
int i1, i2, ia;
if ( s = = t ) return;
merge_sort (b, a, s, (s+t)/2 );
merge_sort (b, a, (s+t)/2, t);
for ( i1=s,i2=(s+t)/2,ia=s ; i1<(s+t)/2 ; i1++){
while ( i2<t && b[i2]<b[i1] ){
a[ia] = b[i2]; ia++; i2++;
}
a[ia] = b[i1]; ia++;
}
while ( i2<t ){
a[ia] = b[i2]; ia++; i2++;
}
}
再帰呼び出しの様子
• マージソートの再帰呼び出しの様子は、２分木になる
merge_sort (int *a, int *b, int s, int t){
int i1, i2, ia;
if ( s = = t ) return;
merge_sort (b, a, s, (s+t)/2 );
merge_sort (b, a, (s+t)/2, t);
for ( i1=s,i2=(s+t)/2,ia=s ; i1<(s+t)/2 ; i1++){
…
分割は、「同じ大きさ」が正解？
• 先ほどのマージソートは配列をだいたい同じ大きさに分割して
いたが、もっといい分割はあるか？
 分割のしかたを変えると、速さは変わるのか？
• まず、２つ目の疑問は、Yes
• マージソートの各反復の計算時間は、ソートする配列の大きさ
に線形 O(n)
• もし、毎回「１個と残り」という分割をすると、配列の長さは毎
回１ずつ小さくなる
 計算時間は 1＋・・・+n に比例、つまり O(n2)
「同じ大きさ」が正解
• 毎回ちょうど半分に分割すると、配列の長さは毎回半分＋１
以下になる
 O(log n) 回分割すると長さが１になる
 各レベルで計算時間を合計すると、 O(n) になるので、合計
はO(nlog n)
• 分割の仕方で計算量のオーダーが変わった
• これは最適なんだろうか？
 ソートの計算時間の下界と一致するので、最適
分割すればいい、と言うものではない
• 分割ができるからといって、分割統治法を使えば速くなる、と
いうものでもない
 a[1],…,a[n] の中から最大のものを見つける問題は、分割し
ても解けるが、速くならない
－ a[1],…,a[k] と a[k+1],…,a[n] に分割してそれぞれの最大
を再帰的に求める
－両最大値のうち、大きいほうを全体の最大値として返す
• 計算木の各頂点で O(1) しか時間
をかけないので、どう分割しても
O(n) 時間になる
クイックソート
• マージソートは、分割前に何もせず、分割後にがんばる
－まず、問題を分割できるように整形する
－問題を分割する（できた問題を子問題という）
－各子問題を解く（再帰呼び出し）
－各子問題の解を合わせて、もとの問題の解を作る
• 逆のアイディアでソートができないか？
• クイックソートと言う方法がある
分割の前にがんばる
• まず、数値をある数 k より大きなものと小さなものに分割する
k
• それぞれを小さい順に並べる
• 終わると、全体が小さい順になっている
k との大小で分割
• 数値を k との大小比較で分割するにはどうすればいいか？
－右からスキャンして k より小さいものを見つけて止まる
－左からスキャンして k より大きいものを見つけて止まる
• 両者を入れ替える
• 繰り返す。スキャンしている場所がすれ違ったら終わる
分割のバランスがとれない
• k の値によって、分割してできる子問題の大きさは変わる
• しかし、真ん中の値（中央値）を見つけるのは、簡単ではない
• しょうがないので、適当なものを選ぼう
 最悪の場合、１つと残り、という分割を繰り返すので
計算時間は O(n2) になる
• しかし、例えば、分割が 1:9 以上になる確率は 2/10 で、
こういうことは、起こりにくい。そんな分割がたくさん起こること
は、なおない。平均的には、 O(nlog n) になる
合計が最も大きい区間を求める
• a[0],…,a[n-1] の区間 a[h],…,a[k] 中で、合計が最も大きいも
のを求める (負の値があると、全体＝最大とはかぎらない)
• 実験の時系列データの解析など？
 各区間の取り方は O(n2) なので、素朴に計算すると O(n3)
時間になる
 各区間の合計の計算の仕方を工夫する（左端を固定して、
右側をひとつずつずらし、新しく入ってくる要素を今までの合
計に足し込む）と O(n2) になる
• 分割統治法を使うと、速く解ける
分割して計算
① a[0],…,a[n-1] を a[0],…,a[k-1] と a[k],…,a[n-1]に分割
② 右端が a[k-1] となる区間の中で最大を求める
③ 左端が a[k] となる区間の中で最大を求める
 a[k] と a[k] を両方含む区間の中で最大なものは、②と③ を
合わせると求まる
④ 再帰呼び出しで、a[0],…,a[k-1] の中の最大と、a[k],…,a[n-1]
の中の最大を求める
• ①と②と③ はO(n) 時間
 問題を半分に分割するようにすれば、マージソートと同じ計算
量になり、全体の計算時間は O(nlog n)
～余談～： k番目を線形時間で見つける
• クイックソートは、問題を分割するときに、だいたい真ん中にな
る数が知りたい
• こういう、数の中から k 番目にあるものを見つける問題を k
best 問題という
• 簡単にやろうとしたら、数字をソートすればよい
（本末転倒だが）
• だが、凝った方法で、ソートせずに線形時間の方法がある
～余談～： k番目を線形時間で見つける２
• 入力した数を a[0],…,a[n-1] とする
• 基本的な戦略は、数 x を選び、 a[0],…,a[n-1] を x をより大き
なものと小さなものに分ける
• x より小さいものが k 個以上あったら、k 番目はx より小さい
 x より小さいものの中で k 番目を見つける
• x より大きいものが k 個以上あったら、k 番目はx より大きい
 xより大きいものの中で n-1-k 番目を見つける
• という具合に小さくしていく。効率は x の選び方しだい
～余談～： k番目を線形時間で見つける３
• x を選ぶのには、「いいかげんな」中央値を使う
（クイックソートにも、いいかげんな中央値で十分だが）
• a[0],…,a[n-1] 中を７個ずつに分け、それぞれの７個の中で中
央値を見つける（定数時間が n/7 回で O(n) 時間）
• 見つけた中央値の中でさらに中央値を見つける
（1/7 の大きさの問題を再帰的に解く）
• これは、真ん中 1/4 以上はじっこに行くことはない
（3/4 の大きさの問題を再帰的に解く、上と合わせて 25/28 ）
～余談～： k番目を線形時間で見つける４
• それぞれの７個の中で中央値より、半分のものは大きい
大
小
• 半分のもののさらに半分は、●より大きい
• 半分のもののさらに半分は、●より小さい
• よって、真ん中 1/4 以上はじっこに行くことはない
～余談～： k番目を線形時間で見つける５
• 問題の大きさの合計が、毎回 25/28 になる
• 問題を分けるのにかかる時間は O(n)
• 全体の計算時間は
O(n + (25/28)n + (25/28)2n + (25/28)3n …)
＝ O(n）
行列積の計算量
行列のかけ算
• 行列の積を求める演算は、行列の操作の中でも基本的なもの
だが、計算に比較的時間がかかる（次元の3乗のオーダー）
• うまいことやって、もっと速くできないだろうか？
×
＝
分割統治法は使えるか？
• ソートでは、問題を分割して高速化した。行列も問題を分割し
たらうまく解けるかも
• うまいことやって、もっと速くできないだろうか？
• 分割するといっても、どのように分割する？どのように解く？
• まずはどのように分割するか、分割した問題をどのように解く
かを考えないと
×
＝
簡単な分割
• 左の行列は横長の行列２つに、右の行列は縦長の行列２つに
分けてみよう
• 横長と縦長の行列の組合せ１つの積を求めると、答えの1ブロ
ックが埋まる
 4回積を求めると、もとの行列の積が求まる
• でも、「正方行列の積」が「正方でない行列の積」になるので、
気持ちが悪いなあ
×
＝
もう少し分割
• 両行列ともに４つに分割する
• 1/4 ブロックの積を２つ求め、足すと、1ブロック埋まる
 正方行列の積を8回求めると、もとの行列の積が求まる
 同じ問題を解いているので、再帰呼び出しできる
• さて、これは速くなっているのでしょうか？？？
解析してみないと、よくわからない。。。
A
B
E
F
×
C
D
＝
G
H
AE
+BG
CE
+DG
AF
+BH
CF
+DH
計算時間の再帰式
• 計算が再帰的なので、計算時間の再帰式を作ろう
• この方法で n 次元行列のかけ算をする時間を T(n) とする
• 問題を分割したり、積の足し算をして解を求める時間は O(n2)で
あるので、定数を使って、cn2 時間であるとする
• 再帰は、大きさ n/2 の問題について 8回行われるので、
T(n) = cn2 + 8T(n/2)
となる
A
B
E
F
×
C
D
＝
G
H
AE
+BG
CE
+DG
AF
+BH
CF
+DH
計算時間の再帰式
• T(n) = cn2 + 8T(n/2) を満たす関数 T(n) とは、どのような関数で
あろうか？
• 図示して考えてみよう
（簡単のため、n = 2k であるとする）
• 大きさ n の問題を受け取ったら、cn2 の計算時間をかけ、 8 個の
大きさ n/2 の問題に関して再帰呼び出しが起こる
• （8個の）大きさ n/2 の問題は、それぞれ c(n/2)2 の計算時間をか
け、それぞれ 8 個の、大きさ n/4 の問題を作る
• （64個の）大きさ n/4 の問題は．．．（以下省略）
• （？？？個の）大きさ 1 の問題が呼び出される
計算時間の再帰式
• 大きさ n の問題を受け取ったら、cn2 の計算時間をかけ、 8 個の
大きさ n/2 の問題に関して再帰呼び出しが起こる．．．
• 1レベル下がると大きさは 1/2 になり、計算時間は 2倍に増える
 全体の計算時間は一番下のレベルの2倍を超えない
• k = log2n レベル下がると、問題の大きさが 1 になり、再帰呼び
出しは起こらない
 そのレベルでの計算時間の合計は cn2 ×2k = cn3
• 計算時間は、O(cn3)
• 苦労したのに何もかわらないや。。。
再帰式、一般的には
• T(n) = cn2 + 8T(n/2) の n2 の部分や、8 の部分、n/2 の 2 の部分
が変化すると、関数 T(n) のオーダーも変化する
• どのように変わるか、少し調べてみよう
• n2 の部分、8 の部分が変わると、1レベル下がったときの計算時
間の増加量が変わる
－ 8 の部分が 2 になると、1レベル下がると計算時間が半分に
 全体の時間はトップレベルの2倍を超えず、O(n2)
－ 8 の部分が 4 になると、各レベルでの計算時間は等しくなる
 全体の計算時間はトップレベルの高さ倍となり、O(n2 log n)
再帰式、一般的には
－ n2 が n になると 1レベル下がるごとに計算時間は4倍になる
 一番下のレベルの計算時間の合計はトップレベルの n2 倍
になる。しかし、トップレベルの計算時間が O(n) であるので、掛
け合わせると O(n3)
－ n2 が n4 になると、1レベル下の計算時間は半分になる
 全体の計算時間はトップレベルの2倍を超えず、 O(n4)
－ n2 が n3 になると、各レベル下の計算時間は等しくなる
 全体の計算時間は O(n3 log n)
再帰式、一般的には
－ n/2 が n/4 になると、1レベル下がるごとに計算時間は1/2に
なり、さらにレベルの高さが半分に
 計算時間の合計はトップレベルの２倍以下。O(n2)
－ n/2 が n/4 になり、n2 が n になると、1レベル下がるごとに計
算時間は2倍になる。レベルの高さが半分になる
 一番下のレベルでは、トップレベルの n1/2 倍。O(n3/2)
再帰式、一般的には
• 一般に、T(n) = cna + bT(n/c) という再帰式が成り立つとき、
－ a > logc b ならば、トップレベルが全体の計算時間を支配し、
計算量は O(na) となる
－ a < logc b ならば、一番下のレベルが全体の計算時間を支配
し、計算量は O(nlogc b) となる
－ a = logc b ならば、各レベルの計算時間は等しくなり、計算量
は高さのファクターが入り、O(nalog n) となる
行列積の高速化
• 先の問題の分割では、答えの行列をブロックごとに求めていた
 その結果、8回のかけ算を必要としている
 行列積は a < logc b （2 < log2 8）の場合であるので、
再帰呼び出しの回数 8 を減らすか、子問題の大きさ n/2 を小さく
しなければならない
• 工夫して、再帰の数、つまりかけ算の数を減らした人がいる
A
B
E
F
×
C
D
＝
G
H
AE
+BG
CE
+DG
AF
+BH
CF
+DH
分配則の利用
• 行列を足してからかけると、行列積の和が得られる
例） (A + B)E = AE + BE B(G – E) = BG – BE
• これらをうまく組合わせて足し合わせると、目的である行列積が
出てくる
例） (AE + BE) + (BG – BE) = AE+BG
A
B
E
F
×
C
D
＝
G
H
AE
+BG
CE
+DG
AF
+BH
CF
+DH
再帰式の変化
• うまい和積取り方と組合せ方を考えて、7回の行列積で、4つのブ
ロックの解が得られるようにした
• 計算時間の再帰式は、T(n) = cn2 + 8T(n/2) から
T(n) = cn2 + 7T(n/2) になった
• log2 7 = 2.80… なので、およそ O(cn2.80) 時間になる
• この方法で一番すごいやつは、100個以上の行列に分解して同様
のことを行い、O(cn2.31…) 時間を達成
A
B
E
F
×
C
D
＝
G
H
AE
+BG
CE
+DG
AF
+BH
CF
+DH
疎な行列のかけ算
疎な行列のかけ算はどうなる？
• 疎な行列は、疎な持ち方をすると効率が良い
• 疎な持ち方にあったかけ算の仕方をしたとき、計算時間はオ
ーダーの意味で改善されているのかな？
 最悪の場合、全部のセルに値が入るので、改善されない
• しかし、疎な行列に興味があるので、行列の疎性に応じた速
さの評価がしたい
• 行列の大きさの他に、非ゼロのセルの数を使って、行列積の
計算時間を評価してみよう
行ごとに格納
• 各要素へのアクセスを良くするため、少々構造をつけよう
• まずは、1 である要素を、行ごとに分類し、記憶
 配列を n 個用意し、そこに各行にある 1 である要素の場
所（列番号のみ）を記録
• 配列が n 個必要になったので、n個メモリが必要だが、行番
号を記録しなくてよくなったので、その分節約できる
• これで、使用するメモリは、「1の数」＋行の数×2（ほんとは１
にできる）になった。
• アクセスも良くできる。各行の位置を小さい順に並べれば、２
分探索できる（１行の要素数が小さければスキャンで十分）
ベクトルの内積
• 疎なベクトルの内積計算をする
• 各行（ベクトル）を、添え字の小さい順に並びかえておく
• 内積を取るベクトル２つを、小さいほうから同時にスキャンする
同時に、の意味は、同じ値、あるいは両者を混ぜ合わせて小さ
い順に並べたときに隣り合う要素を常に見ている、ということ
• 両方とも非ゼロであるところが見つかったら、その要素の積を
答えに加える
1 5 5 1 7 3
1 1 3 3 5 4
疎行列積の計算時間
• 左側の行列の各行について、右側の各列との内積を取る
 各 i 行につき、① その行が n 回スキャンされ、左側行列
の各列が1回ずつスキャンされる
 （i 行の大きさ）×n + （右行列の大きさ）
• これを各行について行い、時間の合計を取ると
（左行列の大きさ）×n + （右行列の大きさ）×n
• 行列の大きさ（非ゼロのセル数）が n2 よりもオーダーの意味
で小さければ、計算量の改善がある
バケツを使った方法
• バケツを使った行列転置の計算方法と同じアイディアを使うと、
もう少し速くできる
• 左行列の第 i 行と右行列の各列の内積を取る問題を考える
（i 行と j 列の内積を p(i,j) と表記する）
• 第 i 行の非ゼロ要素が、l1,…,lk 番目にあるとする
• p(i,j) を各 j について計算するには、各 l=l1,…,lk について、
第 i 行の l 番目の要素と、第 j 列の l 番目の要素の積を求
め、その総和を計算すればよい
バケツを使った方法
• バケツを使った行列転置の計算方法と同じアイディアを使うと、
もう少し速くできる
• 左行列の第 i 行と右行列の各列の内積を取る問題を考える
（i 行と j 列の内積を p(i,j) と表記する）
• 第 i 行の非ゼロ要素が、l1,…,lk 番目にあるとする
• p(i,j) を各 j について計算するには、各 l=l1,…,lk について、
第 i 行の l 番目の要素と、第 j 列の l 番目の要素の積を求
め、その総和を計算すればよい
計算する部分を図示
• 第 i 行の非ゼロ要素のある位置 l1,…,lk に対応する行を見る
• 各列について、要素の積を計算する
第i行
右側の行列
計算の順番を変える
• 各列について、緑の部分にある非ゼロ要素を見つけるのは多
少手間がかかる（ゼロである要素を何度もチェックする）
• 各l 行について積を計算するのならば楽
• つまり、第 i 行のl 番目の要素
に対して、各列のl 番目の要素
との積を計算するならば楽
• 計算した積は、各列の下にある
箱に足し込めばよい
 全ての行についてスキャンすると
箱の中身はその行の内積の値になる
第i行
右側の行列
行のスキャンにも疎性を
• i 行のl 番目の要素と、各列のl 番目の要素との積を計算
 各列のl 番目が非ゼロであるところのみ、計算すればよい
（そうでないところは、積は 0 になるから）
• 右側の各行について
非ゼロである要素の位置を
覚える方式で行列を記録すると、
スキャンするのが楽
第i行
右側の行列
計算時間
• 左側の行列の各 i 行の非ゼロ要素がある位置、l について、
右側の行列のl 番目の行をスキャン
• 左側の行列の各 i 行についてこの操作を行うと、行列の積の
計算ができる
• そのとき、右側の行列の第 j 行は、左側の行列の第 j 列にあ
る非ゼロ要素の数だけ、スキャンされる
• 右側の行列の第 j 行の
大きさを S(j)、左側の行列の
第 j 列の大きさを T(j) とすると
計算時間は S(j)×T(j) 時間
T(j)
S(j)
計算時間
• そのとき、右側の行列の第 j 行は、左側の行列の第 j 列にあ
る非ゼロ要素の数だけ、スキャンされる
• 右第 j 行の大きさを S(j)、左第 j 列の大きさを T(j) とすると
－第 j 行に関する計算時間は S(j)×T(j) 時間
• 全体では Σi S(j)×T(j) 時間
－各行・列の大きさが
定数なら O(n) 時間
－行・列の大きさがべき乗則
に従うなら、(次数が2以上の
とき) O(n) 時間
T(j)
S(j)
逆行列の計算（行列の三角化）
逆行列
• 行列の A の逆行列 A-1 の定義は
A-1 が AA-1 = I （単位行列）を満たすこと
（逆行列 A-1 は A が非退化／フルランク／正規／non-singlarであ
るときのみ存在）
• A から A-1 を求めるのが、逆行列を求める問題
（黄色の行列の要素が何であるか求める問題（方程式を解くような
もの））
1
×
＝
1
1
・・・
1
1
連立方程式へ
• 求める黄色の行列の i 行 j 列の要素を xij とおくと、A と黄色行列
の掛け算をすると、解の各要素には線型方程式が入る
例）解の 1行1列 a11xij + a21x12 + ・・・ + an1x1n
• 解の行列が、単位行列になるように xij を決めると、 A-1 が求まる
例）解の 1行1列 a11xij + a21x12 + ・・・ + an1x1n が 1 になるように xij
を定める  方程式を解いているのと同じ
x11 x12 ・・・ x1n
x21 x22 ・・・ x2n
×
1
＝
xn1 xn2 ・・・ xnn
1
1
・・・
1
1
連立方程式を解く
• 解の i 行 j 列 a1jxi1 + a2jxi2 + ・・・ + anjxin = 1 （あるいは0）
こういう方程式が n2 本ある
• 一方、変数の数は n2 個  退化していなければ解ける
• 線型方程式なので、代入していけば解ける
 それを機械的にやるようにすれば、アルゴリズムができる
x11 x12 ・・・ x1n
x21 x22 ・・・ x2n
×
1
＝
xn1 xn2 ・・・ xnn
1
1
・・・
1
1
１つずつ代入
• こういう方程式を解くときは、ある変数について方程式を解き、そ
れを残りに代入する
例） a1jxi1 + a2jxi2 + ・・・ + anjxin = 1
 xi1 = (1 － (a2jxi2 + ・・・ + anjxin)) / a1j
• こういう操作をやって、すべての変数を消せばよい
• 1行1列から順に代入を使って変数を消すアルゴリズムができる
x11 x12 ・・・ x1n
x21 x22 ・・・ x2n
×
1
＝
xn1 xn2 ・・・ xnn
1
1
・・・
1
1
計算時間
• 1つの変数を消すには、代入の式を作り（O(n2)時間）、それを他の
全ての式（O(n2)個）に代入（O(n2)時間）
 変数は n2 個あるので、O(n6) 時間
逆行列はO(n6) 時間で求められる
• 次に、もう少し速い方法を紹介しましょう
x11 x12 ・・・ x1n
x21 x22 ・・・ x2n
×
1
＝
xn1 xn2 ・・・ xnn
1
1
・・・
1
1
行列の基本変形と三角化
• 行列のある行の○○倍を他の行に足すのが行列の基本変形
 左から、その列と行の要素を○○にした単位行列をかけるこ
とと同じ
• 対角成分の上（下）部分にしか非ゼロの数が入っていないとき、
その行列は上三角行列（下三角行列）という
1
1
1
・・・
1
1
LU分解
• 行列の下の行に上の行（の○○倍）を足して、上三角化行列を作
る（行列の基本変形をする）
• 行列の基本変形を表す行列をかけると、非ゼロ部分を重ね合わ
せた行列になる、ので、
• 全ての基本変形を掛け合わせると、下三角行列ができる
（（このように上・下三角行列に分解することを、LU分解という）
1
1
1
1
×
・・・
1
1
1
1
1
＝
・・・
1
1
1
1
・・・
1
1
LU分解で逆行列を
• 三角化した行列下の逆行列は簡単に求まる
 方程式を作ると、解行列の一番下の行では、変数が１つしか
ないので、簡単に解ける。その結果を代入すると、下から2番目
の行が解ける、、、という具合になる。
• 左から三角行列の逆行列をかけて、逆行列を求める方程式を簡
単な方程式に変形してしまおう
1
1
1
1
×
・・・
1
1
＝
1
1
・・・
1
1
逆行列を
• 三角化した行列で表した逆行列の方程式に、左から基本変形行
列の逆行列をかける
 左側の三角行列がキャンセルして消える
• 解きやすい形になりました
 三角化できていれば、行列積（O(n3)）と代入（O(n3)）の時間
（O(n3)）で逆行列が求まる
A-1
A
-1
×
-1
×
×
＝
1
× ・・・1
1
行列の基本変形と三角化
• 上の行の定数倍を下の行から引く
 下の行の特定の要素が消せる
－ 1列目を使って、それより下の行の1列目を消す
－ 2列目を使って、それより下の行の2列目を消す
…
とすれば、上三角行列になる（基本変形の行列は下三角）
A
＝
×
三角化の計算時間
－ 1列目を使って、それより下の i 行の1列目を消す
 1列目の要素が同じ大きさになるように、
1行目に a1j /a11 を掛け、それをi 行から引く
• 各行について、O(n2) 時間でできる。全部の行について計算
すると O(n3) 時間
逆行列はO(n3) 時間で求められる
A
＝
×
疎な行列だと？
• 「1行目に a1j /a11 を掛け、それを i 行から引く」
• この操作で、 i 行のゼロ要素が一部非ゼロになる（ fill in という）
 何回も行うと、多くのゼロだった要素が非ゼロになり、密になる
• 現実的には、 fill in がなるべくおこらないように、行・列を入れ替
えておけばいい。例えば、上の行、左の列が疎になるようにとか
A
＝
×
グラフ探索
探索問題
• 自分のいるところから到達可能なところを全て調べる問題を
考える（これを探索とよぶ）
• 例えば、グラフ・ネットワークで、現在地から到達できるところ
を全部調べる
 行けるとは、枝をたどって移動すること
• グラフの中で、ある頂点から到達可能な頂点を全て調べる問
題・調べることをグラフ探索という
どういう戦略をとるか
• 有向グラフ G=(V,A) の頂点 v から到達可能な頂点を全て出
力する
• 素朴にするなら、全ての頂点に対して、v から到達可能かどう
か調べる
 v から到達可能でないことを確認すること自体が、ある種、 v
から到達可能な頂点を全て調べることに対応
• 迷路を調べるように、たどっていけるところを少しずつ広げて
いくほうがいいだろう
迷路を解くには？
• 迷路を解く（迷路でいけるところを全部調べる）にはどうする
か？
－出発点から始め、道（枝）をたどる。分かれ道は適当に選ぶ
－行き止まりに来たら、前の分かれ道まで戻って、行ってない
方に行く
－行ってないほうがなくなったら、さらに戻る
－一回行ったことのあるところに出たら、引き返す
• 右手法は、立体交差があるとだめ、入り口と出口が外につい
ていないとだめ、なので、少々不完全
グラフバージョン
• 迷路を解く方法を、グラフに焼きなおそう
－出発頂点から始め、枝をたどる。各頂点で、次に進む枝は
適当に選ぶ
－探索してない枝がない頂点に来たら、前の頂点まで戻って、
行ってない枝に行く
－行ってない枝がなくなったら、さらに戻る
－一回行ったことのある頂点に来たら、引き返す
• 「行ったことのある頂点、たどったことのある枝」を覚えておく
必要がありますね
• あと、各頂点に対して、「どの頂点からきたか」も
来たことあるか、を記憶
• 「行ったことのある頂点、たどったことのある枝」を覚えておく
• 行ったことのある頂点は、各頂点にフラグを用意しておく
フラグ＝０  行っていない
フラグ＝１  行ったことがある
• さらに、「どの頂点から来たか」も一緒に記憶できる
フラグ＝-1 or NULL など  行っていない
フラグ＝それ以外
 直前にいた頂点
• 枝も同じようにして覚えられる、がそうしなくても、もっといい方
法がある
順番に枝をたどる
• 各頂点に隣接する枝は、番号順か何かで、１つずつたどれる
としよう（隣接リスト、隣接配列などで）
• 最後にたどったのは何番目の枝かを覚えておき、次に枝をた
どるときは、その次をたどる
• 頂点の数だけのメモリしかいらない
プログラムを書く
• グラフの探索のための、データはそろった
• さて、アルゴリズム（プログラム）はどうしようか
• 各頂点で何をするか考える
 接続する枝をたどる
 訪問済み（行ったことある）だったら、戻る
 訪問してなかったら、先を探索する
 行った先の頂点でも、同じように枝をたどる
 行った先から帰ってきたら、次の枝を調べる
同じか。じゃあ、再帰呼び出しだ
再帰呼び出しで書く
• 再帰呼び出しの各サブルーチンでは何をするか
• 頂点を与えると、
－接続する各枝に対して、その先を探索するよう、再帰呼び
出しをする
－ただし、訪問済みならば再帰呼び出ししない
－全部の枝を調べたら、サブルーチン終了  自動的に、もと
来た頂点に戻る
• どこから来たか、を覚えなくてよくなり、仕組みが簡単になりま
した
再帰呼び出しによるコード
• deg[v] は vの次数、edge[v] はv に隣接する頂点の配列
• flag[v] は v の訪問済みマーク。最初は全部0にしておく
int flag[n], edge[n][];
DFS (int v){
int j;
flag[v] = 1; // v に訪問済みマークをつける
for ( j=0 ; j<deg[v] ; j++){
if (flag[edge[v][j]] = = 0 ) DFS( edge[v][j]); // 訪問済みでなければ
再帰呼び出し
}
}
再帰呼び出しを使わないコード
• deg[v] は vの次数、edge[v] はv に隣接する頂点の配列
• flag[v] は v の訪問済みマーク。最初は全部 -1 にしておく
int flag[n], k[n], edge[n][];
DFS_ (int v){
int j, vv=v;
for ( j=0 ; j<n ; j++){ flag[j] = -1; k[j] = 0; }
flag[v] = v; // 最初の頂点だけ、自分から来たことにする。特別
while (1){
if (k[v] = = deg[v] ){
if (flag[v] = = vv ) return; // 最初の頂点の枝を全部たどったら終了
v = flag[v]; // そうでなければ、もときたところに戻る
} else {
if (flag[edge[v][k[v]]] < 0 )
{flag[edge[v][k[v]] = v; v = edge[v][k[v]]); } // 枝をたどる
}
}
}
深さ優先
• 先ほどの探索方法は、先へ先へと探索を進めていく
いわば、深いほうをどんどんたどる
• つまり、最後に見つけた頂点の隣を調べている
 スタックと考え方が同じ
• じゃあ、スタックを使ってアルゴリズムをつくろう
 新しく訪れた頂点に隣接する頂点で、訪れたことがないもの
をスタックに入れる
 そして、スタックから頂点を取り出す
 ある頂点から先の探索が終わると、次に探索するべき頂点
が、スタックの最後にある
スタックを使ったコード
DFS_ (int v){
int j;
STACK S;
for ( j=0 ; j<n ; j++) flag[j] = -1;
STACK_init ( &S, n);
// スタックの初期化
STACK_push ( &S, v);
// スタックに最初の頂点を挿入
flag[v] = 1;
while ( S->t > 0){ // スタックが空になるまで繰り返す
STACK_pop (S, &v); // スタックから頂点を取り出す
for ( j=0 ; j<deg[v] ; j++ ){ // 接続する枝を順番に調べる
if (flag[edge[v][j] < 0 ){
flag[edge[v][j] = v; // もと来た頂点を v に設定
STACK_push (&S, edge[v][j]) } // 訪問していなければ、スタックに入れる
}
}
}
STACK_end ( &S );
// スタックの解放（終了操作）
}
探索の順番
• 先ほどの探索方法は、いわばスタック的に新しい頂点を見つ
ける
• それが、迷路をたどる操作とちょうど等価になっている
• しかし、コンピュータは物理的に「たどる」必要がないので、探
索していない頂点なら、実はスタックに入っている頂点、どれ
を選んでもいい
 ランダムに選んでもいい
 探索済みの領域をじわじわと広げていくイメージ
• スタックの代わりにキューを使ってもいい
探索の順番
• キューは、最初に入れたものが最初に出てくる
 探索に使うと、出発点の近くが早くにキューに入る
つまり、優先されて探索される
• こういった、次に探索する頂点をキューに入れて探索する探
索法を幅優先探索という
• 対して、先ほどのスタックを使うものは、深さ優先探索とよば
れる
幅優先探索の性質
• 幅優先探索を実行すると、
• まず出発点に隣接する頂点（距離１の頂点）がキューに入る
• 次に、距離１の頂点に隣接する頂点（距離２の頂点）がキュー
に入っていく
 これら距離２の頂点は、距離１の頂点が全部なくなってから、
キューから出てくる
 そのとき、距離２の頂点は全部キューに入っている
 距離２の頂点が全部キューに入ってから、距離２の頂点が処
理される
 以後、距離kの頂点が全部キューに入ってから、距離k+1の頂
点が処理される
距離の計算
• つまり、幅優先探索を使うと、出発点からの距離がわかる
（出発点から頂点までの、移動に使う枝の最小）
• 各頂点をキューに入れるときに、その頂点の距離を、今の頂
点の距離＋１にする
• これより短く行くことはできないので、これが正しい距離になる
出てくる
キューを使ったコード
BFS (int v){
int j;
QUEUE Q;
for ( j=0 ; j<n ; j++) flag[j] = -1;
QUEUE_init ( &Q, n );
// キューの初期化
QUEUE_ins ( &Q, v );
// キューに最初の点を挿入
flag[v] = 0;
while ( Q->s != Q->t){ // キューが空になるまで繰り返す
QUEUE_ext ( Q, &v ); // キューから頂点を取り出す
for ( j=0 ; j<deg[v] ; j++ ){
if (flag[edge[v][j] < 0 ){
flag[edge[v][j] = flag[v]+1; // 距離を v までの距離 +1 に設定
QUEUE_ins (&Q, edge[v][j]) } // 訪問していなければ、キューに入れる
}
}
}
QUEUE_end ( &Q );
// キューの解放（終了操作）
}
列挙アルゴリズム
列挙問題
• 列挙問題とは、与えられた問題の解を全て出力する問題
 さっきから出てきている例は、列挙問題
－入力した数の組合せで、合計がある範囲にあるものを全て
出力する
－入力グラフに含まれるパスを全て見つける
－入力グラフに含まれるクリークを全て見つける
－大きさ k までの２分木を全て出力する
－入力した文字列の部分文字列で、複数回現れるものを全て
見つける
－入力した数列の中から部分降順列を全て見つける
• 列挙問題を解くアルゴリズムを列挙アルゴリズムという
列挙アルゴリズムの評価
• 列挙問題は自然に、指数個の解を持つ
 出力にかかる時間だけで指数時間なので、多項式時間の
議論ができない
• そこで、「出力の大きさ」もパラメータとして考え、計算時間が
入力と出力の大きさの多項式であるとき、出力多項式時間と
いい、列挙アルゴリズムの効率性の指標にする
• ただ、実際は出力が非常に大きいことが多いので、解１つあ
たりの計算時間（入力の多項式時間）で評価することも多い
遅延
• 列挙問題の解の数は、計算してみないとわからない
 出力多かったり、時間がかかったりする
• 時間がかかる場合、途中でやめる、という選択肢があるが、
それならば、早めになるべく多くの解が手に入るほうがいい
• そこで、解が１つ出てから次の解が得られるまでの計算時間
の最大値を遅延（あるいは遅延時間）と定義し、それで早め
に解が出てくるかどうかを評価する
 出力多かったり、時間がかかったりする
• 遅延が入力の多項式なら多項式遅延、今まで見つけた解の
数、と入力の多項式なら逐次多項式時間

Download Report