アルゴリズムとデータ構造 講義スライド 木 グラフ 茨城大学工学部知能システム工学科井上康介 E 棟 8 号室
木とは リスト構造では枝分かれは起こらなかった. 枝分かれしながらデータが伸びていくデータ構造を木 (tree) と呼ぶ. 木はノード (node) とそれらを結ぶ枝 (branch) から構成される. データが記録されているのはノードであり, 枝はデータとデータの間の親子関係を示す. A ノード B C 枝 D E F G H p.-
木とは あるノードから下に分岐した先のノードを子, 分岐元のノードを親という. 木の一番最初のノードを特に, 根 (root) と呼び, 子を持たないノードを葉 (leaf) と呼ぶ. A 根 親 B C 子 D 親 E F 子 子 G H 葉
木とは あるノードから下につながった木構造の全体を部分木 (subtree) という. 根からあるノードに到達するまでに通る枝の数をそのノードの深さ (depth) といい, 根から最も深いノードまでの深さを木の高さ (height) という. A 深さ 部分木 B C 深さ D E F 深さ 深さ G H この木の高さ=
木とは ノードからの分岐が 以下の木を 分木 (binary tree) と呼ぶ. 親と子の関係が, ある規則 ( 大きい, 小さいなど ) に従って並べられている木を 分探索木 (binary search tree) という. 8 A 分木 B 9 C D E F I G 9 H 左の子 親 右の子
木とは 木構造はきわめて重要で, 多くの実用的対象が存在する. 組織データやファイルシステムなどの階層構造の表現 AI における論理的関係性の表現 探索を容易にする情報表現 ( 分探索木など ) ヒープ ソート 講義では, 分探索木およびヒープに重点を置いて解説する.
分探索木の配列表現 ノードに格納するデータが人名であるとき 名前を辞書順 に並べる分探索木が作れる 全ての親と子の間に 左の子 親 右の子という関係が成 立する 右側の子のノード番号 No. achilda No. No. Candy No. No. Ann No. Rolla No. Emy Nancy No. Eluza Lisa このようにノード番号を管理すれば 配列に格納できる p.8-8
分探索木の配列表現 各ノードに格納する情報は 人名 左の子へのポインタ (ノード番号) 右の子へのポインタ (ノード番号) のつで ある これを構造体にまとめ 配列にする struct tnode { int left; char name[]; int right; }; // 左部分木へのポインタ(番号) // データ(人名) // 右部分木へのポインタ(番号) 8
分探索木の配列表現 この配列を使って 分探索木を表現できる ただし nil はポインタが指し示すものがないという意味 で 具体的には - などを使う a[p].left a[p].name a[p].right No. achilda No. No. Candy No. No. Ann No. No. Emy Nancy No. Eluza Lisa Rolla achilda Candy Rolla nil nil Ann nil Emy nil Nancy nil nil Eluza nil nil Lisa nil 二分探索木の配列表現 9
分探索木の配列表現 分探索木から key という目的データを探すには root から初めて key がノードのデータより小さいときは左側 の木へ, 大きいときは右側の木へ探索すればよい 実質的に二分探索 O(log n) の計算量 a[p].left a[p].name a[p].right key が Eluza の場合 No. achilda No. No. Candy No. No. Ann No. No. Emy Nancy No. Eluza Lisa Rolla achilda Candy Rolla nil nil Ann nil Emy nil Nancy nil nil Eluza nil nil Lisa nil 二分探索木の配列表現
二分探索木の配列表現 (ソースコード) p.9 このコードでは 分探索木を初期化において与えてい る nil は - と定義 (プリプロセッサ) scanf() で key を読み込み p を (根ノード) で初期 化 p が nil にならない限り続けるループに入る strcmp() を使って 今見ているノード p の名前欄と key を照合し 合致していたら発見したことを表示して ループを抜ける もし key の方が小さいときは p を a[p].left に 逆の場合は p を a[p].right にする
分探索木へのデータの追加 先程の例では, 最初から 分探索木ができていたが, これを作るアルゴリズムが必要 すでに存在する 分探索木に対して, 新しいノードを追加する手順は, 以下の 段階を踏む 新ノードの親となるノードを探索 新ノードを親ノードに接続 現在調べているノードの番号を視点 p とし, この視点に一つ遅れで追従する視点 old も用意する p を進めていき,p が nil になったとき,old が指し示しているノードが新ノードの親
分探索木へのデータの追加 p=; while (p!=nil){ old=p; if (strcmp(key,a[p].name)<=) p=a[p].left; else p=a[p].right; } a[sp].left=a[sp].right=nil; strcpy(a[sp].name,key); if (strcmp(key,a[old].name)<=) a[old].left=sp; else a[old].right=sp; sp++; sp: key: Nancy Patie p: - p old achilda - p old Candy - - - p old - Rolla Nancy - - Patie -
分探索木の動的表現 リストの場合と同様 ツリーもノードが動的に追加される データ構造である 従って 自己参照構造体としてノードを表現し 必要に応 じてメモリを動的に確保するのが適している struct tnode { struct tnode *left; /* 左部分木へのポインタ */ char name[]; /* 名前 */ struct tnode *right; /* 右部分木へのポインタ */ }; struct tnode *talloc(void) { return (struct tnode *)malloc(sizeof(struct tnode)); }; p.8-8
新規ノード作成手順 (コードを見つつ) 配列表現の時と同様 () 新規ノードの親となるノードの 探索 () 新規ノードの生成と親ノードからの接続を行う. Candy を追加 Emyを追加 視点 p を root で初期化 p:null p は新規データ dat の大小にした p=p->left がって木をたどり old は一つ遅れ p old achilda で追従 old=p としてから p を old->left=p 適切な方向へ進める p old p=p->right Candy p が NULL なら old が親ノード old->right=p p p=talloc()としてデータ記入 Emy 左右の子はいない NULL に 親ノードの名前と新ノードの名前の大小関係により 親ノードの左右どちらかのポインタを p に向ける
分探索木の動的表現 ( ソースコード ) まずはルートノード作成 root=talloc(); scanf("%s",root->name); root->left=root->right=null; root achilda
分探索木の動的表現 (ソースコード) while (scanf("%s",dat)!=eof){ p=root; while (p!=null){ old=p; if (strcmp(dat,p->name)<=) p=p->left; ここから下 p は else 視点 ではなく p=p->right; 新規ノード位置 } を示す p=talloc(); strcpy(p->name,dat); p->left=p->right=null; if (strcmp(dat,old->name)<=) old->left=p; else old->right=p; } 第ノード以降作成 (さきほどの手順) root dat: Rolla Nancy p: NULL p old achilda p old Rolla p Nancy
分探索木の再帰的表現 (集中して聞くこと) 木構造は再帰的処理に向いている 例えば探索の場合 rootノード (achilda) 以下から Emy を探す と いう問題は root->left (Candy) 以下の部分木から Emy を探す という副問題に 分解 できる root この中からの探索 この中か らの探索 再帰の脱出条件 発見 or 行き先が NULL (不在) (例 Eluza) achilda Rolla Candy Ann p.8-88 (途中まで) Emy 8
ノード追加の再帰的方法 (集中して聞くこと) 既存の 分探索木に新しいデータ w を含むノードを追加す る処理を再帰的に記述することを考える 再帰関数のプロトタイプを以下の通りとする struct tnode *gentree(struct tnode *p, char w[]) p 起点ノード (このノード以下が作業対象) w 追加するデータ (名前) その動作は条件により異なる p が NULL ではないとき ノード p の適切な方の子 ノードを起点として gentree()を再帰呼び出しし 受け取ったポインタ p をそのまま返す (オウム返し) p が NULL のとき 新規ノードを作り w を格納 作った新規ノードへのポインタを返す 9
ノード追加の再帰的方法 ここでは データ Nancy を含むノードへの ポインタを [Nancy] と表記する root main() root = gentree(root, Emy ) 呼出 Nancy [Nancy] 第 引数が NULL 以外 適切な子を起点とする 再帰呼び出し 第一引数をオウム返し 第 引数が NULL 新規ノードを作成 新規ノードへのポイ ンタを返す gentree([nancy], Emy ) 同じポインタを上書き 元の構造を壊さない [Nancy]->left = gentree([nancy]->left, Emy ); 呼出 [Candy] gentree([candy], Emy ) NULL Candy [Candy]->right = gentree([candy]->right, Emy ); 呼出 Emy [Emy] gentree(null, Emy ) ノード作成 戻り値の利用方法 に注目
ノード追加の再帰的方法 同じ方法で 第一ノード (root ノード) 作成も できるだろうか root main() root = gentree(root, Nancy ) 呼出 [Nancy] 第 引数が NULL 以外 適切な子を起点とする 再帰呼び出し 第一引数をオウム返し 第 引数が NULL 新規ノードを作成 新規ノードへのポイ ンタを返す gentree(null, Nancy ) Nancy ノード作成 作ったノードへのポインタを返す 第一ノード作成もそれ以降も root = gentree(略) でOK 二分探索木の生成は root を NULL で初期化し root = gentree(略); を 繰り返せば全部できる void main(void) { char dat[]; struct tnode *root; } root = NULL; while (scanf("%s",dat)!= EOF){ root = gentree(root,dat); }
ノード追加の再帰的方法 (ソース) struct tnode *gentree(struct tnode *p, char *w) { if (p == NULL){ p = talloc(); 新規ノード作成 strcpy(p->name, w); p->left = p->right = NULL; p 新規ノード } else if (strcmp(w, p->name) < ) 適切な子の選択 p->left = gentree(p->left, w); 再帰 else 子ポインタへの代入 再帰呼出 呼出 p->right = gentree(p->right, w); return p; p 第一引数そのまま } ポインタを返す (新ノードを作ったときはそれへのポインタ そうでないときは 受け取った第一引数 p を (いじらずそのまま) オウム返し)
分探索木のサーチ (再帰版) while (printf("search name -->"), scanf("%s",key)!=eof){ if ((p=search(root,key))!=null) p=search(root,key)) printf( %s printf("%s が見つかりました n,p->name); が見つかりました n",p->name); else printf("見つかりません n"); printf( 見つかりません n ); } key: Nancy Rolla p struct tnode *search(struct tnode *p,char *key) struct tnode *search(struct tnode *p,char *key) *p,char *key) { struct tnode *search(struct tnode (p: マチルダ) { (p: ローラ) (p: NULL) {if (p==null strcmp(key,p->name)==) if (p==null strcmp(key,p->name)==) if (p==null return p; strcmp(key,p->name)==) return p; return p; if (strcmp(key,p->name)<) if (strcmp(key,p->name)<) if (strcmp(key,p->name)<) return search(p->left,key); return search(p->left,key); elsereturn search(p->left,key); else else return search(p->right,key); return search(p->right,key); return search(p->right,key); } } } achilda p Rolla p: NULL
分探索木のトラバーサル (深さ優先) トラバーサル (traversal) 木の全てのノードを訪れるこ と (木の走査) (例 大学組織データ内からの教員捜し) 深さ優先探索 左向きにとにかく進んで 端に来たら つ前の親に戻って右に進む という行動を繰り返す 再帰的に記述すると 関数 treewalk(p)は 以下のよう な動作をすれば良い (p 起点ノードへのポインタ) void treewalk(struct tnode *p) { p が NULL なら戻る (終了条件) if (p!=null){ p の左の子を起点として再帰呼出 treewalk(p->left); printf("%s n",p->name); p での作業 (ノード内容表示) treewalk(p->right); p の右の子を起点として再帰呼出 } } 8
分探索木のトラバーサル (深さ優先) ノード内容表示の順序次第で 表示順序が変わる 行きがけ順 void treewalk(struct tnode *p) { if (p!=null){ printf("%s n",p->name); treewalk(p->left); treewalk(p->right); } } p NULL p achilda p p Emy p Rolla p Candy 画面表示 Lisa achilda Emy Candy Lisa Rolla 9
分探索木のトラバーサル (深さ優先) ノード内容表示の順序次第で 表示順序が変わる 通りがけ順 void treewalk(struct tnode *p) { if (p!=null){ treewalk(p->left); printf("%s n",p->name); treewalk(p->right); } } p NULL p achilda p p Emy p Rolla p Candy 画面表示 アルファベット順 Lisa Candy Emy Lisa achilda Rolla
レベルごとのトラバーサル (試験範囲外) 木のレベル (深さ) ごとに さらに同一レベルでは左から 右にノードをトラバーサルするには 配列 (TODOリスト) で実現 配列 q G BH A D CF E copy BH D CF E 配列 w G レベル終了時に配列 w が空なら終了 A レベル B C E D G レベル F H 教科書でこの配列を スタック と呼んでいるのは間違い レベル レベル
ヒープ ヒープ (heap 山 堆積) とは すべての親が必ずつの 子を持つ (最後の要素は左の子だけでも良い) 完全分木で どの親と子をとっても 親 子になっている木を言う 配列表現 ノードを深さごとに 左から順に配列に格 納する 9 ヒープにおいては添え字は でなく から始める 8 こうすると 子 s の親 p は p=s/ で求まる 8 9 9 8 例 /= (整数演算) 8 p.- 9
ヒープへのデータ追加 (上方移動) 既に存在するヒープへ新規データを追加することを考える その手順は以下の通りである () 新しいデータをヒープの最後の要素として格納する () その要素を子とする親のデータと比較し 親の方が大 きければ子と親を交換する () 次に その親を子とする親 (おじいちゃん) との間で 比較を行い 必要があれば交換 これを 子の位置が根ま で上がるか 親 子になるまで繰り返す 教科書 p. の図.を参照せよ この手順を上方移動 (shift up) という ソースコードは p..
ヒープへのデータ追加 (上方移動) () 新しいデータをヒープの最後の要素として格納する () その要素を子とする親のデータと比較し 親の方が大きければ子と親 を交換する () 次に その親を子とする親 (おじいちゃん) との間で比較を行い 必 要があれば交換 これを 子の位置が根まで上がるか 親 子になる まで繰り返す 9 8 9 s= 9 p=
ヒープの作成 (下方移動) 上方移動では既存のヒープにデータを一つずつ追加することに よりヒープを作成したが 既存の全データをそのまま分木に 割り当ててから ヒープとして整えるという方法がある その 手順は以下の通り (教科書は分かりにくい) () 子を持つ最後の親 (データ数が n のとき n/) i から開始し 全ての親に対して逆順に (n/, n/-, n/-,, ) 以下の () () の手順を繰り返す () 親の番号を p とし ２つの子 (p, p+) のうちで小さい方を s とする (一番最後の親は 左側にしか子を持たない場合がある この場合は自動的に s = p とする.) () 子 s の値が 親 p 以上なら () のループで次へ () p と s の値を交換し 交換された子の方を親として (p = s s = p) () へ戻る
ヒープの作成 (下方移動) 図的に理解しよう () 子を持つ最後の親から開始してループ (最初は 9/ = から) () 親の番号を p とし p と p+ で小 さい方の子を s とする () s が p より大きいときは () ループで 次へ i= p= 8 s= 8 8 9 () p と s を交換し p=s, s=p とする 8 9 s>n なら () ループで次へ s<=n なら () へ 8 () から () の手順を 下方移動 (shift down) と呼ぶ ソースコード p.
ヒープ ソート ヒープを用いたソーティングアルゴリズムがヒープ ソー トである 手順は大まかに以下の通り ()与えられた数列からヒープを作成する ()根ノードには最小値が来ているはずなので, これを取り外 す その代わり 最後のノード (データ数 n なら n番の要 素) を切り離して根ノードに持ってくる ()これにより残ったデータ (n-個) のヒープ条件が狂った ので 下方移動を使ってヒープの修正を行う. この場合 根ノードからの回の下方移動を行うだけでよい ()() に戻る 教科書 p.8 の図. を参照せよ 計算量のオーダは O (n log n) p.8-
ヒープ ソート (ソースコード) p.9 関数 swap() はつの配列要素の交換 main関数内 最初の whileループは初期ヒープの作成 データを入れるごとに 入れたデータを最後尾に格納した 上で 上方移動を使ってヒープを整える作業を繰り返して いる つめの whileループは データを取り出すごとのループ 最初にルート (番) と最後尾 (n番) を交換して 最後尾 をヒープから除外している (n--) 次のループは 視点 p を根に初期化して下方移動を回 行っている部分 p. では 初期ヒープ作成を下方移動で行っている 8
第章 グラフ リスト構造は ノード群を鎖状につないだもので 分岐は なかった 一方木構造は分岐はするが 分岐した枝同士は 分かれたまま これらをより一般化したものがグラフ (graph) である グラフでは ノード間の連結は任意であり ループを含む こともある 8 p.- 9
グラフとは 円で描いた部分はノード (node 節点 vertex 頂点ともい う) であり それを結んでいるのは エッジ (edge 辺 branch 枝) である ノードとはつながっているが とはつながっていない エッジ ノード 8
グラフとは グラフをデータとして表現するときに使われるのは隣接行 列 (adjacency matrix) である ノード i と j の間に接続 がある場合は ない場合は としておく 教科書ではノード番号はからとしている j 8 対角成分は 同じノードへの接続をあると するかどうかに関係する (この場合はなし としている) 8 i 8
グラフとは ここまでの例では グラフのエッジには向きはなかった このようなものを無向グラフ (undirected graph) という これに対して, 進める方向 のような向きを含んだグラ フを有向グラフ (directed graph) という この場合 隣 接行列は ノード i から j へのエッジに対して 要素 (i, j) は 要素 (j, i) は としておく (p. 図.) 8
深さ優先探索 グラフのノードにデータが記載されている場合 この中か ら特定のデータを探すとき グラフの全てのノードを巡る というアルゴリズムが必要となる その一つは 深さ優先探索 (depth first search, 縦型探索 とも呼ばれる) である ()始点を出発し ノード番号の若い順に進む位置を調べ い けるところ (エッジで連結されていてまだ訪問していない ノード) まで進む ()行き場所がなくなったら まだいける方向の残っている分 岐点まで戻り 再びいけるところまで進む ()行き場所が全てなくなったら終了 (来た道を戻る) p.-8
深さ優先探索 どのように探索が進むかを図で見てみよう () 始点を出発し ノード番号の若い順に進む位置を調べ いけるところ (エッジで連結されていてまだ訪問していないノード) まで進む () 行き場所がなくなったら まだいける方向の残っている分岐点まで戻 り 再びいけるところまで進む () 行き場所が全てなくなったら終了 (来た道を戻る) 8
深さ優先探索の再帰的解法 深さ優先探索を再帰 的に行う関数は右の 通り 未探索の行き先を順 番に探して 行ける ときは再帰呼び出し でそこに進む visit()を呼ぶと void visit(int i) { int j; } v[i]=; for (j=;j<=n;j++){ if (a[i][j]== && v[j]==){ printf("%d->%d ",i,j); visit(j); } } j= j= j= j= 8 8 j= j=
深さ優先探索 (ソースコード) 次元配列 a[][] によって隣接行列を記述 (初期化) これ がグラフの実体である 配列 v[n+] は 訪問済みフラグ を意味する これが となっているノードは未訪問 なら訪問済み main関数では訪問フラグの初期化の後 visit() を呼び 出しているだけ 関数 visit() は再帰的関数であり 引数 i は探索を開始 するノードの番号 要するに ノード i から先を探索せ よ という関数 visit() では まず起点ノード i の訪問済みフラグを立て る (にする) 次に他の全てのノード j を調べ ノード i とつながっており (a[i][j]==) 未訪問 (v[j]==) な らば, ノード j を起点として探索 (再帰呼出 visit(j))
深さ優先探索の応用 グラフ上の各ノードを起点として深さ優先探索を繰り返す 場合は 各探索の前に訪問済みフラグを下ろして置かなく てはならない p. 図. のように ノード群が分かれているグラフを 非連結グラフと呼ぶ これがどのように分かれているかを 調べるには 訪問済みフラグのリセットをせずに 各ノー ドを起点とする探索を繰り返せばよい 探索の起点となるノードが訪問済みの場合は次のノードへ 進む 訪問済みでないときは カウントをつ進める これにより カウント数 分かれている集団の数となる
幅優先探索 幅優先探索 (breadth first search 横型探索とも言う) で は これから進まなくてはならないノードのメモ を キューの中に保存し それを参照しながら探索を進める ()始点をキューに入れる ()キューからノードを取り出し そのノードに連結している 未訪問のノードを全てキューに入れておく ()キューが空なら終了 そうでないときは () へ これにより 始点から近いノードから順序よく探索が進め られる p.9-8
幅優先探索 ()始点をキューに入れる ()キューからノードを取り出し, 訪問済みとする. そのノー ドに連結している未訪問ノードを全てキューに入れておく ()キューが空なら終了 そうでないときは () へ ソースコード p.- 8 キュー 8 9
トポロジカル ソート グラフを見ると から仕事を始めたとき やができる ためには, が出来ていなければならないのと同時 に 右側では,, 8 が出来ていなければならない 教科書に誤植 つまり,,,, という系列と,,,, 8, とい う系列がある 従って の次に行いうる仕事 とでは どちらを先に行っても良い このように必ずしも順序を比 較できない場合がある順序関係を半順序関係 (partial order) という p.- 8
トポロジカル ソート 半順序関係が与えられたデータに対して 最初に行う仕事 から最後に行う仕事を列に並べることをトポロジカル ソート (topological sort) という どちらを先にやっても良い部分が含まれているので 解は つとは限らず どれかが得られればよい 8
トポロジカル ソート 有向グラフに対する深さ優先探索を繰り返し実行し 行き 着いたところから来た道を戻ろうとするときに そのノー ドを記録していけばよい 記録は 最後に行き着く場所 から順に行われるので逆 順 8 8
Euler の一筆書き 辺を消しながら深さ優先探索を行い, 出発点に戻った時に全ての経路が消えていれば, そのとき通った経路が求める経路である スタック v[n] ソースコード :p. p.8-
ネットワーク 各辺に重みが定義されているグラフを 重み付きグラフ あるいは ネットワーク (network) と呼ぶ 重みの意味は 例えば道路網については道路の長さであっ たり 水道網なら流量だったりである (p.9 図.) 8 データの実体は 重み行列 で 記述する e b a f d c g h 8 ( 無限大)
最短路問題 (Dijkstra のアルゴリズム) 解きたい問題 ノード a から h までの最短距離を求める 全てのノードの確定フラグを下ろし, 距離値を無限大で初期化 スタートノードの距離値を とする (), () を N 回繰り返す 距離値最小の未確定ノードの番号を p とし 確定フラグを立てる p につながる全ノードについて p から進んだときの距離値が現在の 距離値より小さくなるとき そのノードの距離値を更新する あるノードの距離値を更新するとき 距離値だけでなく この距離値に e なる場合 直前のノードはこれ と b いう 手前ノード情報 も記録する f 距離だけでなく経路も求まる () () () () a c p.-9 d g 9 h
最短路問題の例 障害物環境下での移動ロボットのナビゲーション コンフィギュレーション障害物の頂点をサブゴールとし, 可視グラフ (visibility graph) を構築, 最短路を探索 sub-goal obstacle start obstacle goal 移動ロボットのナビゲーションを主にやってるとこ : 城間研 configuration obstacle
講義のおわりに 本講義では, 知能システム工学科の趣旨に則って, メカと情報の融合分野を扱う上でのアルゴリズム データ構造を実践的に ( ソース コードをベースとして ) 解説した. 情報工学科における同名の講義とは異なり, 理論的な議論はほとんど行っておらず, 情報に興味のある学生にとっては不十分である. 一方, 組み込みシステムなど, ハードウェアに近いプログラミングでは, マイコンや電子回路など, 多くのハードウェアに関する知識が必要となる. それらについては, 各自が必要に応じてより深く勉強すること. 本講義は基礎の基礎しか扱っていない. 講義終了後もアルゴリズム データ構造に関する質問は随時受け付ける.