情報数学（第13回） （根つき）木.

Presentation on theme: "情報数学（第13回） （根つき）木."— Presentation transcript:

1 情報数学（第13回） （根つき）木

2 有向木 有向木： 逆有向辺を含む閉路を持たない連結有向グラフ 根（root）: 入次数が0の節点（入口）
教科書p. 170■木 有向木 有向木：　逆有向辺を含む閉路を持たない連結有向グラフ 　根（root）: 入次数が0の節点（入口） 　葉（leaf）: 出次数が0の節点（出口） 　分岐節点：それ以外 葉 根 分岐 節点 辺が上から下に向くよう節点を配置し辺の向きを省略する

3 根付き木 根付き木（rooted tree） ： 根を一つだけ持つ有向木 次数2 分岐節点 葉 根から各々の葉に至る有向順路がちょうど一つ
教科書p. 170■根付き木 根付き木 根付き木（rooted tree） ：　根を一つだけ持つ有向木 次数2 分岐節点 葉 根から各々の葉に至る有向順路がちょうど一つ

4 根付き木 根付き木（rooted tree） ： 根を一つだけ持つ有向木 深さ 0 深さ 1 深さ 2 深さ 3
教科書p. 170■根付き木 根付き木 根付き木（rooted tree） ：　根を一つだけ持つ有向木 深さ　0 深さ　1 深さ　2 深さ　3 節点の深さ（高さ）：根からの順路の長さ

5 教科書p. 171■根付き木 根付き木の部分木 根付き木 𝑇 の任意の連結部分グラフはやはり木であり、𝑇 の部分木（subtree）という。多くの場合、ある分岐節点とその節点から有向順路があるすべての節点からなるもののみを考える 𝑎の枝 ともいう 𝑎 部分木と 言わないことが 多い 𝑑を根とする 部分木 𝑑

6 教科書p. 171■根付き木 親節点　子節点　兄弟節点 兄弟（姉妹） 節点 親（上位）節点 子（下位） 節点

7 教科書p. 171■根付き木 親子関係と祖先子孫関係 親子関係を推移律を満たすよう拡張した関係（推移閉包）を祖先子孫関係という。さらに反射律を満たすように拡張した関係（反射推移閉包）を祖先子孫関係と言う場合もある 祖先 推移閉包の場合 親 子 子孫

8 教科書p. 171■根付き木 親子関係と祖先子孫関係 親子関係を推移律を満たすよう拡張した関係（推移閉包）を祖先子孫関係という。さらに反射律を満たすように拡張した関係（反射推移閉包）を祖先子孫関係と言う場合もある 祖先 反射推移閉包の場合 親 子孫 子 半順序関係

9 分岐次数、𝑛分木 節点の（分岐）次数： 節点の出次数（子の数） 葉以外のすべて次数が 𝑛 （正則）𝑛分木 𝑛以下 𝑛分木とよぶ場合もある
教科書p. 171■根付き木 分岐次数、𝑛分木 節点の（分岐）次数：　節点の出次数（子の数） 葉以外のすべて次数が 𝑛 （正則）𝑛分木 　 𝑛以下 𝑛分木とよぶ場合もある （正則）3分木 3分木とよぶ場合もある

10 2分決定木（診断木） 条件（質問） yes no 条件（質問） 条件（質問） no yes yes no 条件（質問） 条件（質問）
教科書p. 171■根付き木 2分決定木（診断木） 条件（質問） yes no 条件（質問） 条件（質問） no yes yes no 条件（質問） 条件（質問） 条件（質問） 結論 yes no yes no yes no 条件（質問） 結論 結論 結論 結論 結論 yes no 結論 結論

11 2分探索木 左（右）の枝には自身より小さい（大きい）データを 収容することによりデータ探索を効率化する方法 <4 4<
平成31年度春季基本情報処理技術者試験問題 2分探索木 <4 4< <2 2< <8 8< <6 6< 左（右）の枝には自身より小さい（大きい）データを 収容することによりデータ探索を効率化する方法

