第12回:木構造

アルゴリズムとデータ構造
講義スライド 4
木
 グラフ
茨城大学 工学部 知能システム工学科 井上 康介
E2棟407号室
木とは
 リスト構造では枝分かれは起こらなかった.枝分かれしな
がらデータが伸びていくデータ構造を木 (tree) と呼ぶ.
 木はノード (node) とそれらを結ぶ枝 (branch) から構成
される.データが記録されているのはノードであり,枝は
データとデータの間の親子関係を示す.
A
ノード
B
D
G
p.276-277
枝
C
E
F
H
2
木とは
 あるノードから下に分岐した先のノードを子,分岐元の
ノードを親という.
 木の一番最初のノードを特に,根 (root) と呼び,子を持
たないノードを葉 (leaf) と呼ぶ.
根
A
親
子
D
B
親
子
C
E
F
子
G
H
葉
3
木とは
 あるノードから下につながった木構造の全体を部分木
(subtree) という.
 根からあるノードに到達するまでに通る枝の数をそのノー
ドの深さ (depth) といい,根から最も深いノードまでの
深さを木の高さ (height) という.
A
部分木
B
D
深さ 3
G
深さ 0
C
E
H
深さ 1
F
深さ 2
この木の高さ= 3
4
木とは
 ノードからの分岐が2以下の木を2分木 (binary tree) と呼
ぶ.
 親と子の関係が,ある規則 (大きい,小さいなど) に従っ
て並べられている木を2分探索木 (binary search tree) と
いう.
48
A
32
B
26
D
11
G
2分木
59
C
51
E
67
F
I
29
H
5
木とは
 木構造はきわめて重要で,多くの実用的対象が存在する.
 組織データやファイルシステムなどの階層構造の表現
 AI における論理的関係性の表現
 探索を容易にする情報表現 (2分探索木など)
 ヒープ・ソート
 講義では,2分探索木およびヒープに重点を置いて解説す
る.
6
2分探索木の配列表現
 ノードに格納するデータが人名であるとき,名前を辞書順
に並べる2分探索木が作れる.
 全ての親と子の間に,左の子≦親≦右の子という関係が成
立する.
右側の子のノード番号
No.0
1
Machilda
No.1
3
2
No.2
Candy
No.3
4
No.4
6
Ann
No.6
5
Rolla
No.5
Emy
7
Nancy
No.7
Eluza
Lisa
このようにノード番号を管理すれば,配列に格納できる.
p.278-282
7
2分探索木の配列表現
 各ノードに格納する情報は,人名,左の子へのポインタ
(ノード番号),右の子へのポインタ (ノード番号) の3つで
ある.
 これを構造体にまとめ,配列にする.
struct tnode {
int left;
char name[64];
int right;
} a[100];
// 左部分木へのポインタ(番号)
// データ(人名)
// 右部分木へのポインタ(番号)
8
2分探索木の配列表現
 この配列を使って,2分探索木を表現できる.
 ただし,nil はポインタが指し示すものがないという意味
で,具体的には -1 などを使う.
a[p].left a[p].name a[p].right
0
1
2
3
No.0
1
Machilda
2
No.1
3
No.2
Candy
No.3
4
5
No.4
Ann
6
No.6
No.5
Emy
7
Nancy
No.7
Eluza
Lisa
Rolla
4
5
6
7
1 Machilda 2
3
Candy
4
5
Rolla
nil
nil
Ann
nil
6
Emy
7
nil
Nancy
nil
nil
Eluza
nil
nil
Lisa
nil
二分探索木の配列表現
9
2分探索木の配列表現
 2分探索木から key という目的データを探すには,root
から初めて,key がノードのデータより小さいときは左側
の木へ, 大きいときは右側の木へ探索すればよい.
 O(log n) の計算量
a[p].left a[p].name a[p].right
key が Eluza の場合
0
1
2
3
No.0
1
Machilda
2
No.1
3
No.2
Candy
No.3
4
5
No.4
Ann
6
No.6
No.5
Emy
7
Nancy
No.7
Eluza
Lisa
Rolla
4
5
6
7
1 Machilda 2
3
Candy
4
5
Rolla
nil
nil
Ann
nil
Emy
7
6
nil
Nancy
nil
nil
Eluza
nil
nil
Lisa
nil
二分探索木の配列表現
10
二分探索木の配列表現 (ソースコード)
 p.279
 このコードでは,2分探索木を初期化において与えてい
