茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室

Presentation on theme: "茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室"— Presentation transcript:

1 茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室
アルゴリズムとデータ構造 講義スライド 4 木 グラフ 茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室

2 木とは リスト構造では枝分かれは起こらなかった．枝分かれしながらデータが伸びていくデータ構造を木 (tree) と呼ぶ．
木はノード (node) とそれらを結ぶ枝 (branch) から構成される．データが記録されているのはノードであり，枝はデータとデータの間の親子関係を示す． A B C D G H F E ノード 枝 p

3 木とは あるノードから下に分岐した先のノードを子，分岐元のノードを親という．
木の一番最初のノードを特に，根 (root) と呼び，子を持たないノードを葉 (leaf) と呼ぶ． 根 A B C D G H F E 親 子 親 子 子 葉

4 木とは あるノードから下につながった木構造の全体を部分木 (subtree) という．
根からあるノードに到達するまでに通る枝の数をそのノードの深さ (depth) といい，根から最も深いノードまでの深さを木の高さ (height) という． A B C D G H F E 深さ 0 部分木 深さ 1 深さ 2 深さ 3 この木の高さ＝ 3

5 木とは 左の子 ≦ 親 ≦ 右の子 ノードからの分岐が2以下の木を2分木 (binary tree) と呼ぶ．
親と子の関係が，ある規則 (大きい，小さいなど) に従って並べられている木を2分探索木 (binary search tree) という． 48 32 59 26 11 29 67 51 A 2分木 B C I D E F 左の子 ≦ 親 ≦ 右の子 G H

6 木とは 木構造はきわめて重要で，多くの実用的対象が存在する． 組織データやファイルシステムなどの階層構造の表現
AI における論理的関係性の表現 探索を容易にする情報表現 (2分探索木など) ヒープ・ソート 講義では，2分探索木およびヒープに重点を置いて解説する．

7 2分探索木の配列表現 ノードに格納するデータが人名であるとき，名前を辞書順に並べる2分探索木が作れる．
全ての親と子の間に，左の子≦親≦右の子という関係が成立する． 右側の子のノード番号 Machilda 1 2 Candy 3 4 Rolla 5 Emy 6 7 Ann Eluza Lisa Nancy No.0 No.1 No.3 No.4 No.5 No.7 No.6 No.2 このようにノード番号を管理すれば，配列に格納できる． p

8 2分探索木の配列表現 各ノードに格納する情報は，人名，左の子へのポインタ (ノード番号)，右の子へのポインタ (ノード番号) の3つである．
これを構造体にまとめ，配列にする． struct tnode { int left; // 左部分木へのポインタ(番号) char name[64]; // データ(人名) int right; // 右部分木へのポインタ(番号) };

9 2分探索木の配列表現 この配列を使って，2分探索木を表現できる．
ただし，nil はポインタが指し示すものがないという意味で，具体的には -1 などを使う． 1 Machilda 2 3 Candy 4 5 Rolla nil Ann 6 Emy 7 Nancy Eluza Lisa a[p].left a[p].name a[p].right 二分探索木の配列表現 Machilda 1 2 Candy 3 4 Rolla 5 Emy 6 7 Ann Eluza Lisa Nancy No.0 No.1 No.3 No.4 No.5 No.7 No.6 No.2

10 2分探索木の配列表現 2分探索木から key という目的データを探すには，root から初めて，key がノードのデータより小さいときは左側の木へ, 大きいときは右側の木へ探索すればよい． 実質的に二分探索 O(log n) の計算量 1 Machilda 2 3 Candy 4 5 Rolla nil Ann 6 Emy 7 Nancy Eluza Lisa a[p].left a[p].name a[p].right 二分探索木の配列表現 1 4 key が Eluza の場合 Machilda 1 2 Candy 3 4 Rolla 5 Emy 6 7 Ann Eluza Lisa Nancy No.0 No.1 No.3 No.4 No.5 No.7 No.6 No.2 6

11 二分探索木の配列表現 (ソースコード) p.279 このコードでは，2分探索木を初期化において与えている．
nil は -1 と定義 (プリプロセッサ)． scanf() で key を読み込み，p を 0 (根ノード) で初期化． p が nil にならない限り続けるループに入る． strcmp() を使って，今見ているノード p の名前欄と key を照合し，合致していたら発見したことを表示してループを抜ける． もし key の方が小さいときは，p を a[p].left に． 逆の場合は p を a[p].right にする．

12 2分探索木へのデータの追加 先程の例では，最初から 2分探索木ができていたが，これを作るアルゴリズムが必要
すでに存在する 2分探索木に対して，新しいノードを追加する手順は，以下の 2段階を踏む 新ノードの親となるノードを探索 新ノードを親ノードに接続 現在調べているノードの番号を視点 p とし，この視点に一つ遅れで追従する視点 old も用意する p を進めていき，p が nil になったとき，old が指し示しているノードが新ノードの親

13 2分探索木へのデータの追加  p=0; while (p!=nil){ old=p;
if (strcmp(key,a[p].name)<=0) 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)<=0) a[old].left=sp; a[old].right=sp; sp++; sp: 5 3 4 key: “Nancy” “Patie”  p: -1  p old  Machilda 1 2 p old  1 2  Candy -1 Rolla 3 -1 -1 p old  3 -1 Nancy -1 4   4 -1 Patie -1

