03．グラフ・木・BFS・DFS

5．ゲームAIで使う探索の考え方

ゲームAIには、ルール、状態、Behavior Tree、ゴール、効用など、さまざまな考え方があります。また、移動経路を求めるAIでは、グラフ探索が重要になります。

Q27．AIの考え方を具体例と対応させよう

次の例を、それぞれどのAIの考え方に近いか対応させてください。

例	考え方
「HPが30%未満なら逃げる」のような条件とルールで決める	＿＿＿＿＿＿
Idle、Chase、Attack を切り替える	＿＿＿＿＿＿
「攻撃できる→攻撃、できない→追跡」のように行動を木で組み立てる	＿＿＿＿＿＿
攻撃・回復・逃走に点数を付け、最も高い行動を選ぶ	＿＿＿＿＿＿

選択肢：ルールベース・ステートベース・ビヘイビアベース・ユーティリティベース

答え

• 条件とルール → ルールベース
• 状態と遷移 → ステートベース
• 行動を木で構成 → ビヘイビアベース
• 点数で評価 → ユーティリティベース

Q28．ゲームマップをグラフに置き換えよう

道路の交差点A・B・Cと、それらを結ぶ道を使って経路探索したいとします。グラフとして表現するときの対応として最も適切なものを選んでください。

• A．交差点をNode、道をEdge、移動距離や時間をEdgeのコストとして持たせる
• B．交差点をEdge、道をNodeとして持たせる
• C．すべての交差点をRootとして扱う
• D．地点どうしのつながりを記録しない

答え

A

経路探索では、どこへ行けるかと、必要ならどれだけコストがかかるかをグラフとして表します。

---

6．グラフと木の用語を整理しよう

Q29．用語を対応させよう

用語	意味
Node	＿＿＿＿＿＿
Edge	＿＿＿＿＿＿
Root	＿＿＿＿＿＿
Leaf	＿＿＿＿＿＿

選択肢：点・点どうしのつながり・木の始点となる節点・子を持たない節点

答え

• Node → 点
• Edge → 点どうしのつながり
• Root → 木の始点となる節点
• Leaf → 子を持たない節点

Q30．有向グラフと無向グラフ

一方通行の道を表すのに向いているグラフを選んでください。

• A．有向グラフ
• B．無向グラフ

答え

A．有向グラフ

Edgeに向きがあるため、「AからBへは行けるがBからAへは行けない」を表せます。

Q31．木と一般のグラフの違い

木（Tree）の特徴として正しいものをすべて選んでください。

• A．階層構造を表せる
• B．Rootを持つ形で考えられる
• C．同じ場所をぐるぐる回る循環を基本的に持たない
• D．必ずすべてのNodeが3個の子を持つ

答え

A・B・C

Q32．どちらが木構造？

次のうち木構造として扱うのに向いているものをすべて選んでください。

• A．Behavior Tree
• B．フォルダの階層
• C．二分探索木
• D．循環する道路網全体

答え

A・B・C

循環する道路網は一般のグラフとして扱う方が自然です。

---

7．BFSとDFSを使い分けよう

幅優先探索（BFS）と深さ優先探索（DFS）は、グラフや木をたどる基本的な探索方法です。

Q33．BFSでQueueを使う理由は？

BFSでは、見つけた隣接Nodeを追加し、先に見つけたNodeから処理します。Queueが向いている理由を選んでください。

• A．FIFOなので、先に追加したNodeから取り出せる
• B．LIFOなので、直前に追加したNodeから取り出せる
• C．値の大小で自動的に並べ替える
• D．Root以外を保存できない

答え

A

BFSの「近い階層から順に広げる」動きとQueueのFIFOが対応しています。

Q34．DFSでStackを使う理由は？

DFSでは、見つけた経路をできるだけ深く進み、行き止まりになったら戻る動きをします。Stackが向いている理由を選んでください。

• A．最後に追加したNodeを最初に取り出せるため、直前に見つけた先へさらに深く進みやすい
• B．最初に追加したNodeを最初に取り出すため
• C．最短経路を自動計算してくれるため
• D．Nodeを保存しなくても探索できるため

答え

A

StackのLIFOによって、直前に見つけたNodeを続けて処理できます。

Q35．QueueとStackの取り出し順を実際に確認しよう

1 → 2 → 3 の順にデータを追加しました。最初に取り出される値と、その理由を対応させてください。

データ構造	最初に取り出される値	理由
Queue	＿＿	＿＿＿＿＿＿
Stack	＿＿	＿＿＿＿＿＿

理由の選択肢：FIFO（先入れ先出し）・LIFO（後入れ先出し）

答え

• Queue → 1 / FIFO
• Stack → 3 / LIFO

用語だけでなく、どの値が実際に出てくるかまで結び付けて覚えましょう。

Q36．BFSの探索順を求めよう

次の木を、各Nodeの子を左から右の順に見つけるものとします。

        0
     /  |  \
    1   2   3
   / \  |  / \
  4  5  6 7  8

BFSで0から探索した順番を書いてください。

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

答え

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

BFSは近い階層から順番に調べます。

Q37．DFSの探索順を求めよう

Q36と同じ木を、左の子から優先して深く進むDFSで探索します。順番を書いてください。

答え

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

Q38．BFSのQueueの動きを読もう

Q36の木で、0を取り出して子1・2・3をQueueへ入れた直後のQueueを選んでください。

• A．[1, 2, 3]
• B．[3, 2, 1]
• C．[0, 1, 2, 3]
• D．[]

答え

A．[1, 2, 3]

Q39．DFSをStackで左優先にするには？

0の子が左から 1, 2, 3 です。Stackを使ったDFSで1から先に取り出したいとき、子をStackへ積む順番として適切なものを選んでください。

• A．1 → 2 → 3
• B．3 → 2 → 1
• C．1だけ積む
• D．順番は絶対に関係ない

答え

B．3 → 2 → 1

Stackは最後に入れたものが最初に出るため、左の1を最初に取り出したいなら逆順に積みます。

Q40．BFSとDFSを使う場面を考えよう

次の目的に、BFSとDFSのどちらがより適しているか対応させてください。

目的	探索
Edgeのコストがすべて同じ迷路で、最も少ない手数のゴールを探したい	＿＿＿＿＿＿
1本の分岐を奥まで調べ、行き止まりなら戻りながら探索したい	＿＿＿＿＿＿

選択肢：BFS・DFS

答え

• 最少手数 → BFS
• 1本を深く探索 → DFS

データ構造の名前だけでなく、探索の広がり方と目的を結び付けましょう。