Skip to main content

04．二分木・巡回・経路探索

8．二分木と二分探索木

二分木・二分探索木の板書

二分木（Binary Tree）は、各Nodeが最大2つの子を持つ木です。二分探索木（Binary Search Tree: BST）では、値の大小関係を使って探索しやすい形にします。

Q41．二分木の特徴は？

二分木の説明として正しいものを選んでください。

  • A．各Nodeが持てる子は最大2つ
  • B．必ずNodeが2個しかない
  • C．必ず左の子しか持てない
  • D．グラフではない
答え

A

Q42．二分探索木のルールを穴埋めしよう

一般的な二分探索木では、あるNodeの値を基準に、

  • 小さい値 → ＿＿側
  • 大きい値 → ＿＿側

へ配置します。

答え
  • 小さい値 → 左
  • 大きい値 → 右

Q43．BSTを作ってLeafを見つけよう

空の二分探索木へ 5, 3, 7, 2, 4, 6, 8 の順に値を入れました。この木で**Leaf（子を持たないNode）**になる値をすべて選んでください。

  • A．2
  • B．3
  • C．4
  • D．5
  • E．6
  • F．7
  • G．8
答え

A・C・E・G（2・4・6・8）

      5
    /   \
   3     7
  / \   / \
 2   4 6   8

Q44．BSTで6を探そう

Q43の二分探索木で値6を探します。たどるNodeの順番を選んでください。

  • A．5 → 3 → 2 → 6
  • B．5 → 7 → 6
  • C．5 → 4 → 6
  • D．8 → 7 → 6
答え

B．5 → 7 → 6

6は5より大きいので右へ、7より小さいので左へ進みます。

Q45．線形探索との違いは？

整った二分探索木を使う利点として適切なものを選んでください。

  • A．大小比較によって探索する範囲を絞れる
  • B．必ず1回の比較で見つかる
  • C．値を比較する必要がない
  • D．どんな形でも探索回数は必ず同じ
答え

A

ただし、木が片側に偏ると効率が悪くなる場合があります。

9．木の巡回順を整理しよう

BFS・DFSと木の巡回の板書

二分木では、Nodeの値をいつ取り出すかによって、代表的な3種類の巡回順があります。

Q46．巡回の名前を対応させよう

日本語 英語・処理順
行きがけ順 ＿＿＿＿＿＿
通りがけ順 ＿＿＿＿＿＿
帰りがけ順 ＿＿＿＿＿＿

選択肢：Preorder（親→左→右）・Inorder（左→親→右）・Postorder（左→右→親）

答え
  • 行きがけ順 → Preorder（親→左→右）
  • 通りがけ順 → Inorder（左→親→右）
  • 帰りがけ順 → Postorder（左→右→親）

Q47．行きがけ順で読もう

次の二分木を行きがけ順（Preorder）で巡回してください。

      5
    /   \
   3     7
  / \   / \
 2   4 6   8

答え：＿＿ → ＿＿ → ＿＿ → ＿＿ → ＿＿ → ＿＿ → ＿＿

答え

5 → 3 → 2 → 4 → 7 → 6 → 8

Q48．通りがけ順で読もう

Q47の木を通りがけ順（Inorder）で巡回してください。

答え

2 → 3 → 4 → 5 → 6 → 7 → 8

二分探索木をInorderで巡回すると、値を昇順に取り出せます。

Q49．帰りがけ順で読もう

Q47の木を帰りがけ順（Postorder）で巡回してください。

答え

2 → 4 → 3 → 6 → 8 → 7 → 5

10．探索アルゴリズムを整理しよう

ここでは、授業で詳しく扱った BFS と DFS を中心に整理します。
Dijkstra と A* は、名前と「どんな経路探索に使うものか」という概要だけ確認しましょう。

Q50．BFSとDFSの特徴を対応させよう

次の特徴を、BFSとDFSに対応させてください。

特徴 BFS / DFS
Startに近いNodeから順に広げていく ＿＿＿＿＿＿
1本の経路を深く進み、行き止まりなら戻る ＿＿＿＿＿＿
Queue と相性がよい ＿＿＿＿＿＿
Stack と相性がよい ＿＿＿＿＿＿
答え
  • Startに近いNodeから順に広げる → BFS
  • 1本の経路を深く進む → DFS
  • Queue → BFS
  • Stack → DFS