14 2分探索木の動的表現 リストの場合と同様，ツリーもノードが動的に追加されるデータ構造である．
従って，自己参照構造体としてノードを表現し，必要に応じてメモリを動的に確保するのが適している． struct tnode { struct tnode *left; /* 左部分木へのポインタ */ char name[12]; /* 名前 */ struct tnode *right; /* 右部分木へのポインタ */ }; struct tnode *talloc(void) { return (struct tnode *)malloc(sizeof(struct tnode)); }; p

15 新規ノード作成手順 (コードを見つつ) 配列表現の時と同様，(1) 新規ノードの親となるノードの探索，(2) 新規ノードの生成と親ノードからの接続を行う. 視点 p を root で初期化． p は新規データ dat の大小にした がって木をたどり，old は一つ遅れ で追従：old=p としてから p を 適切な方向へ進める p が NULL なら old が親ノード p=talloc()としてデータ記入 左右の子はいない：NULL に 親ノードの名前と新ノードの名前の大小関係により，親ノードの左右どちらかのポインタを p に向ける Emyを追加 Candy を追加 p:NULL p=p->left p old Machilda old->left=p p old p=p->right Candy old->right=p p Emy

16 2分探索木の動的表現 (ソースコード) まずはルートノード作成 root=talloc();
scanf("%s",root->name); root->left=root->right=NULL; root Machilda

