探索木 (G検定)

1. 定義と概要

探索木とは、問題を解くために取りうる状態をノード（節。探索木の中で「状態」や「分かれ道」を表す1つ1つの点）として、ある状態から別の状態へ移る操作を枝（エッジ。ノードとノードをつなぎ、ある状態から別の状態へ移ることを表す線）として、木構造（上下に枝分かれする図で情報のつながりを表す表現方法）に表現したものです。

探索の出発点となる初期状態は親を持たない最上位のノードでルート（根）と呼ばれ、それ以上枝分かれしない末端の状態はリーフ（葉）と呼ばれます。ルート（根）とは、木構造の一番上にある、探索の出発点となるノードのことです。

迷路の問題であれば、分岐点や行き止まりがノードに、通路が枝に対応し、スタートからゴールに至る道筋を木構造として整理できます。頭の中で分岐をたどるかわりに、状態のつながりを図として置き直したものが探索木にあたります。

従来、複雑な問題の解決は人手による試行錯誤に頼る面が大きなものでした。問題が取りうる状態全体を状態空間（問題として起こりうるすべての状態を集めたもの）として捉え、状態と状態の遷移（ある状態から別の状態へ移ること）を木構造に落とし込むことで、コンピュータが体系的かつ網羅的に解の候補をたどれるようになります。

探索木は、幅優先探索（ルートに近いノードから順にたどる進み方）や深さ優先探索（1本の枝を行き止まりまで進んでから戻る進み方）、ゲーム木探索といった探索アルゴリズムの前提となる基礎概念です。G検定のシラバスでは、探索と推論（すでにわかっている情報から新しい結論を論理的に導き出す処理）を扱う分野の冒頭に位置づけられます。

2. 試験対策ポイント

G検定の試験対策としては、まずノード・枝・ルート・リーフといった探索木の構成要素の呼び方を、具体的な問題設定に対応づけられるかがポイントになります。

あるノードを基準にすると、上下・横のつながりにもそれぞれ呼び方が用意されています。

呼び方	どのノードを指すか
親ノード	あるノードから見て、1つ上でつながっている元のノード
子ノード	あるノードから枝分かれした先のノード
兄弟ノード	同じ親を持つノード同士

この上下・横の関係にある呼び方は親ノード・子ノード・兄弟ノード（家系図のように、上下や横の関係にあるノード同士の呼び方）とまとめて表されます。迷路の分岐点や行き止まりのように、具体的な場面をノード・枝に置き換えて理解しておきたいところです。

試験で取り違えやすい点として、探索木はあくまで探索の対象となる構造であり、その木をどのような順序でたどるかという手順は幅優先探索や深さ優先探索といった別の探索アルゴリズムにあたるという整理があります。木そのものと、木をたどる手順は別の概念として区別されます。

対戦相手が存在するゲームでは、自分の手だけでなく相手の応手も含めてすべての可能な手を木に展開したものをゲーム木（自分の手だけでなく対戦相手の応手も含めて広げた探索木）と呼びます。探索木の考え方をゲームの意思決定に応用した位置づけとして整理されます。

また、問題の状態や選択肢の数が増えるほど、木のノード数は組み合わせに応じて指数関数的に膨れ上がります。この現象は組合せ爆発（選択肢が増えるほど調べる対象が爆発的に増えてしまう現象）と呼ばれ、すべての状態を網羅する探索が現実的な時間で終わらなくなる要因として扱われます。

3. 関連概念との比較・相違点

探索木と並べて語られる概念は、探索木との関係でそれぞれ位置づけが異なります。

概念	探索木との関係
幅優先探索・深さ優先探索	探索木をどの順序でたどるかという手順
ゲーム木	対戦相手の応手も交互に含めて広げた探索木
組合せ爆発	探索木を扱う際に直面する限界を表す現象

それぞれの違いを、順に確認していきます。

幅優先探索・深さ優先探索との最大の違いは、指し示す対象が構造か手順かという点にあります。探索木は探索の対象となる木構造そのものを指すのに対し、幅優先探索・深さ優先探索はその木をどの順序でノードをたどるかという手順（アルゴリズム）を指します。

同じ探索木に対しても、根に近いノードから順にたどるか、一本の枝を先の方までたどってから戻るかで異なる手順が使い分けられますが、それぞれの手順の中身は個別の探索アルゴリズムの解説に譲られる整理です。探索木という構造と、それをたどる手順は別の概念として区別されます。

ゲーム木との最大の違いは、木に展開する手が自分のものだけか、相手の応手も含むかという点にあります。一般の探索木は自分が取りうる手のみを展開するのに対し、ゲーム木は対戦相手の応手も交互に含めて木を広げます。将棋や囲碁のような対戦型のゲームでは、自分の一手ごとに相手の応手が枝分かれするため、木は双方の意思決定が交互に積み重なった形で広がっていきます。

組合せ爆発は、探索木そのものではなく探索木が抱える課題という位置づけで区別されます。状態や選択肢が増えるほどノード数が指数関数的に増加し、木を余すことなくたどる全探索が非現実的になる現象を指します。探索木という構造自体は問題を整理するための表現方法である一方、組合せ爆発はその構造を扱う際に直面する限界を表す概念として、探索木とは別の切り口で整理されます。

4. ビジネス・実務での活用シナリオ

ゲームAI（将棋・囲碁など）の分野では、着手の候補を探索木として展開し、その中から評価の高い手を選び出すことで、対戦戦略を体系的に導き出す仕組みに使われています。人間の勘や経験だけに頼らず、取りうる手の候補を漏れなく木として整理することで、局面ごとの評価を一貫した基準で比較できるようになります。

ルート探索・ナビゲーションの分野では、地図上の分岐点をノード、道路を枝とする木構造をたどることで、出発地から目的地までの経路の候補を漏れなく洗い出します。分岐点ごとの選択を木として整理しておくことで、遠回りの経路や行き止まりを含めて候補を体系的に比較できるようになります。

計画立案・スケジューリングの分野では、作業の進め方や工程の選択肢を状態として木構造に展開し、目的の状態に到達するまでの手順を体系的に探索します。工程の組み合わせが多い計画ほど思いつきの順で検討すると見落としが生まれやすく、状態を木として整理する考え方は工程管理の精度を支える土台になっています。

5. 要点まとめ

• 探索木は問題の状態をノード、状態間の移り方を枝として木構造に表したもので、出発点をルート（根）、末端をリーフ（葉）と呼びます。
• 探索木は探索の対象となる構造であり、幅優先探索・深さ優先探索はその木をたどる手順にあたります。木と手順は別の概念として整理されます。
• 対戦相手の応手も含めて木を広げたものがゲーム木であり、状態が増えるほどノード数が指数関数的に増える組合せ爆発が課題となります。

6. 確認問題