alg2015-4r2.ppt

Transcription

1 1 アルゴリズムとデータ 構造 第 4 回基本的なデータ構造 ( ヒープ ) 再帰的アルゴリズム 2017/04/18 アルゴリズムとデータ構造

2 2 リスト リストとは要素を 0 個以上 1 列に並べたもの リスト a 0,a 1,,a n-1 の実現法 1. 配列 (array) 前回の復習 (1/3) a 0 a 1 a n-1 2. 連結リスト (linked list) init a 0 a 1 a n-1 null 3. 双方向連結リスト (doubly linked list) init null a n-1 null final a 0 a 1 配列は i 番目の要素への位置付けが容易 ( 双方向 ) 連結リストは挿入 削除が容易 i 番目の要素への位置付け挿入 or 削除 配列 O(1) O(n) ( 双方向 ) 連結リスト O(n) O(1)

3 3 リストの応用 前回の復習 (2/3) スタック 要素の挿入 削除がいつも先頭からなされるリスト LIFO(last-in-first-out) a 2 PUSH(a2,S) POP(S) a 2 a 2 TOP(S) a 1 a 1 a 1 a 0 a 0 a 0 待ち行列 ( キュー ) 要素の挿入は最後尾 削除は先頭からなされるリスト FIFO(first-in-first-out) ENQUEUE(a 2,Q) a 0 a 1 a 2 TOP(Q) a 0 a 1 a 2 DEQUEUE(Q) a 0 a 1 a 2

4 proc PUSH( x: elementtype; var S: stack); begin if S.top := 1then writeln("error!"); else begin end end. S.top := S.top - 1; S.element[S.top] := x; top element F E D C B A

5 5 前回の復習 (3/3) キューの配列による実現 すべての操作の時間計算量は O(1) Q TOP(Q) = front j rear (j+i)%n 0 n-1 a i a 0 a 1 ENQUEUE(a i+1,q) front j rear (j+i+1)%n 0 n-1 Q a 0 a 1 a i a i+1 DEQUEUE(Q) front (j+1)%n rear (j+i+1)%n 0 n-1 Q a 1 a i a i+1 バリエーション rearを最後尾の次のインデックスとする rearを保持せずに要素数 numを保持し rearは毎回 (front+num-1)%nで計算しなおす 空( カラ ) か 空きなし かの判断は? 要素数 numを保持する場合はnum=0であれば空 ( カラ ) num=nであれば空きなし 要素が入っていない状態を表す特別な値( 要素として現れない値 ) で配列を初期化し DEQUEUEのときに取り出した位置を初期化する ENQUEUEの時 追加しようとした位置に要素が格納されていれば空きなし 要素の数をn-1までしか格納しない rear=(front-1)%nであれば 空 ( カラ ) rear=(front-2)%nの場合には 空きなし と判断する

6 配列で巡回リストを表わす. キューの長さ n が限定された場合 先頭と末尾がつながって, 輪になったリスト 要素の位置を,n の剰余演算で決定 Element A 4 A 5 A 1 A 2 A 3 rear front front から i 番目の要素 = Element[ (front + i) mod n ] ex. Elem[(head + 5) mod n] (head = 1 and n = 6) = Elem[7 mod 6] = E[1]

7 1 element front 3 rear A B C D E F

8 優先度つき待ち行列 応用

9 A.

10 Priority Queue linked list DELETEMIN( A ) O( n ) INSERT( x, A ) O( 1 ) DELETEMIN( A ) O( 1 ) INSERT( x, A ) O( n ) Header a 1 a 2... a n

11 11 疑問 DELETEMINとINSERTの両方の演算をもっと効率良く実現できないか?

12 ヒープ (heap)

13 13 ヒープ (heap) 英語 : 山積み という意味.

14 14 優先度付き待ち行列 ( ヒープ, heap) * 初心者注意 集合 X 上の全順序 (total order, 線形順序 (linear order)) とは X 上の要素間の 2 項関係 ` で 次の性質をもつものをいう (1) x x for all x X ( 反射律, reflexivity) (2) x y, y z x z ( 推移律, transitivity) (3) x y, y x x=y ( 反対称律, anti-symmetry) (4) x y or y x for all x,y X ( 比較可能性, comparability) 全順序 ` が定義されている集合の要素を節点にもつ木で次のような条件を満たす 2 分木 ( 各節点の子の数が高々 2 つの木 ) を考える ヒープ条件任意の節点 u に対して u の親の要素 u の要素 が成り立つ