12 順序木（ordered tree） 順序木：木の兄弟節点間に全順序の上下関係を導入したもの 𝑎 通常、左が上位 𝑏1 𝑏2 𝑏3 𝑐1 𝑐2
教科書p. 172■順序木 順序木（ordered tree） 順序木：木の兄弟節点間に全順序の上下関係を導入したもの 𝑎 通常、左が上位 𝑏1 𝑏2 𝑏3 𝑐1 𝑐2 𝑐3 𝑐4 𝑐5 𝑑1 𝑑2 𝑑3

13 順序木の継承関係 ・祖先は子孫より上位 ・兄およびその子孫は弟より上位 を満たす全順序関係
教科書p. 172■順序木 順序木の継承関係 ・祖先は子孫より上位 ・兄およびその子孫は弟より上位 を満たす全順序関係 兄弟間の上下関係をそれらの子孫が継承する「継承関係」 𝑎 𝑏1 𝑏2 𝑏3 𝑐1 𝑐2 𝑐3 𝑐4 𝑐5 𝑑1 𝑑2 𝑑3 𝑎≥ 𝑏 1 ≥ 𝑐 1 ≥ 𝑐 2 ≥ 𝑑 1 ≥ 𝑑 2 ≥ 𝑏 2 ≥ 𝑐 3 ≥ 𝑑 3 ≥ 𝑐 4 ≥ 𝑏 3 ≥ 𝑐 5

14 木、順序木の同型 木としては同型 順序木としては 同型でない 4つの節点からなる同型でない根付き木は4通り 順序木は5通り
教科書p. 172側注■同型でない順序木 木、順序木の同型 木としては同型 順序木としては 同型でない 4つの節点からなる同型でない根付き木は4通り 　 順序木は5通り

15 演習3, 5 異なる（同型でない）根付き木について、次の問いに答えよ (1) 節点が2個あるいは3個からなる根付き木をすべて描け
教科書p. 180■演習問題 演習3, 5 異なる（同型でない）根付き木について、次の問いに答えよ (1) 節点が2個あるいは3個からなる根付き木をすべて描け 4個の節点で構成される根付き木をすべて描け (3) 5個の節点で構成される根付き木はいくつあるか 異なる（同型でない）順序木について、次の問いに答えよ (1) 節点が2個あるいは3個からなる順序木をすべて描け 4個の節点で構成される順序木をすべて描け (3) 5個の節点で構成される順序木はいくつあるか

16 構文木（タイプ1） 演算子が親、被演算子が子とすることで数式の構造を表現 + 葉： 数値や変数 それ以外： 演算子 − ×
教科書p. 173■構文木 構文木（タイプ1） 演算子が親、被演算子が子とすることで数式の構造を表現 + 葉： 数値や変数 それ以外： 演算子 − × 部分木も数式（部分式） ÷ 1 − 𝑧 演算子が2項演算のみなら 　　　　2分木 𝑥 2 9 4 𝑥÷2−1+(9−4)×𝑧

17 構文木（タイプ2） 葉に単語、その他の節点に文法概念を割り当て句構造を表現
教科書p. 173■構文木 構文木（タイプ2） 葉に単語、その他の節点に文法概念を割り当て句構造を表現 文 動詞句 名詞句 前置詞句 前置詞句 名詞句 名詞句 名詞句 I saw a man on the hill with a telescope I saw a man on the hill with a telescope

18 構文木（タイプ2） 葉に単語、その他の節点に文法概念を割り当て句構造を表現
教科書p. 173■構文木 構文木（タイプ2） 葉に単語、その他の節点に文法概念を割り当て句構造を表現 文 動詞句 名詞句 前置詞句 前置詞句 名詞句 名詞句 名詞句 I saw a man on the hill with a telescope I saw a man on the hill with a telescope 構造によって文の意味が違ってくる

