• 検索結果がありません。

第12回:木構造

N/A
N/A
Protected

Academic year: 2021

シェア "第12回:木構造"

Copied!
53
0
0

読み込み中.... (全文を見る)

全文

(1)

アルゴリズムとデータ構造

講義スライド 4

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

(2)

2

木とは

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

(3)

木とは

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

(4)

4 部分木

木とは

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

(5)

I

木とは

 ノードからの分岐が2以下の木を2分木 (binary tree) と呼

ぶ.

 親と子の関係が,ある規則 (大きい,小さいなど) に従っ

て並べられている木を2分探索木 (binary search tree) と いう. A B C D G H F E 2分木 48 32 59 26 11 29 67 51

左の子 ≦ 親 ≦ 右の子

(6)

木とは

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

(7)

2分探索木の配列表現

 ノードに格納するデータが人名であるとき,名前を辞書順 に並べる2分探索木が作れる.  全ての親と子の間に,左の子≦親≦右の子という関係が成 立する. Machilda 1 2 Candy 3 4 5 Rolla Emy 6 7 Ann Eluza Lisa Nancy No.0 No.1

No.3 No.4 No.5

No.7 No.6

No.2

右側の子のノード番号

(8)

2分探索木の配列表現

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

(9)

 この配列を使って,2分探索木を表現できる.  ただし,nil はポインタが指し示すものがないという意味 で,具体的には -1 などを使う.

2分探索木の配列表現

Machilda 1 2 Candy 3 4 5 Rolla Emy 6 7 Ann Eluza Lisa Nancy No.0 No.1

No.3 No.4 No.5

No.7 No.6 No.2 1 Machilda 2 3 Candy 4 5 Rolla nil

nil Ann nil

6 Emy 7

nil Nancy nil nil Eluza nil nil Lisa nil

0 1 2 3 4 5 6 7

a[p].left a[p].name a[p].right

(10)

2分探索木の配列表現

 2分探索木から key という目的データを探すには,root から初めて,key がノードのデータより小さいときは左側 の木へ, 大きいときは右側の木へ探索すればよい. Machilda 1 2 Candy 3 4 5 Rolla Emy 6 7 Ann Eluza Lisa Nancy No.0 No.1

No.3 No.4 No.5

No.7 No.6 No.2 1 Machilda 2 3 Candy 4 5 Rolla nil

nil Ann nil

6 Emy 7

nil Nancy nil nil Eluza nil nil Lisa nil

0 1 2 3 4 5 6 7

a[p].left a[p].name a[p].right

二分探索木の配列表現 key が Eluza の場合 1 4 6 実質的に二分探索 O(log n) の計算量

(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 が指し示し ているノードが新ノードの親 12

(13)

2分探索木へのデータの追加

Machilda 1 2 Candy -1 -1 -1 Rolla -1 -1 -1 -1 -1 0 2 1 4 3 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; else a[old].right=sp; sp++; 3 4 sp: 354

key: “Nancy”“Patie”

p old p old          p old p: -1 Nancy Patie

(14)

14

2分探索木の動的表現

 リストの場合と同様,ツリーもノードが動的に追加される データ構造である.  従って,自己参照構造体としてノードを表現し,必要に応 じてメモリを動的に確保するのが適している. p.283-284 struct tnode {

struct tnode *left; /* 左部分木へのポインタ */ char name[12]; /* 名前 */

struct tnode *right; /* 右部分木へのポインタ */ };

struct tnode *talloc(void) {

return (struct tnode *)malloc(sizeof(struct tnode)); };

(15)

新規ノード作成手順 (コードを見つつ)

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

(16)

root

2分探索木の動的表現 (ソースコード)

 まずはルートノード作成 16 root=talloc(); scanf("%s",root->name); root->left=root->right=NULL; Machilda

(17)

p

2分探索木の動的表現 (ソースコード)

 第2ノード以降作成 (さきほどの手順) 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; else old->right=p; }                            root Machilda

dat: RollaNancy p: NULLNULL Rolla Nancy p old p old pp ここから下,p は 「視点」ではなく, 「新規ノード位置」 を示す.

(18)

 木構造は再帰的処理に向いている.例えば探索の場合…  「rootノード (Machilda) 以下から Emy を探す」と

いう問題は,「root->left (Candy) 以下の部分木から Emy を探す」という副問題に 分解 できる. 18 この中からの探索

2分探索木の再帰的表現

Machilda Ann Rolla Candy Emy root この中か らの探索 再帰の脱出条件: 発見 or 行き先が NULL (不在) (例:Eluza) p.285-288 (途中まで)