る.
 nil は -1 と定義 (プリプロセッサ).
 scanf() で key を読み込み,p を 0 (根ノード) で初期
化.
 p が nil にならない限り続けるループに入る.
 strcmp() を使って,今見ているノード p の名前欄と
key を照合し,合致していたら発見したことを表示して
ループを抜ける.
 もし key の方が小さいときは,p を a[p].left に.
 逆の場合は p を a[p].right にする.
11
2分探索木へのデータの追加
 先程の例では,最初から 2分探索木ができていたが,これ
を作るアルゴリズムが必要
 すでに存在する 2分探索木に対して,新しいノードを追加
する手順は,以下の 2段階を踏む
 新ノードの親となるノードを探索
 新ノードを親ノードに接続
 現在調べているノードの番号を視点 p とし,この視点に一
つ遅れで追従する視点 old も用意する
 p を進めていき,p が nil になったとき,old が指し示し
ているノードが新ノードの親
12
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;
else
a[old].right=sp;
sp++;
sp: 3
4
5
key: “Nancy”
“Patie”
p: -1
p old
0
1
Machilda
1
-1
2
p old
2
Candy
-1
-1
3
-1
p old
3
-1
Rolla
Nancy
-1
4
4
-1
Patie
-1
13
2分探索木の動的表現
 リストの場合と同様,ツリーもノードが動的に追加される
データ構造である.
 従って,自己参照構造体としてノードを表現し,必要に応
じてメモリを動的に確保するのが適している.
struct tnode {
struct tnode *left; /* 左部分木へのポインタ */
char name[12];
/* 名前 */
struct tnode *right; /* 右部分木へのポインタ */
};
struct tnode *talloc(void)
{
return (struct tnode *)malloc(sizeof(struct tnode));
};
p.283-284
14
新規ノード作成手順 (コードを見つつ)
 配列表現の時と同様,(1) 新規ノードの親となるノードの
探索,(2) 新規ノードの生成と親ノードからの接続を行う.
Candy を追加
 視点 p, old を root で初期化. Emyを追加
p:NULL
 p は新規データ dat の大小にした
p=p->left
がって木をたどり,old は一つ遅れ
p old
Machilda
で追従:old=p としてから p を
old->left=p
適切な方向へ進める
p old
p=p->right
Candy
 p が NULL なら old が親ノード
old->right=p
p
 p=talloc()としてデータ記入
Emy
 左右の子はいない:NULL に
 親ノードの名前と新ノードの名前の大小関係により,
親ノードの左右どちらかのポインタを p に向ける
15
2分探索木の動的表現 (ソースコード)
 P.283~p.284
 ノードの型は自己参照構造体.左部分木へのポインタ
left と右部分木へのポインタ right を含む.
 ノードの新規生成は関数 talloc() により行う.
 main関数では,最初に根ノードだけを別処理で生成.
 次の whileループでは,内部の whileループで,新たに
生成するノード (データ部は文字列 dat) の親となるノー
ドを探索している.
 p が NULL ではない限り続けるループで,現在調べている
ノードへのポインタ p を「一つ前のポインタ」old にコ
ピーした後,大小関係に応じて視点 p を右側,あるいは
左側に移動.p が NULL なら,その方向にはそれ以上ノー
ドがないことになるので, そこにつなげる.
16
2分探索木の動的表現 (ソースコード)
 まず新規ノードを作成し,それへのポインタを p に代入
し,データ部に dat をコピーする.また,p は葉になる
ノードである (子をもたない) ので,left, right は
NULL としておく.
 親 (old) のデータ部に対して dat が等しいか小さいとき
は左側,つまり old->left に,大きいときは右側
old->right に p をつなげる.
17
2分探索木の再帰的表現
 木構造は再帰的処理に向いている.
 例えば「rootノード (Machilda) 以下から Emy を探
