アルゴリズムと データ構造 第9回 再帰的アルゴリズム

先週の復習 探索 線形探索 2分探索 ハッシュ法 番兵による線形探索 ハッシュ法によるデータの格納・探索 衝突を処理する方法 チェイン法 オープンアドレス法 再ハッシュ(rehashing) ランダムに処理する方法

先週の演習問題 バケット数5のハッシュ表を考える．ハッシュ関数h(x)= x mod 5 を用いて,空のハッシュ表に数値データ x ={23,　48,　35,　4,　10}を格納する場合について以下の問に答えよ． （問1）　チェイン法を用いてデータを格納した場合，ハッシュ表はどうなるか？図を描け． （問2）　オープンアドレス法（再ハッシュ）を用いてデータを格納した場合，ハッシュ表はどうなるか？図を描け．

答え 23 mod 5 = 3 48 mod 5 = 3 35 mod 5 = 0 4 mod 5 = 4 10 mod 5 = 0 10 (問1)解答 (チェイン法) 23 mod 5 = 3 48 mod 5 = 3 35 mod 5 = 0 4 mod 5 = 4 10 mod 5 = 0 ポインタの配列 連結リスト 10 35 table[0] table[1] NULLの ところは斜線 バケット数 5の ハッシュ表 table[2] 48 23 table[3] table[4] 4

(問1)なぜ先頭に挿入するの？ f c a g b c a f g b 先頭への挿入なら一定時間でできる 挿入位置の計算O(1) table [0] c a [1] 先頭への挿入なら一定時間でできる g b [2] 挿入位置の計算O(n) 末尾はどこ？ table [0] c a f [1] g b [2]

再ハッシュ hi (x)= (h(x)+i) mod 5 (問2)解答オープンアドレス法 ハッシュ関数 h(x)= x mod 5 再ハッシュ hi (x)= (h(x)+i) mod 5 h(23) = 23 mod 5 = 3 h(48) = 48 mod 5 = 3 再 h1(48)=(h(48)+1) mod 5 = 4 mod 5 = 4 h(35) = 35 mod 5 = 0 h( 4) = 4 mod 5 = 4 再 h1(4)= (h(4)+1) mod 5 = 5 mod 5 = 0 再 h2(4)= (h(4)+2) mod 5 = 6 mod 5 = 1 h(10) = 10 mod 5 = 0 再 h1(10)= (h(10)+1) mod 5 = 1 mod 5 = 1 再 h2(10)= (h(10)+2) mod 5 = 2 mod 5 = 2 バケット数 5の ハッシュ表 配列 35 table[0] 4 table[1] 10 table[2] 23 table[3] 48 table[4]

　　　　　　　　　　　　第9回 　　　　　再帰的アルゴリズム

再帰の基本 再帰（recursive）とは 自然数の定義 再帰関数呼び出し 関数が自分自身をさらに呼び出す 　ある事象が，自分自身を含んでいたり，それを用いて定義されていること。 自然数の定義 （a）１は自然数である。 （b） ある自然数の直後の整数は自然数である。 このような定義を再帰的定義（recursive definition）といいます。 再帰関数呼び出し 関数が自分自身をさらに呼び出す 実際は自分自身と同じ関数を「別途」呼び出す

再帰の例：階乗値 階乗n!の定義 10! = 10* 9! 9! = 9 * 8! (a) 0! = 1 数学的帰納法で定義されるような問題は，再帰的となります。 階乗n!の定義 (a) 0! = 1 (b) n! = n × (n – 1)!　(n > 0) 10! = 10* 9! 9! = 9 * 8! int factorial(int n) { if (n > 0) return (n * factorial(n – 1)); /* 再帰的関数呼び出し */ else return (1); }

再帰の例：階乗値 再帰関数呼び出しの流れ int factorial(int n ) { if (n > 0) return ( n * factorial(n – 1)); else return (1); } factorial(3) 6 3 2 1 3 * factorial(2) 2 2 * factorial(1) 1 2 3 1 2 1 1 * factorial(0) 1

直接的な再帰と間接的な再帰 直接的な再帰： 自分と同じ関数を呼び出す。 間接的な再帰： 別の関数を呼出し， その関数が自分と同じ関数を呼び出す。 関数Ａ 　　Ａ（・・） 関数Ａ 　　Ｂ（・・） 関数Ｂ 　　Ａ（・・） 関数Ａ 　　Ａ（・・） 関数Ａ 　　Ａ（・・）

2数の最大公約数（greatest common divisor） 再帰の例：ユークリッドの互除法 2数の最大公約数（greatest common divisor） 2数を辺とする長方形を、あまりが出ないよう正方形で埋め尽くす問題 例：12と33 33 12 12 9 9 12 3 3 3 3