(集中して聞くこと)

(19)

ノード追加の再帰的方法

既存の 2分探索木に新しいデータ w を含むノードを追加す

る処理を再帰的に記述することを考える.

 再帰関数のプロトタイプを以下の通りとする:

struct tnode *gentree(struct tnode *p, char w[])

p:起点ノード (このノード以下が作業対象)  w:追加するデータ (名前)  その動作は条件により異なる:  p が NULL ではないとき: ノード p の適切な方の子 ノードを起点として gentree()を再帰呼び出しし, 受け取ったポインタ p をそのまま返す (オウム返し)  p が NULL のとき: 新規ノードを作り,w を格納, 作った新規ノードへのポインタを返す

(集中して聞くこと)

(20)

※ ここでは,データ Nancy を含むノードへの ポインタを [Nancy] と表記する. gentree(NULL,”Emy”) ノード作成 gentree([Candy],”Emy”) [Candy]->right = gentree([Candy]->right,”Emy”); gentree([Nancy],”Emy”) [Nancy]->left = gentree([Nancy]->left,”Emy”);

ノード追加の再帰的方法

20 main() root = gentree(root,”Emy”) 第 1引数が NULL 以外: ・適切な子を起点とする 再帰呼び出し ・第一引数をオウム返し 第 1引数が NULL : ・新規ノードを作成 ・新規ノードへのポイ ンタを返す Nancy root Candy 呼出 呼出 呼出 [Emy] [Candy] [Nancy] 戻り値の利用方法 に注目 Emy NULL 同じポインタを上書き  元の構造を壊さない

(21)

同じ方法で,第一ノード (root ノード) 作成も できるだろうか?

ノード追加の再帰的方法

第 1引数が NULL 以外: ・適切な子を起点とする 再帰呼び出し ・第一引数をオウム返し 第 1引数が NULL : ・新規ノードを作成 ・新規ノードへのポイ ンタを返す root Nancy main() root = gentree(root,”Nancy”) gentree(NULL,”Nancy”) ・ノード作成 ・作ったノードへのポインタを返す 呼出 [Nancy] void main(void) { char dat[12];

struct tnode *root; root = NULL;

while (scanf("%s",dat)!= EOF){

root = gentree(root,dat);

第一ノード作成もそれ以降も root = gentree(略) でOK!

 二分探索木の生成は,

root を NULL で初期化し, root = gentree(略); を 繰り返せば全部できる!

(22)

ノード追加の再帰的方法 (ソース)

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)

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); } return search(p->right,key); (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); } (p: ローラ) return search(p->left,key); return 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); (p: NULL) return p;

2分探索木のサーチ (再帰版)

Machilda Rolla while (printf("Search name -->"),

scanf("%s",key)!=EOF){ if ((p=search(root,key))!=NULL) printf("%s が見つかりました¥n",p->name); else printf("見つかりません¥n"); } p=search(root,key)) key: “Rolla” key: “Nancy” p p p: NULL printf(“%s が見つかりました¥n”,p->name); printf(“見つかりません¥n”);

(24)

2分探索木のトラバーサル (深さ優先)

トラバーサル (traversal):木の全てのノードを訪れるこ と (木の走査) (例:大学組織データ内からの教員捜し)  深さ優先探索:「左向きにとにかく進んで,端に来たら 1 つ前の親に戻って右に進む」という行動を繰り返す.  再帰的に記述すると,関数 treewalk(p)は,以下のよう な動作をすれば良い (p:起点ノードへのポインタ) 28

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分探索木のトラバーサル (深さ優先)

void treewalk(struct tnode *p) { if (p!=NULL){ printf("%s¥n",p->name); treewalk(p->left); treewalk(p->right); } } p p Machilda Rolla Emy Candy Lisa p p p Machilda Emy Candy Lisa 画面表示 p: NULL

(26)

 ノード内容表示の順序次第で,表示順序が変わる

 通りがけ順

2分探索木のトラバーサル (深さ優先)

30

void treewalk(struct tnode *p) { if (p!=NULL){ treewalk(p->left); printf("%s¥n",p->name); treewalk(p->right); } } p p Machilda Rolla Emy Candy Lisa p p p Candy Emy Lisa Machilda Rolla 画面表示 p: NULL アルファベット順 

(27)

 木のレベル (深さ) ごとに,さらに同一レベルでは左から 右にノードをトラバーサルするには?  配列 (TODOリスト) で実現 E G H

レベルごとのトラバーサル (試験範囲外)