す」という問題は,「root->left (Candy) 以下の部分
木から Emy を探す」という問題に分解できる.
root
この中からの探索
この中か
らの探索
再帰の脱出条件:
発見 or
行き先が NULL (不在)
(例:Eluza)
Machilda
Rolla
Candy
Ann
p.285-288 (途中まで)
Emy
18
ノード追加の再帰処理
 既存の 2分探索木に新しいデータ w を含むノードを追加す
る処理を再帰的に記述することを考える.
 関数 gentree(p,w):ノード p 以下の部分木の中の適切
な位置に,データ w をもつ新規ノードを追加する再帰関数
 p:処理の起点となるノードへのポインタ
 w:入れるべきデータ (教科書では名前)
 返り値:2つのケースに分かれる
 ノード生成時:作ったノードへのポインタ
 そうでない時:第1引数の p をそのままオウム返し
 ノード生成は p==NULL だったとき行う.
 返り値をこのようにすることで,「親ノードの探索」と
「新規ノード生成」を単一のコードでうまく両立
19
ノード追加の再帰処理
 関数 gentree(p,w)がやるべき仕事は2つ:
 新規ノード生成:起点ノードのポインタ p が NULL だっ
た場合は,新規ノードを生成して w を格納,そのノー
ドへのポインタをリターン
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)<0)
変数のように使って新規ノー
p->left=gentree(p->left,w);
ドへのポインタとしている
else
p->right=gentree(p->right,w);
return p;
}
20
ノード追加の再帰処理
 親ノード探索:起点ノード p から適切な方向へ進む
 p->left または p->right を起点として再帰呼出,
返ってきた値を p->left または p->right に代入,
その後,与えられた引数 p をそのままリターン
struct tnode *gentree(struct tnode *p,char *w)
{
if (p==NULL){
p=talloc(); 引数 p の値には一切変更を加
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;
}
21
gentree()の動作
 root を NULL で初期化し, w を入力,
root=gentree(root,w); とする:
struct tnode *gentree(struct tnode *p,
struct tnode *gentree(struct tnode *p,
char *w)
char *w) p:
マチルダ
p:NULL
{
p:NULL
{
if (p==NULL){
if (p==NULL){
p=talloc();
p=talloc();
w:”Machilda”
w:”Candy”
strcpy(p->name,w);
strcpy(p->name,w);
p->left=p->right=NULL;
p->left=p->right=NULL;
}
}
else if(strcmp(w,p->name)<0)
else if(strcmp(w,p->name)<0)
p
p->left=gentree(p->left,w);
p->left=gentree(p->left,w);
Machilda
else
else
p->right=gentree(p->right,w);
p->right=gentree(p->right,w);
p
return p;
return p;
Candy
}
}
22
2分探索木のサーチ (再帰版)
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)==0)
if (p==NULL || strcmp(key,p->name)==0)
if
(p==NULL
return
p; || strcmp(key,p->name)==0)
return p;
return p;
if (strcmp(key,p->name)<0)
if (strcmp(key,p->name)<0)
if
(strcmp(key,p->name)<0)
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);
}
}
}
Machilda
p
Rolla
p: NULL
23
2分探索木のトラバーサル (深さ優先)
 トラバーサル (traversal):木の全てのノードを訪れるこ
と (木の走査)
 深さ優先探索:「左向きにとにかく進んで,端に来たら 1
つ前の親に戻って右に進む」という行動を繰り返す.
 再帰的に記述すると,関数 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 の右の子を起点として再帰呼出
}
}
24
2分探索木のトラバーサル (深さ優先)
 ノード内容表示の順序次第で,表示順序が変わる
 行きがけ順
void treewalk(struct tnode *p)
{
if (p!=NULL){
printf("%s\n",p->name);
treewalk(p->left);
treewalk(p->right);
}
}
p: NULL
p
Machilda
p
p
Emy
p
Rolla
p
Candy
画面表示
Lisa
Machilda
Emy
Candy
Lisa
Rolla
25
2分探索木のトラバーサル (深さ優先)
 ノード内容表示の順序次第で,表示順序が変わる
 通りがけ順
void treewalk(struct tnode *p)
{
if (p!=NULL){
treewalk(p->left);
printf("%s\n",p->name);
treewalk(p->right);
}
}
p: NULL
p
Machilda
p
p
Emy
p
Rolla
p
Candy
画面表示
アルファベット順 
Lisa
Candy
Emy
Lisa
Machilda
Rolla
26
ヒープ
 ヒープ (heap:山,堆積) とは,すべての親が必ず2つの