19 順序木のリスト表現 リスト（list）: 成分をカンマで区切って列挙し、カッコでくくったもの 成分としてリストを許すものを再帰リストという
教科書p. 174■構文木のリスト表現 順序木のリスト表現 リスト（list）: 成分をカンマで区切って列挙し、カッコでくくったもの 成分としてリストを許すものを再帰リストという アトム（atom）またはリスト 順序木のリスト表現：　 　　第1成分を親、第2成分以降に兄から順に子を列挙したもの 𝑎 𝑎 𝑏 𝑒 𝑏 𝑑 𝑔 𝑐 𝑑 𝑐 𝑒 𝑓 ℎ (𝑎, 枝𝑏, 𝑒) (𝑎, (𝑏, 𝑐, 𝑑), 𝑒) (𝑎, 枝𝑏, 枝𝑑) (𝑎, (𝑏, 𝑐), 枝𝑑) (𝑎, 𝑏, 𝑐 , 𝑑, 𝑒, 𝑓, 枝𝑔 ) (𝑎, 𝑏, 𝑐 , 𝑑, 𝑒, 𝑓, 𝑔,ℎ )

20 演習７ 次のリストの表す順序木を描け (1) (𝑎,𝑏,𝑐,𝑑) (2) (𝑎, 𝑏, 𝑐,𝑑 ) (3) (𝑎, 𝑏,𝑐 , 𝑑,𝑒 )
教科書p. 181■演習問題 演習７ 次のリストの表す順序木を描け (1)　(𝑎,𝑏,𝑐,𝑑) (2)　(𝑎, 𝑏, 𝑐,𝑑 ) (3)　(𝑎, 𝑏,𝑐 , 𝑑,𝑒 ) (4)　(𝑎, 𝑏, 𝑐,𝑑,𝑒 , 𝑓,𝑔 ) (5)　(𝑎, 𝑏, 𝑐,𝑑 ,𝑒 ,(𝑓, 𝑔,ℎ,𝑖 ),𝑗) 教科書の解答: (5)は間違い 正しくは右図 𝑎 𝑏 𝑓 𝑗 𝑐 𝑒 𝑔 𝑑 ℎ 𝑖

21 構文木（タイプ1）のリスト表現 + − × ÷ 1 − 𝑧 𝑥 2 9 4 (+, −, ÷,𝑥,2 ,1 , 𝑥, −,9,4 ,𝑧 )
教科書p. 174■構文木のリスト表現 構文木（タイプ1）のリスト表現 + − × ÷ 1 − 𝑧 𝑥 2 9 4 (+, −, ÷,𝑥,2 ,1 , 𝑥, −,9,4 ,𝑧 ) 前置記法、ポーランド記法

22 離散グラフの探索 洞窟のような迷路を離散グラフでモデル化し、開始節点から目標節点（複数あってもよい）への順路を見つける問題
教科書p. 175■グラフの探索と探索木 離散グラフの探索 洞窟のような迷路を離散グラフでモデル化し、開始節点から目標節点（複数あってもよい）への順路を見つける問題 ・グラフに沿って移動 ・通過した節点は区別できる S A B C D E F G H 迷路

23 離散グラフの探索 迷路 探索木 S A S A B C B D D E F C E G H F G H
教科書p. 175■グラフの探索と探索木 離散グラフの探索 S A S A B C B D D E F C E G H F G H 迷路 探索木

24 横型探索（BFS: Breadth First Search）
教科書p. 176■横型探索と縦型探索 横型探索（BFS: Breadth First Search） 深さを1段ずつ成長させることにより探索木を生成 　　（幅優先探索） S C A S A B D F B D C D E D C G E F G C 迷路 横型探索木

25 縦型探索（DFS: Depth First Search）
葉（行き止まり）に至る順路を順次生成することにより探索木を構成 （深さ優先探索） S A C S A B C B D C D E E C F G S F S 迷路 G 縦型探索木

26 BFS, DFSのデータ構造とアルゴリズム 【データ構造】 open: 接続先未調査節点のリスト （初期状態：Sのみ）
close: 調査済み節点のリスト （初期状態：空） 親節点の情報こみでリストに収容 【アルゴリズム】 BFS: Open中の節点をFIFOで調査 DFS: Open中の節点をLIFOで調査 既にClose中にある節点は ・Openに追加しない ・再調査しない 終了時のCloseを基に探索木が構成できる