再帰の例：ユークリッドの互除法 最大公約数を求める手順 数学的手順 (a) 大きい方の数を小さい方の数で割ったあまりを求める (b) あまりが0になるまで、小さい方の数を大きい方の数、あまりを小さい方の数として繰り返す 数学的手順 最大公約数gcd(x, y)は、yが0ならx、そうでなければgcd(y, x % y） Ｅｕｃｌｉｄ（Ｅｕｋｌｅｉｄｅｓ） ユークリッド（エウクレィデス） （紀元前３００年ごろ） 33 12 12 9 9 12 3 3 3 3

再帰の例：ユークリッドの互除法 関数実装例 最大公約数gcd(x, y)は、yが0ならx、そうでなければgcd(y, x % y） int gcd(int x, int y) { if (y == 0) return (x); else return (gcd(y, x % y)); /* 再帰的関数呼び出し */ }

再帰呼出しを使うことのメリット 記述が簡潔になる 理解しやすくなる アルゴリズムの正しさの証明がしやすくなる 計算量の解析が容易になる

再帰的アルゴリズムの作り方 数学的帰納法で証明を書くつもりで！ 解くべき問題を、同じ問題でよりサイズの小さな問題を解くことに帰着させる。 　　（漸化式を立てる） 　　例）　mとn(m≧n)の最大公約数は、nとm%nの最大公約数と同じ。 　　　　　 gcd(m,n)=gcd(n,m%n) for n>0 最小サイズの問題の解を示す。 　　例) mとn(m≧n)の最大公約数は、m%n=0のときn int gcd(int x, int y) { if (y == 0) return (x); else return (gcd(y, x % y)); } 最小サイズの問題 より小さな問題

再帰アルゴリズムの解析 解析用関数 関数内で2度再帰呼び出し：真に(genuinely)再帰的な関数 int recur(int n) { if (n > 0) { recur(n – 1); printf(“%d\n”, n); recur(n – 2); } 関数内で2度再帰呼び出し：真に(genuinely)再帰的な関数

再帰アルゴリズムの解析 トップダウン法（top-down method） 呼び出し側から始めて段階的に詳細へと調べていく解析手法 recur(3) recur(3) 4 4 recur(2) recur(2) recur(2) recur(2) 3 3 recur(1) recur(1) recur(1) recur(1) 2 2 recur(0) recur(0) recur(1) recur(1) 2 2 recur(0) recur(0) recur(0) recur(0) 1 1 recur(-1) recur(-1) recur(0) recur(0) 1 1 recur(-1) recur(-1) recur(0) recur(0) 1 1 recur(-1) recur(-1)

再帰アルゴリズムの解析 ボトムアップ（bottom-up method）解析（n=4の場合） recur(-1) : （何もしない） → 1 recur(2) : recur(1) 2 recur(0) → 1 2 recur(3) : recur(2) 3 recur(1) → 1 2 3 1 recur(4) : recur(3) 4 recur(2) → 1 2 3 1 4 1 2

再帰を使うべきか 再帰の問題点 再帰にすべきかどうか 関数呼び出しの状態を保存しておくため、膨大なメモリが必要 関数呼び出しのオーバーヘッドなどで、計算時間が増大する可能性大 再帰にすべきかどうか 非再帰で実現できるなら非再帰を用いるべき 非再帰では複雑になりすぎるなら再帰を用いる

何でも再帰呼出しにすれば良いという訳では・・・ gcd(int m,int n) { int a[2]={m,n}, i=1,j; while(a[i]!=0) { j=(i+1)%2; a[j]=a[j]%a[i]; i=j; } return a[(i+1)%2]; gcd(int m,int n) { if( n=0 ) return m; else return gcd(n,m%n); } 再帰呼出しを 使わないと 関数の最初または最後に １回だけ再帰呼出しされる場合 ×記述は少し複雑　　　　　　 ○メモリ使用量は少ない　　 　(スタック領域の使用量が少ない) ○計算時間も短い 　(関数呼出し、復帰処理がない) ループを用いて比較的容易に かける場合が多い

再帰呼出しの時間計算量 再帰的アルゴリズムの時間計算量＝ 再帰呼出しの時間計算量 ＋ 再帰呼出し以外の時間計算量 (例） 　　　再帰呼出しの時間計算量　＋　再帰呼出し以外の時間計算量 (例） プログラム int factorial(int n) { if(n==1) return 1; else return n*factorial(n-1); } factorial(n)の実行時間をT(n)とおくと 再帰呼出しfactorial(n-1)の時間計算量=T(n-1) 再帰呼出し以外の時間計算量≦C (定数) よって　　　T(n)≦T(n-1) + C, T(1)≦C 　　　　　　　 T(n-1)≦C(n-1) したがって　T(n)≦Cn=O(n)

再帰関数の応用例 ハノイの塔 8王妃問題　

ハノイの塔 （towers of Hanoi） ハノイの塔は、フランスの数学者E・リュカ(Edouard Lucas)が 1883年に考えたものである。リュカは、インドに次のような伝 説があると説明している。 ブラフマーの塔　 インドのガンジス河の畔のベナレス（ヴァラナシ）に世界の中心を表すという聖堂がある。そこには3本の大理石の柱（ダイヤモンドの針との説もあり）が立てられており、そのうちの1本には、当初64枚の黄金の円盤が大きい円盤から順に重ねられていたという。バラモン僧たちはそこで、一日中円盤を別の柱に移し替える作業を行っている。そして、全ての円盤の移し替えが終わったときに、この世は崩壊し終焉を迎えると言われている。 もちろんこれはリュカの作り話であるが、64枚の円盤を移動させるには、最低でも18,446,744,073,709,551,615回かかり、1枚移動させるのに1秒かかったとして、約5,845億年かかる（なお、ビッグバンは今から約137億年前の発生とされている）。

ハノイの塔とは 固定された3本の柱のうちの１本に、下へ行くほど半径の大きい円盤 以下のルールで別の1本に円盤をすべて移動 重なった円盤を３本柱の間で移動する問題（３枚の場合） （より小さい円盤が必ず上にくるように重ねる） １ ２ ３ 固定された3本の柱のうちの１本に、下へ行くほど半径の大きい円盤 以下のルールで別の1本に円盤をすべて移動 1回に動かせる円盤は1枚 半径の小さい円盤の上に半径の大きい円盤は重ねられない 棒以外の部分には円盤は置けない

ハノイの塔 移動例（3枚の場合） ３ ２ １ ５ ４ ６ ７ 円盤の移動回数： 1 1 2 1 2 3 1 2 3 1 開始軸 中間軸 円盤の移動回数：　 ３ ２ １ ５ ４ ６ ７ 1 1 2 1 2 3 1 2 3 1 開始軸 中間軸 目的軸

ハノイの塔 ハノイの塔の解法 底の円盤を除いた円盤グループを開始軸から中間軸に移動 底の円盤を開始軸から目的軸に移動 円盤グループを中間軸から目的軸に移動 1.と3.で再帰呼び出し

ハノイの塔 関数実装例 void hanoi(int no, int x, int y) { if (no > 1) hanoi (no - 1, ｘ, 6 - x - y); printf(“[%d]を軸%dから軸%dへ移動\n”, no, x, y); hanoi (no - 1, 6 - x - y, y); } ・1 : 開始軸、2 : 中間軸、3 : 目的軸

8王妃問題とは 8x8のチェス盤に、8個の王妃を互いに取られないように配置 王妃は縦横斜めいずれのライン上のコマも取ることができる ラインにも別の王妃がないように 配置しなければならない 例

8王妃問題 王妃の配置 何も考えないと、64x63x62x61x60x59x58x57 = 178,462,987,637,760通り 　 = 178,462,987,637,760通り 各列に王妃を1個のみ配置と限定すると、 　 8x8x8x8x8x8x8x8 = 16,777,216通り 各行にも王妃を1個のみ配置と限定すると・・・簡単には計算できない

王妃の配置 flagを導入し、すでに配置されている行のflagを立てておく flagの立っている行には配置作業を行わない 必要のない枝分かれを抑制して、不要な組み合わせの列挙を省略：分枝限定法 注意点： １.　南西斜め筋はcol+rowが一定！ N-王妃問題を解くためのデータ構造 2. 南東斜め筋はcol-rowが一定！ 次の四つの配列で表現： 配列１：　各行に王妃が配置済みか flag_a[row] その行に王妃がいるときにFALSE、いないときにTRUE 配列２：　右上がり（／）方向に王妃が配置済みか flag_ｂ[col+row] 配列３：　右下がり（　　　）方向に王妃が配置済みか 　　　　　　　flag_ｃ[col-row+N-1] 配列４：　各列の王妃の位置 　　　　　　　pos[col]

分枝限定法よる解法 Step 1. 配列： pos[col]=row に、とりあえず王妃を置いてみる。 pos[0]=0 効き筋を埋める 考え方： とりあえず、置いてみる。 行き詰ったら、前に戻って、 別の選択肢でやってみる。 Step　1.　配列： pos[col]=row に、とりあえず王妃を置いてみる。 pos[0]=0 効き筋を埋める 次の候補は A, B, C Step　２：　とりあえずA pos[1]=2 に置いてみる 効き筋チェック 次の候補はD Step　３：pos[2]=4 に置いてみる この場合にはうまくいっていますが、次の候補がなければキャンセル して前に戻る（バックトラック） 効き筋チェック

8王妃問題を解くプログラム バックトラック

まとめ 再帰の基本 再帰関数呼び出し 再帰呼出しを使うことのメリット 再帰的アルゴリズムの作り方 再帰呼出しの時間計算量 再帰関数の応用例 ハノイの塔 8王妃問題　

演習問題