子を持つ (最後の要素は左の子だけでも良い) 完全2分木で,
どの親と子をとっても,親≦子になっている木を言う.
1
2
4
配列表現:
10
ノードを深さごとに
左から順に配列に格
納する
3
25
15
5
30
6
26
7
20
29
※ ヒープにおいては添え字は
0 でなく 1 から始める.
35
40
27
28
22
こうすると,子 s の親 p は,
p=s/2 で求まる.
1
2
3
4
5
6
7
8
9
10 11 12
10 25 15 30 26 20 29 35 40 27 28 22
例)11/2=5 (整数演算)
8
p.303-307
9 10
11
12
27
ヒープへのデータ追加 (上方移動)








既に存在するヒープへ新規データを追加することを考える.
その手順は以下の通りである:
(1) 新しいデータをヒープの最後の要素として格納する.
(2) その要素を子とする親のデータと比較し,親の方が大
きければ子と親を交換する.
(3) 次に,その親を子とする親 (おじいちゃん) との間で
比較を行い,必要があれば交換.これを,子の位置が根ま
で上がるか,親≦子になるまで繰り返す.
教科書 p.304 の図6.13を参照せよ.
この手順を上方移動 (shift up) という.
ソースコードは p.305.
28
ヒープへのデータ追加 (上方移動)
 (1) 新しいデータをヒープの最後の要素として格納する.
 (2) その要素を子とする親のデータと比較し,親の方が大きければ子と親
を交換する.
 (3) 次に,その親を子とする親 (おじいちゃん) との間で比較を行い,必
要があれば交換.これを,子の位置が根まで上がるか,親≦子になる
まで繰り返す.
1
10
25
12
4
30
12
25
35
9
30
12
15
5
26
8
3
2
6
20
7
29
s= 2
4
9
p= 1
4
2
29
ヒープの作成 (下方移動)
 上方移動では既存のヒープにデータを一つずつ追加することに
よりヒープを作成したが,既存の全データをそのまま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) へ戻る.
30
ヒープの作成 (下方移動)
 図的に理解しよう.  (1) 子を持つ最後の親から開始してループ
(最初は 9/2 = 4 から)
 (2) 親の番号を p とし,2p と 2p+1 で小
さい方の子を s とする.
 (3) s が p より大きいときは (1) ループで
次へ.
1
2
3
i= 4
p= 6
2
7
4
8
1
3
s= 12
7
14
4
8
16
6
3
7
1
2
4
2
4
3
2
3
4
8
4
9
1
 (4) p と s を交換し,p=s, s=2p とする.
1
7
6
8
2
5
9
5
7
6
6
s>n なら (1) ループで次へ.
s<=n なら (2) へ.
3
8
1
7
(2) から (4) の手順を
下方移動 (shift down)
と呼ぶ
ソースコード:p.307
31
ヒープ・ソート
 ヒープを用いたソーティングアルゴリズムがヒープ・ソー
トである.手順は大まかに以下の通り:
(1)与えられた数列からヒープを作成する.
(2)根ノードには最小値が来ているはずなので, これを取り外
す.その代わり,最後のノード (データ数 n なら n番の要
素) を切り離して根ノードに持ってくる.
(3)これにより残ったデータ (n-1個) のヒープ条件が狂った
ので,下方移動を使ってヒープの修正を行う. この場合,
根ノードからの1回の下方移動を行うだけでよい.
(4)(2) に戻る.
 教科書 p.308 の図6.15 を参照せよ.
p.308-311
32
ヒープ・ソート (ソースコード)
 p.309.
 関数 swap() は2つの配列要素の交換.
 main関数内,最初の whileループは初期ヒープの作成.
データを入れるごとに,入れたデータを最後尾に格納した
上で,上方移動を使ってヒープを整える作業を繰り返して
いる.
 2つめの whileループは,データを取り出すごとのループ.
 最初にルート (1番) と最後尾 (n番) を交換して,最後尾
をヒープから除外している (n--).
 次のループは,視点 p を根に初期化して下方移動を1回