17 2分探索木の動的表現 (ソースコード) 第2ノード以降作成 (さきほどの手順) root dat: Nancy Rolla p: NULL
  while (scanf("%s",dat)!=EOF){ p=root; while (p!=NULL){ old=p; if (strcmp(dat,p->name)<=0) p=p->left; else p=p->right; } p=talloc(); strcpy(p->name,dat); p->left=p->right=NULL; if (strcmp(dat,old->name)<=0) old->left=p; old->right=p; 第2ノード以降作成 (さきほどの手順)        root    dat: Nancy Rolla    p: NULL NULL  ここから下，p は 「視点」ではなく， 「新規ノード位置」 を示す． p p old   Machilda   p p old   Rolla     p  Nancy 

18 2分探索木の再帰的表現 (集中して聞くこと) 木構造は再帰的処理に向いている．例えば探索の場合…
「rootノード (Machilda) 以下から Emy を探す」と いう問題は，「root->left (Candy) 以下の部分木から Emy を探す」という副問題に 分解 できる． 再帰の脱出条件： 　　発見 or 　　行き先が NULL (不在) root Machilda Ann Rolla Candy Emy (例：Eluza) この中からの探索 この中からの探索 p (途中まで)

19 ノード追加の再帰的方法 (集中して聞くこと)
既存の 2分探索木に新しいデータ w を含むノードを追加する処理を再帰的に記述することを考える． 再帰関数のプロトタイプを以下の通りとする： struct tnode *gentree(struct tnode *p, char w[]) p：起点ノード (このノード以下が作業対象) w：追加するデータ (名前) その動作は条件により異なる： p が NULL ではないとき： ノード p の適切な方の子ノードを起点として gentree()を再帰呼び出しし， 受け取ったポインタ p をそのまま返す (オウム返し) p が NULL のとき： 新規ノードを作り，w を格納，作った新規ノードへのポインタを返す

20 ノード追加の再帰的方法 第 1 引数が NULL 以外： ・適切な子を起点とする 再帰呼び出し ・第一引数をオウム返し
・適切な子を起点とする 　再帰呼び出し ・第一引数をオウム返し 第 1 引数が NULL ： ・新規ノードを作成 ・新規ノードへのポイ 　ンタを返す ※ ここでは，データ Nancy を含むノードへの 　 ポインタを [Nancy] と表記する． root main() root = gentree(root,”Emy”) 呼出 [Nancy] gentree([Nancy],”Emy”) [Nancy]->left = gentree([Nancy]->left,”Emy”); 同じポインタを上書き  元の構造を壊さない Nancy 呼出 [Candy] gentree([Candy],”Emy”) [Candy]->right = gentree([Candy]->right,”Emy”); NULL Candy 呼出 [Emy] 戻り値の利用方法に注目 Emy gentree(NULL,”Emy”) ノード作成

21 ノード追加の再帰的方法 第 1 引数が NULL 以外： ・適切な子を起点とする 再帰呼び出し ・第一引数をオウム返し
・適切な子を起点とする 　再帰呼び出し ・第一引数をオウム返し 第 1 引数が NULL ： ・新規ノードを作成 ・新規ノードへのポイ 　ンタを返す 同じ方法で，第一ノード (root ノード) 作成も できるだろうか？ root main() root = gentree(root,”Nancy”) 呼出 [Nancy] gentree(NULL,”Nancy”) ・ノード作成 ・作ったノードへのポインタを返す Nancy 第一ノード作成もそれ以降も root = gentree(略) でOK！ void main(void) { char dat[12]; struct tnode *root; root = NULL; while (scanf("%s",dat)!= EOF){ root = gentree(root,dat); }  二分探索木の生成は， 　 root を NULL で初期化し， 　root = gentree(略); を 　 繰り返せば全部できる！

22 ノード追加の再帰的方法 (ソース) struct tnode *gentree(struct tnode *p, char *w) {
if (p == NULL){ p = talloc(); strcpy(p->name, w); p->left = p->right = NULL; } else if (strcmp(w, p->name) < 0) p->left = gentree(p->left, w); else p->right = gentree(p->right, w); return p; 新規ノード作成  p：新規ノード  適切な子の選択 再帰 呼出 子ポインタへの代入 再帰呼出  p：第一引数そのまま ポインタを返す (新ノードを作ったときはそれへのポインタ，そうでないときは 受け取った第一引数 p を (いじらずそのまま) オウム返し)

23 2分探索木のサーチ (再帰版) key: “Rolla” key: “Nancy”
while (printf("Search name -->"), scanf("%s",key)!=EOF){ if ((p=search(root,key))!=NULL) printf("%s が見つかりました\n",p->name); else printf("見つかりません\n"); } key: “Rolla” key: “Nancy” p=search(root,key)) printf(“%s が見つかりました\n”,p->name); p printf(“見つかりません\n”); Machilda p struct tnode *search(struct tnode *p,char *key) { if (p==NULL || strcmp(key,p->name)==0) return p; if (strcmp(key,p->name)<0) return search(p->left,key); else return search(p->right,key); } Rolla struct tnode *search(struct tnode *p,char *key) { if (p==NULL || strcmp(key,p->name)==0) return p; if (strcmp(key,p->name)<0) return search(p->left,key); else return search(p->right,key); } struct tnode *search(struct tnode *p,char *key) { if (p==NULL || strcmp(key,p->name)==0) return p; if (strcmp(key,p->name)<0) return search(p->left,key); else return search(p->right,key); } (p: マチルダ) (p: ローラ) p: NULL (p: NULL) return p; return p; return search(p->left,key); return search(p->right,key);

24 2分探索木のトラバーサル (深さ優先) トラバーサル (traversal)：木の全てのノードを訪れること (木の走査) (例：大学組織データ内からの教員捜し) 深さ優先探索：「左向きにとにかく進んで，端に来たら 1つ前の親に戻って右に進む」という行動を繰り返す． 再帰的に記述すると，関数 treewalk(p)は，以下のような動作をすれば良い (p：起点ノードへのポインタ) void treewalk(struct tnode *p) { if (p!=NULL){ treewalk(p->left); printf("%s\n",p->name); treewalk(p->right); }  p が NULL なら戻る (終了条件)  p の左の子を起点として再帰呼出  p での作業 (ノード内容表示)  p の右の子を起点として再帰呼出

25 2分探索木のトラバーサル (深さ優先) ノード内容表示の順序次第で，表示順序が変わる 行きがけ順
Machilda Rolla Emy Candy Lisa p： NULL void treewalk(struct tnode *p) { if (p!=NULL){ 　　　　printf("%s\n",p->name); 　　　　treewalk(p->left); 　　　　treewalk(p->right); } p p p p p 画面表示 Machilda Emy Candy Lisa Rolla

26 2分探索木のトラバーサル (深さ優先) ノード内容表示の順序次第で，表示順序が変わる 通りがけ順 アルファベット順 
Machilda Rolla Emy Candy Lisa p： NULL void treewalk(struct tnode *p) { if (p!=NULL){ treewalk(p->left); printf("%s\n",p->name); treewalk(p->right); } p p p p p 画面表示 Candy Emy Lisa Machilda アルファベット順  Rolla

27 レベルごとのトラバーサル (試験範囲外) 木のレベル (深さ) ごとに，さらに同一レベルでは左から右にノードをトラバーサルするには？
 配列 (TODOリスト) で実現 配列 q： G B A D C E H F copy 配列 w： D G B E H C F レベル終了時に配列 w が空なら終了 A レベル 1 B C レベル 2 D E F レベル 3 G H レベル 4 ※ 教科書でこの配列を「スタック」と呼んでいるのは間違い

28 ヒープ ヒープ (heap：山，堆積) とは，すべての親が必ず2つの子を持つ (最後の要素は左の子だけでも良い) 完全2分木で，どの親と子をとっても，親≦子になっている木を言う． 1 35 30 25 10 15 26 40 27 28 22 20 29 配列表現： ノードを深さごとに左から順に配列に格納する 3 2 5 6 7 4 ※ ヒープにおいては添え字は 　 0 でなく 1 から始める． 　 こうすると，子 s の親 p は， 　 p=s/2 で求まる． 8 9 10 11 12 10 1 25 2 15 3 30 4 26 5 20 6 29 7 35 8 40 9 27 10 28 11 22 12 例）11/2=5 (整数演算) p

29 ヒープへのデータ追加 (上方移動) 既に存在するヒープへ新規データを追加することを考える． その手順は以下の通りである：
(1) 新しいデータをヒープの最後の要素として格納する． (2) その要素を子とする親のデータと比較し，親の方が大きければ子と親を交換する． (3) 次に，その親を子とする親 (おじいちゃん) との間で比較を行い，必要があれば交換．これを，子の位置が根まで上がるか，親≦子になるまで繰り返す． 教科書 p.304 の図6.13を参照せよ． この手順を上方移動 (shift up) という． ソースコードは p.305.

30 ヒープへのデータ追加 (上方移動)    s= 4 9 2 p= 4 1 2 (1) 新しいデータをヒープの最後の要素として格納する．
(2) その要素を子とする親のデータと比較し，親の方が大きければ子と親を交換する． (3) 次に，その親を子とする親 (おじいちゃん) との間で比較を行い，必要があれば交換．これを，子の位置が根まで上がるか，親≦子になるまで繰り返す．   35 29 30 26 25 15 20 10 1 2 7 3 6 5 8 4 12 12 25 12 9 s= 4 9 2 30 p= 4 1 2

31 ヒープの作成 (下方移動) 上方移動では既存のヒープにデータを一つずつ追加することによりヒープを作成したが，既存の全データをそのまま2分木に割り当ててから，ヒープとして整えるという方法がある．その手順は以下の通り (教科書は分かりにくい)： (1) 子を持つ最後の親 (データ数が n のとき，n/2) i から開始し，全ての親に対して逆順に (n/2, n/2-1, n/2-2, …, 1)，以下の (2)～(4) の手順を繰り返す． (2) 親の番号を p とし，２つの子 (2p, 2p+1) のうちで小さい方を s とする．(一番最後の親は，左側にしか子を持たない場合がある．この場合は自動的に s = 2p とする.) (3) 子 s の値が，親 p 以上なら，(1) のループで次へ． (4) p と s の値を交換し，交換された子の方を親として (p = s， s = 2p)，(2) へ戻る．

32 ヒープの作成 (下方移動) 図的に理解しよう．     (2) から (4) の手順を 下方移動 (shift down) と呼ぶ
(1) 子を持つ最後の親から開始してループ (最初は 9/2 = 4 から)  (2) 親の番号を p とし，2p と 2p+1 で小 さい方の子を s とする． i= 3 4 2 1  (3) s が p より大きいときは (1) ループで 次へ． p= 4 6 8 3 7 1 2 4 8 3 7 4 3 2 9 8 6 1 5 1 s= 6 4 12 8 14 16 3 16 8 7  (4) p と s を交換し，p=s, s=2p とする． s>n なら (1) ループで次へ． s<=n なら (2) へ． 2 7 6 1 (2) から (4) の手順を 下方移動 (shift down) と呼ぶ 4 3 2 7 8 4 3 ソースコード：p.307

33 ヒープ・ソート ヒープを用いたソーティングアルゴリズムがヒープ・ソートである．手順は大まかに以下の通り：
(1) 与えられた数列からヒープを作成する． (2) 根ノードには最小値が来ているはずなので, これを取り外す．その代わり，最後のノード (データ数 n なら n番の要素) を切り離して根ノードに持ってくる． (3) これにより残ったデータ (n -1個) のヒープ条件が狂ったので，下方移動を使ってヒープの修正を行う. この場合，根ノードからの1回の下方移動を行うだけでよい． (4) (2) に戻る． 教科書 p.308 の図6.15 を参照せよ． 計算量のオーダは O (n log n)． p

34 ヒープ・ソート (ソースコード) p.309． 関数 swap() は2つの配列要素の交換．
main関数内，最初の whileループは初期ヒープの作成．データを入れるごとに，入れたデータを最後尾に格納した上で，上方移動を使ってヒープを整える作業を繰り返している． 2つめの whileループは，データを取り出すごとのループ． 最初にルート (1番) と最後尾 (n番) を交換して，最後尾をヒープから除外している (n--)． 次のループは，視点 p を根に初期化して下方移動を1回行っている部分． p.311 では，初期ヒープ作成を下方移動で行っている．

35 第7章：グラフ リスト構造は，ノード群を鎖状につないだもので，分岐はなかった．一方木構造は分岐はするが，分岐した枝同士は分かれたまま．
これらをより一般化したものがグラフ (graph) である．グラフでは，ノード間の連結は任意であり，ループを含むこともある． 1 3 2 4 5 7 6 8 p

36 グラフとは 円で描いた部分はノード (node 節点，vertex 頂点ともいう) であり，それを結んでいるのは エッジ (edge 辺，branch 枝) である．ノード1と2はつながっているが，1と3はつながっていない． エッジ ノード 1 3 2 4 5 7 6 8

37 グラフとは グラフをデータとして表現するときに使われるのは隣接行列 (adjacency matrix) である．ノード i と j の間に接続がある場合は 1，ない場合は 0 としておく． 教科書ではノード番号は1からとしている． i j 1 2 3 4 5 6 7 8 1 3 2 4 5 7 6 8 1 対角成分は，同じノードへの接続をあるとするかどうかに関係する (この場合はなしとしている)．

38 グラフとは ここまでの例では，グラフのエッジには向きはなかった．このようなものを無向グラフ (undirected graph) という．
これに対して,「進める方向」のような向きを含んだグラフを有向グラフ (directed graph) という．この場合，隣接行列は，ノード i から j へのエッジに対して，要素 (i, j) は 1，要素 (j, i) は 0 としておく (p.333 図7.4)． 1 3 2 4 5 7 6 8

39 深さ優先探索 グラフのノードにデータが記載されている場合，この中から特定のデータを探すとき，グラフの全てのノードを巡るというアルゴリズムが必要となる． その一つは 深さ優先探索 (depth first search, 縦型探索とも呼ばれる) である． (1) 始点を出発し，ノード番号の若い順に進む位置を調べ，いけるところ (エッジで連結されていてまだ訪問していないノード) まで進む． (2) 行き場所がなくなったら，まだいける方向の残っている分岐点まで戻り，再びいけるところまで進む． (3) 行き場所が全てなくなったら終了 (来た道を戻る)． p

40 深さ優先探索 どのように探索が進むかを図で見てみよう．
(1) 始点を出発し，ノード番号の若い順に進む位置を調べ，いけるところ (エッジで連結されていてまだ訪問していないノード) まで進む． (2) 行き場所がなくなったら，まだいける方向の残っている分岐点まで戻り，再びいけるところまで進む． (3) 行き場所が全てなくなったら終了 (来た道を戻る)． 6 2 5 4 1 8 7 3

41 深さ優先探索の再帰的解法 深さ優先探索を再帰 的に行う関数は右の 通り．
未探索の行き先を順 番に探して，行ける ときは再帰呼び出し でそこに進む． visit(1)を呼ぶと… void visit(int i) { int j; v[i]=1; for (j=1;j<=N;j++){ if (a[i][j]==1 && v[j]==0){ printf("%d->%d ",i,j); visit(j); } 1 2 3 4 5 6 8 7 2 2 6 6 5 5 4 4 j= 3 j= 8 5 j= 4 8 8 1 1 j= 2 3 3 7 7 j= 7 j= 6

42 深さ優先探索 (ソースコード) 2次元配列 a[][] によって隣接行列を記述 (初期化)．これがグラフの実体である．
配列 v[N+1] は「訪問済みフラグ」を意味する．これが 0 となっているノードは未訪問，1 なら訪問済み． main関数では訪問フラグの初期化の後，visit(1) を呼び出しているだけ． 関数 visit() は再帰的関数であり，引数 i は探索を開始するノードの番号．要するに「ノード i から先を探索せよ」という関数． visit() では，まず起点ノード i の訪問済みフラグを立てる (1にする)．次に他の全てのノード j を調べ，ノード i とつながっており (a[i][j]==1)，未訪問 (v[j]==0) ならば, ノード j を起点として探索 (再帰呼出 visit(j))．

43 深さ優先探索の応用 グラフ上の各ノードを起点として深さ優先探索を繰り返す場合は，各探索の前に訪問済みフラグを下ろして置かなくてはならない．
p.337 図7.6 のように，ノード群が分かれているグラフを非連結グラフと呼ぶ．これがどのように分かれているかを調べるには，訪問済みフラグのリセットをせずに，各ノードを起点とする探索を繰り返せばよい． 探索の起点となるノードが訪問済みの場合は次のノードへ進む．訪問済みでないときは，カウントを1つ進める． これにより，カウント数＝分かれている集団の数となる．

44 幅優先探索 幅優先探索 (breadth first search，横型探索とも言う) では，「これから進まなくてはならないノードのメモ」をキューの中に保存し，それを参照しながら探索を進める． (1) 始点をキューに入れる． (2) キューからノードを取り出し，そのノードに連結している未訪問のノードを全てキューに入れておく． (3) キューが空なら終了，そうでないときは (2) へ． これにより，始点から近いノードから順序よく探索が進められる． p

45 幅優先探索 (1) 始点をキューに入れる． (2) キューからノードを取り出し, 訪問済みとする. そのノードに連結している未訪問ノードを全てキューに入れておく． (3) キューが空なら終了，そうでないときは (2) へ． ソースコード：p 6 2 5 4 1 8 7 3 キュー： 1 2 3 4 5 7 6 8

46 トポロジカル・ソート グラフを見ると，2から仕事を始めたとき，4や7ができるためには，1, 3 が出来ていなければならないのと同時に，右側では 5, 6, 8 が出来ていなければならない． つまり，2, 1, 3, 4, 7 という系列と 2, 5, 4, 6, 8, 7 という系列がある．従って，2の次に行いうる仕事，1と5ではどちらを先に行っても良い．このように必ずしも順序を比較できない場合がある順序関係を半順序関係 (partial order) という． 教科書に誤植 6 2 5 8 4 1 7 3 p

47 トポロジカル・ソート 半順序関係が与えられたデータに対して，最初に行う仕事から最後に行う仕事を1列に並べることをトポロジカル・ソート (topological sort) という． どちらを先にやっても良い部分が含まれているので，解は1つとは限らず，どれかが得られればよい． 1 2 3 4 5 7 6 8

48 トポロジカル・ソート 有向グラフに対する深さ優先探索を繰り返し実行し，行き着いたところから来た道を戻ろうとするときに，そのノードを記録していけばよい． 記録は「最後に行き着く場所」から順に行われるので逆順． 6 2 5 8 4 1 7 3 2 5 6 8 1 3 7 4

49 Euler の一筆書き 辺を消しながら深さ優先探索を行い，出発点に戻った時に全ての経路が消えていれば，そのとき通った経路が求める経路である
スタック v[n] 1 1 4 2 1 4 3 2 1 2 4 3 ソースコード：p.350 p

50 ネットワーク 各辺に重みが定義されているグラフを 重み付きグラフ あるいは ネットワーク (network) と呼ぶ．
重みの意味は，例えば道路網については道路の長さであったり，水道網なら流量だったりである (p.359 図7.22)． データの実体は，重み行列 で 記述する． 1 2 3 4 5 6 7 8 M a b c d e f g h 1 2 4 7 6 5 3 (M：無限大)

51 最短路問題 (Dijkstra のアルゴリズム)
解きたい問題：ノード a から h までの最短距離を求める (1) 全てのノードの確定フラグを下ろし, 距離値を無限大で初期化 (2) スタートノードの距離値を 0 とする．(3), (4) を N 回繰り返す (3) 距離値最小の未確定ノードの番号を p とし，確定フラグを立てる (4) p につながる全ノードについて，p から進んだときの距離値が現在の 距離値より小さくなるとき，そのノードの距離値を更新する あるノードの距離値を更新するとき， 距離値だけでなく「この距離値に なる場合，直前のノードはこれ」と いう「手前ノード情報」も記録する  距離だけでなく経路も求まる M 3 e e e 1 M 2 b b b 1 4 5 M 4 f f f 1 2 M a a a 7 d d d 6 9 M 10 7 6 M h h h 2 3 2 M 2 c c c 5 g g g M 7 p

52 最短路問題の例 障害物環境下での移動ロボットのナビゲーション
コンフィギュレーション障害物の頂点をサブゴールとし，可視グラフ (visibility graph) を構築，最短路を探索 sub-goal start goal obstacle shortest path obstacle 移動ロボットのナビゲーションを主にやってるとこ：城間研 configuration obstacle

53 講義のおわりに 本講義では，知能システム工学科の趣旨に則って，メカと情報の融合分野を扱う上でのアルゴリズム・データ構造を実践的に (ソース・コードをベースとして) 解説した． 情報工学科における同名の講義とは異なり，理論的な議論はほとんど行っておらず，情報に興味のある学生にとっては不十分である． 一方，組み込みシステムなど，ハードウェアに近いプログラミングでは，マイコンや電子回路など，多くのハードウェアに関する知識が必要となる． それらについては，各自が必要に応じてより深く勉強すること．本講義は基礎の基礎しか扱っていない． 講義終了後もアルゴリズム・データ構造に関する質問は随時受け付ける．