BFSは幅方向、DFSは深さ方向へ探索するため、Nodeを取り出す順序を作るデータ構造も異なります。

Q51．DijkstraとA*は何をする探索？

Dijkstra（ダイクストラ）法とA*（Aスター）について、授業で扱った範囲として最も適切な説明を選んでください。

  • A．移動コストなどを考えながら、目的地までの経路を探すために使われる
  • B．二分木を必ず昇順に並べ替えるためだけに使われる
  • C．キャラクターのアニメーションを補間するために使われる
  • D．描画するポリゴン数を数えるために使われる
答え

A

DijkstraやA*は、ゲームのマップなどで目的地までの経路を探すアルゴリズムとして使われます。

  • Dijkstra：移動にかかるコストを考えて経路を探す
  • A*：コストに加えて、ゴールの方向を意識して探索する考え方を持つ

このワークでは、細かな計算方法までは覚えなくて構いません。

Q52．BFSとDFSを状況から選ぼう

次の場面では、BFSとDFSのどちらの考え方が向いているでしょう。

場面 BFS / DFS
すべての移動を1回として数え、StartからGoalまでの最短手数を探したい ＿＿＿＿＿＿
とりあえず1本の経路を奥まで調べ、行き止まりなら戻りたい ＿＿＿＿＿＿
Startから距離1、距離2、距離3……の順にNodeを調べたい ＿＿＿＿＿＿
再帰やStackを使って、子へ子へと深くたどりたい ＿＿＿＿＿＿
答え
  • 最短手数を探す → BFS
  • 1本の経路を奥まで調べる → DFS
  • 距離の近い順に調べる → BFS
  • Stackで深くたどる → DFS

重みのないグラフでは、BFSはStartから近いNodeを順に調べるため、最短手数の経路を見つける用途にも使えます。

11．最後に整理しよう

Q53．ゲームでやりたいことと仕組みを対応させよう

ゲームでやりたいこと 使う考え方・仕組み
敵の待機・追跡・攻撃を状態で整理したい ＿＿＿＿＿＿
状態ごとの処理を別クラスに分けたい ＿＿＿＿＿＿
判断や行動を木構造として組みたい ＿＿＿＿＿＿
近いNodeから広げて探索したい ＿＿＿＿＿＿
1本の経路を深く探索したい ＿＿＿＿＿＿
先入れ先出しでNodeを管理したい ＿＿＿＿＿＿
後入れ先出しでNodeを管理したい ＿＿＿＿＿＿
二分探索木を昇順に読みたい ＿＿＿＿＿＿
移動コストを考える経路探索として名前を知っておきたい ＿＿＿＿＿＿

選択肢：FSM・Stateパターン・Behavior Tree・BFS・DFS・Queue・Stack・Inorder・Dijkstra / A*

答え
  • 状態で整理 → FSM
  • 状態ごとにクラス分割 → Stateパターン
  • 木構造で判断・行動 → Behavior Tree
  • 近いNodeから探索 → BFS
  • 深く探索 → DFS
  • 先入れ先出し → Queue
  • 後入れ先出し → Stack
  • BSTを昇順に読む → Inorder
  • 移動コストを考える経路探索 → Dijkstra / A*

Q54．AIの処理を1本の流れとして組み立てよう

次の敵AIを考えます。

敵は普段巡回している。プレイヤーが索敵範囲と視野内に入ったら追跡状態へ移る。障害物のあるマップでは目的地までの経路を探索して移動する。十分近づいたら攻撃状態へ移る。

このAIを作る処理の流れとして最も適切なものを選んでください。

  • A．距離や内積などでプレイヤーを検出 → FSMで Patrol から Chase へ遷移 → 必要なら目的地までの経路を探索 → 経路に沿って移動 → 攻撃条件を満たしたら Attack へ遷移
  • B．最初に攻撃を実行 → 描画結果からStateを決定 → 最後にプレイヤーの位置を調べる
  • C．DFSでStateそのものを作成 → Queueで視野角を計算 → 二分探索木で攻撃状態へ遷移する
  • D．経路探索だけを実行すれば、索敵・状態遷移・攻撃判断もすべて自動的に行われる
答え

A

ゲームAIでは、1つの仕組みだけですべてを行うのではなく、状況を調べる → 状態や行動を決める → 必要なら経路を探す → 実際に行動するという複数の処理を組み合わせます。

No Comments
Back to top
Entity Select