行っている部分.
 p.311 では,初期ヒープ作成を下方移動で行っている.
33
第7章:グラフ
 リスト構造は,ノード群を鎖状につないだもので,分岐は
なかった.一方木構造は分岐はするが,分岐した枝同士は
分かれたまま.
 これらをより一般化したものがグラフ (graph) である.
グラフでは,ノード間の連結は任意であり,ループを含む
こともある.
6
2
5
4
1
8
7
3
p.331-333
34
グラフとは
 円で描いた部分はノード (node 節点,vertex 頂点ともい
う) であり,それを結んでいるのは エッジ (edge 辺,
branch 枝) である.ノード1と2はつながっているが,1
と3はつながっていない.
エッジ
ノード
6
2
5
4
1
8
7
3
35
グラフとは
 グラフをデータとして表現するときに使われるのは隣接行
列 (adjacency matrix) である.ノード i と j の間に接続
がある場合は 1,ない場合は 0 としておく.
2
4
1
3
5
6
教科書ではノード番号は1からとしている.
j
8
7
対角成分は,同じノードへの接続をあると
するかどうかに関係する (この場合はなし
としている).
1 2 3
4 5 6 7
8
1
0
1
0
0
0
0
0
0
2
1
0
1
1
0
0
0
0
3
i 4
5
0
1
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
1
0
0
6
0
0
0
0
1
0
1
1
7
8
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
0
36
グラフとは
 ここまでの例では,グラフのエッジには向きはなかった.
このようなものを無向グラフ (undirected graph) という.
 これに対して,「進める方向」のような向きを含んだグラ
フを有向グラフ (directed graph) という.この場合,隣
接行列は,ノード i から j へのエッジに対して,要素 (i,
j) は 1,要素 (j, i) は 0 としておく (p.333 図7.4).
6
2
5
4
1
8
7
3
37
深さ優先探索
 グラフのノードにデータが記載されている場合,この中か
ら特定のデータを探すとき,グラフの全てのノードを巡る
というアルゴリズムが必要となる.
 その一つは 深さ優先探索 (depth first search, 縦型探索
とも呼ばれる) である.
(1)始点を出発し,ノード番号の若い順に進む位置を調べ,い
けるところ (エッジで連結されていてまだ訪問していない
ノード) まで進む.
(2)行き場所がなくなったら,まだいける方向の残っている分
岐点まで戻り,再びいけるところまで進む.
(3)行き場所が全てなくなったら終了 (来た道を戻る).
p.334-338
38
深さ優先探索
 どのように探索が進むかを図で見てみよう.
(1) 始点を出発し,ノード番号の若い順に進む位置を調べ,いけるところ
(エッジで連結されていてまだ訪問していないノード) まで進む.
(2) 行き場所がなくなったら,まだいける方向の残っている分岐点まで戻
り,再びいけるところまで進む.
(3) 行き場所が全てなくなったら終了 (来た道を戻る).
2
4
1
3
5
6
8
7
39
深さ優先探索の再帰的解法
 深さ優先探索を再帰
的に行う関数は右の
通り.
 未探索の行き先を順
番に探して,行ける
ときは再帰呼び出し
でそこに進む.
 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);
}
}
2
1
j= 2
4
j= 3
5
j= 4
6
j= 8
5
8
3
7
j= 7
j= 6
40
深さ優先探索 (ソースコード)
 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)).
41
深さ優先探索の応用
 グラフ上の各ノードを起点として深さ優先探索を繰り返す
場合は,各探索の前に訪問済みフラグを下ろして置かなく
てはならない.
 p.337 図7.6 のように,ノード群が分かれているグラフを
非連結グラフと呼ぶ.これがどのように分かれているかを
調べるには,訪問済みフラグのリセットをせずに,各ノー
ドを起点とする探索を繰り返せばよい.
 探索の起点となるノードが訪問済みの場合は次のノードへ
進む.訪問済みでないときは,カウントを1つ進める.
 これにより,カウント数=分かれている集団の数となる.
42
幅優先探索
 幅優先探索 (breadth first search,横型探索とも言う) で