15 15 i-2 i-1 i i+1 i+2 ヒープの定義 y y = = y x x x ヒープ (heap, 順位付きキュー (priority queue)) とは A[i] の親をA[ (i-1)/2 ] として定義される2 分木がヒープ条件を満たす配列 A ( 例 )

16 16 ヒープの基本操作 ( 最小要素の削除 ) 実行例 DELETEMIN(A) 最小 ( 根にある ) 要素の削除 (n: 削除前の要素数 ) Step 1 A[0] A[n-1], i 0 Step 2 2i+1 n-1 ならば停止 そうでなければ j argmin k {2i+1,2i+2},k<n A[k] とする Step 3 A[i] A[j] ならば停止 そうでなければ A[i] と A[j] の中身を入れ替え i j として Step 2 へ i i j 12 i Step 2 停止 i Step Step 1 5 i 7 8 j Step Step Step 3 5 i 5 i 7 8 j Step Step 2

17 17 ヒープの基本操作 ( 要素の追加 ) 実行例 INSERT(x,A) 要素の追加 (n: 追加前の要素数 ) Step 1 A[n] x, i n Step 2 i=0 ならば停止 そうでなければ j (i-1)/2 とする Step 3 A[i] A[j] ならば停止 そうでなければ A[i] と A[j] の中身を入れ替え i j として Step 2 へ Step 3 停止 i i Step 1 j Step j i Step i i Step j 2 Step 3 Step i

18 18 ヒープの基本操作の時間計算量 * 初心者注意 DELETEMIN(A), INSERT(x,A) ともに 各 Step は定数時間で実行可能 Step 2 と Step 3 の間のループの回数のオーダーで実行可能 1 回の繰り返し毎にDELETEMINはiの位置が1つずつ深くなっていく INSERTは iの位置が1つずつ浅くなっていく 最悪 木の高さの回数だけループする 要素数 n のヒープを 2 分木で表現した場合 木の高さは log 2 n である 証明してみよう! DELETEMIN(A) と INSERT(x,A) の最悪時間計算量は O(log n)

19

20 整列問題の解法 : ヒープソート

21

22 22 再帰呼出し 再帰呼出しとは 関数がその定義の中でそれ自身を呼び出すこと 再帰的アルゴリズムとは 再帰呼出しを用いて記述されたアルゴリズム

23 23 再帰的アルゴリズムの例 最大公約数を求めるアルゴリズム ( ユークリッドの互除法 ) 2 つの自然数 m,n(m n) の最大公約数は gcd(m,n) Euclid(Eukleides) ユークリッド ( エウクレィデス ) ( 紀元前 300 年ごろ ) gcd(int m,int n) { int r=m%n; if( r=0 ) return n; else return gcd(n,r); } 実はもっと簡潔に以下のようにも書ける gcd(int m,int n) { if( n=0 ) return m; else return gcd(n,m%n); }

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

25 25 再帰的アルゴリズムの作り方 数学的帰納法で証明を書くつもりで! 1. 解くべき問題を 同じ問題でよりサイズの小さな問題を解くことに帰着させる ( 漸化式を立てる ) 例 ) m と n(m n) の最大公約数は n と m%n の最大公約数と同じ gcd(m,n)=gcd(n,m%n) for n>0 2. 最小サイズの問題の解を示す 例 ) m と n(m n) の最大公約数は m%n=0 のとき n

26 26 何でも再帰呼出しにすれば良いというもでは gcd(int m,int n) { } if( n=0 ) return m; else return gcd(n,m%n); 関数の最初または最後に 1 回だけ再帰呼出しされる場合 ループを用いて比較的容易にかける場合が多い 再帰呼出しを使わないと 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]; } 記述は少し複雑 メモリ使用量は少ない ( スタック領域の使用量が少ない ) 計算時間も短い ( 関数呼出し 復帰処理がない )

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

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