A C B D F レベル 1 レベル 2 レベル 3 レベル 4 配列 q: 配列 w: B C A B C D E F G H D E F G H copy レベル終了時に配列 w が空なら終了

(28)

32

ヒープ

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

(29)

ヒープへのデータ追加 (上方移動)

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

(30)

12 9

ヒープへのデータ追加 (上方移動)

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

(31)

ヒープの作成 (下方移動)

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

(32)

ヒープの作成 (下方移動)

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

(33)

ヒープ・ソート

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

(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

(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 3 2 4 5 7 6 8 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 i j 1 2 3 4 5 6 7 1 2 3 4 5 6 7 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)行き場所が全てなくなったら終了 (来た道を戻る).

(40)

深さ優先探索

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

(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 1 2 3 4 5 6 8 7 j= 2 j= 3 1 2 3 4 5 6 8 7 j= 5 j= 4 8

(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)

48

幅優先探索

 幅優先探索 (breadth first search,横型探索とも言う) で

は,「これから進まなくてはならないノードのメモ」を キューの中に保存し,それを参照しながら探索を進める. (1)始点をキューに入れる. (2)キューからノードを取り出し,そのノードに連結している 未訪問のノードを全てキューに入れておく. (3)キューが空なら終了,そうでないときは (2) へ.  これにより,始点から近いノードから順序よく探索が進め られる. p.339-342

(45)

幅優先探索

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

(46)

50

トポロジカル・ソート

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

(47)

トポロジカル・ソート

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

(48)

トポロジカル・ソート

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

(49)

Euler の一筆書き

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

(50)

 各辺に重みが定義されているグラフを 重み付きグラフ あるいは ネットワーク (network) と呼ぶ.  重みの意味は,例えば道路網については道路の長さであっ たり,水道網なら流量だったりである (p.359 図7.22).  データの実体は,重み行列 で 記述する.

ネットワーク

54 a b c d e f g h 1 2 2 4 1 7 6 5 2 3 2 1 2 3 4 5 6 7 8 1 0 1 7 2 M M M M 2 1 0 M M 2 4 M M 3 7 M 0 M M 2 3 M 4 2 M M 0 M M 5 M 5 M 2 M M 0 1 M M 6 M 4 2 M 1 0 M 6 7 M M 3 5 M M 0 2 8 M M M M M 6 2 0 (M:無限大)

(51)

解きたい問題:ノード a から h までの最短距離を求める (1) 全てのノードの確定フラグを下ろし, 距離値を無限大で初期化 (2) スタートノードの距離値を 0 とする.(3), (4) を N 回繰り返す (3) 距離値最小の未確定ノードの番号を p とし,確定フラグを立てる (4) p につながる全ノードについて,p から進んだときの距離値が現在の 距離値より小さくなるとき,そのノードの距離値を更新する  あるノードの距離値を更新するとき, 距離値だけでなく「この距離値に なる場合,直前のノードはこれ」と いう「手前ノード情報」も記録する  距離だけでなく経路も求まる

最短路問題 (Dijkstraのアルゴリズム)

b d e f 1 2 2 4 1 7 6 5 2 3 2 a c g h M M M M M M M 10 b d e f a c g h 0 1 7 6 2 3 5 b d e f a c g h 4 9

(52)

 障害物環境下での移動ロボットのナビゲーション

 コンフィギュレーション障害物の頂点をサブゴールとし,

可視グラフ (visibility graph) を構築,最短路を探索

最短路問題の例

56

start obstacle goal

obstacle sub-goal

configuration obstacle

移動ロボットのナビゲーション を主にやってるとこ:城間研

(53)

講義のおわりに

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

参照

関連したドキュメント

ところで,このテクストには,「真理を作品のうちへもたらすこと(daslnsaWakPBrinWl

2008 ) 。潜在型 MMP-9 は TIMP-1 と複合体を形成することから TIMP-1 を含む含む潜在型 MMP-9 受 容体を仮定して MMP-9

ホーム &gt; マニュアル &gt; ユーザーマニュアル &gt; 事前知識&gt; 「サイボウズ デヂエ」の画面構成..

これはつまり十進法ではなく、一進法を用いて自然数を表記するということである。とは いえ数が大きくなると見にくくなるので、.. 0, 1,

被保険者証等の記号及び番号を記載すること。 なお、記号と番号の間にスペース「・」又は「-」を挿入すること。

備考 1.「処方」欄には、薬名、分量、用法及び用量を記載すること。

これら諸々の構造的制約というフィルターを通して析出された行為を分析対象とする点で︑構

「あるシステムを自己準拠的システムと言い表すことができるのは,そのシ