は,「これから進まなくてはならないノードのメモ」を
キューの中に保存し,それを参照しながら探索を進める.
(1)始点をキューに入れる.
(2)キューからノードを取り出し,そのノードに連結している
未訪問のノードを全てキューに入れておく.
(3)キューが空なら終了,そうでないときは (2) へ.
 これにより,始点から近いノードから順序よく探索が進め
られる.
p.339-342
43
幅優先探索
(1)始点をキューに入れる.
(2)キューからノードを取り出し, 訪問済みとする. そのノー
ドに連結している未訪問ノードを全てキューに入れておく.
(3)キューが空なら終了,そうでないときは (2) へ.
ソースコード:p.340-341
6
2
5
4
1
8
7
3
キュー:
1
2
3
4
5
7
6
8
44
トポロジカル・ソート
 グラフを見ると,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
1
3
p.343-345
8
4
7
45
トポロジカル・ソート
 半順序関係が与えられたデータに対して,最初に行う仕事
から最後に行う仕事を1列に並べることをトポロジカル・
ソート (topological sort) という.
 どちらを先にやっても良い部分が含まれているので,解は
1つとは限らず,どれかが得られればよい.
2
5
6
8
4
1
3
7
46
トポロジカル・ソート
 有向グラフに対する深さ優先探索を繰り返し実行し,行き
着いたところから来た道を戻ろうとするときに,そのノー
ドを記録していけばよい.
 記録は「最後に行き着く場所」から順に行われるので逆
順.
2
6
5
8
4
1
7
3
2
5
6
8
1
3
7
4
47
Euler の一筆書き
 辺を消しながら深さ優先探索を行い,出発点に戻った
時に全ての経路が消えていれば,そのとき通った経路
が求める経路である
スタック v[n]
1
1
2
3
p.348-350
4
1
2
4
3
2
1
4
ソースコード:p.350
ネットワーク
 各辺に重みが定義されているグラフを 重み付きグラフ
あるいは ネットワーク (network) と呼ぶ.
 重みの意味は,例えば道路網については道路の長さであっ
たり,水道網なら流量だったりである (p.359 図7.22).
1 2 3 4 5 6 7 8
 データの実体は,重み行列 で
1 0 1 7 2 M M M M
記述する.
e
2
b
1
7
a
1
4
f
2
6
d
2
3
c
5
2
g
h
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:無限大)
49
最短路問題 (Dijkstra のアルゴリズム)
解きたい問題:ノード a から h までの最短距離を求める
全てのノードの確定フラグを下ろし, 距離値を無限大で初期化
スタートノードの距離値を 0 とする.(3), (4) を N 回繰り返す
距離値最小の未確定ノードの番号を p とし,確定フラグを立てる
p につながる全ノードについて,p から進んだときの距離値が現在の
距離値より小さくなるとき,そのノードの距離値を更新する
 あるノードの距離値を更新するとき,
M
3
距離値だけでなく「この距離値に
M 2
1
e
なる場合,直前のノードはこれ」と
1
b
4
いう「手前ノード情報」も記録する
M
5
4
1
f
 距離だけでなく経路も求まる
2

(1)
(2)
(3)
(4)
a
M 7
0
2
c
p.353-359
6
d 7
M
6
M
2
3
5
2
g
10
M
9
h
M
7
50
最短路問題の例
 障害物環境下での移動ロボットのナビゲーション
 コンフィギュレーション障害物の頂点をサブゴールとし,
可視グラフ (visibility graph) を構築,最短路を探索
sub-goal
obstacle
start
移動ロボットのナビゲーション
を主にやってるとこ:城間研
obstacle
goal
configuration obstacle
51
講義のおわりに
 本講義では,知能システム工学科の趣旨に則って,メカと
情報の融合分野を扱う上でのアルゴリズム・データ構造を
実践的に (ソース・コードをベースとして) 解説した.
 情報工学科における同名の講義とは異なり,理論的な議論
はほとんど行っておらず,情報に興味のある学生にとって
は不十分である.
 一方,組み込みシステムなど,ハードウェアに近いプログ
ラミングでは,マイコンや電子回路など,多くのハード
ウェアに関する知識が必要となる.
 それらについては,各自が必要に応じてより深く勉強する
こと.本講義は基礎の基礎しか扱っていない.
 講義終了後もアルゴリズム・データ構造に関する質問は随
時受け付ける.
52