27 横型探索 Sを調査 ・Sをopenからcloseへ移動 ・openの末尾に Sからの接続先A[S], C[S]を追加 親節点
o: open, c: close S A B C D E F G o(S[]) c() o(A[S],C[S]) c(S[]) Sを調査 ・Sをopenからcloseへ移動 ・openの末尾に 　Sからの接続先A[S], C[S]を追加 親節点 S C A

28 横型探索 Aを調査 ・Aをopenからcloseへ移動 ・openの末尾に Aからの接続先B[A], D[A]を追加
o: open, c: close S A B C D E F G o(S[]) c() o(A[S],C[S]) c(S[]) o(C[S],B[A],D[A]) c(S[],A[S]) Aを調査 ・Aをopenからcloseへ移動 ・openの末尾に 　Aからの接続先B[A], D[A]を追加 S C A B D

29 横型探索 o: open, c: close S A B C D E F G o(S[]) c() o(A[S],C[S]) c(S[])
o(C[S],B[A],D[A]) c(S[],A[S]) o(B[A],D[A],D[C],F[C]) 　　c(S[],A[S],C[S]) o(D[A],D[C],F[C],E[B]) 　　c(S[],A[S],C[S],B[A]) S o(D[C],F[C],E[B]) 　　　c(S[],A[S],C[S],B[A],D[A]) C A o(E[B],G[F]) c(S[],A[S],C[S], B[A],D[A],F[C]) D F B D D o(G[F]) c(S[],A[S],C[S], B[A],D[A],F[C],E[B]) C G E o() c(S[],A[S],C[S], B[A],D[A],F[C],E[B],G[F]) C

30 縦型探索 Aを調査 ・Aをopenからcloseへ移動 ・openの先頭に Aからの接続先B[A], D[A]を追加
o: open, c: close S A B C D E F G o(S[]) c() o(A[S],C[S]) c(S[]) o(B[A],D[A],C[S]) c(S[],A[S]) Aを調査 ・Aをopenからcloseへ移動 ・openの先頭に 　Aからの接続先B[A], D[A]を追加 S A C B D

31 縦型探索 o: open, c: close S A B C D E F G o(S[]) c() o(A[S],C[S]) c(S[])
o(B[A],D[A],C[S]) c(S[],A[S]) o(E[B],D[A],C[S]) c(S[],A[S],B[A]) o(D[A],C[S]) c(S[],A[S],B[A],E[B]) S A C o(C[D],C[S]) 　　　c(S[],A[S],B[A],E[B],D[A]) C B D o(F[C],C[S]) c(S[],A[S],B[A], E[B],D[A],C[D]) E C o(G[F],C[S]) c(S[],A[S],B[A], E[B],D[A],C[D],F[C]) S F S G o(C[S]) c(S[],A[S],B[A], E[B],D[A],C[D],F[C],G[F])

32 ゲーム木 現在の盤面 1手先 の盤面 2手先 の盤面 ○ × ○ × ○ × ○ × ○ × ○ ×
教科書p. 175■グラフの探索と探索木 ゲーム木 ○ × 現在の盤面 ○ × ○ × 1手先 の盤面 ○ × ○ × ○ × 2手先 の盤面

33 今日のまとめ ・有向木、根付き木の基本的事項 根・分岐節点・葉、部分木、節点の深さ、グラフの高さ 親子関係、祖先子孫関係 分岐次数と𝑛分木
　根・分岐節点・葉、部分木、節点の深さ、グラフの高さ 　親子関係、祖先子孫関係 　分岐次数と𝑛分木 ・順序木 　全順序継承関係、同型な順序木 ・2種類の構文木（数式の表現、英文の句構造の表現）　 ・順序木のリスト表現 ・グラフ（迷路）の探索 　横型（幅優先）探索と縦型（深さ優先）探索 　探索のためのデータ構造とアルゴリズム

34 来週 第1週に配布した 「情報数学講義資料」 を持参すること