① 人工知能の基礎と動向 ／ 3. 探索・推論
探索木とは
探索木とは、問題の状態遷移をノード（節点）と枝で表現した木構造です。探索アルゴリズムの違いは、この木をどの順序でたどるかの違いとして整理できます。
この用語はG検定シラバスの「3. 探索・推論」に含まれます。 章全体の用語は用語解説①（全54語）にまとまっています。
一言でいうと
「今の状態」と「次に取りうる状態」を枝でつないだ木の形の図です。
ノードと枝が表すもの
- ノード：ある時点の状態（盤面、迷路の位置など）
- 枝：1回の行動による状態の遷移
- 根（ルート）：初期状態
行動を1つ選ぶたびに枝分かれするため、深くなるほどノード数は急激に増えます。この増加が探索の難しさの正体です。
たどる順序で手法が決まる
同じ探索木でも、たどる順序を変えると別のアルゴリズムになります。
すべてのノードを調べ尽くす方法がブルートフォースです。
探索の2つの立場
探索手法は、手がかりを使うかどうかで大きく2つに分かれます。
探索空間が大きい問題では、後者のように当たりをつける工夫が欠かせません。
🎯 G検定での押さえどころ
- ノード＝状態、枝＝状態の遷移
- 探索アルゴリズムの違いは「たどる順序」の違い
- 深くなるほどノード数が指数的に増える
⚠️ よくある誤りの選択肢
- 「探索木のノードは行動を、枝は状態を表す」→ 誤り。ノードが状態、枝が遷移です
- 「探索木は深くなってもノード数はあまり増えない」→ 誤り。指数的に増えます
関連する用語
ご利用にあたって 本ページの内容は、JDLAが公開しているG検定シラバス2024や公式テキストなど、一般に公開されている情報をもとに独自に整理・解説したものです。実際の試験の出題内容を示すものではなく、また合格を保証するものでもありません。制度・法令・試験要項は変更されることがあるため、最新の情報は必ずJDLA公式サイトでご確認ください。