【G検定】探索木とは？場合分けを木構造で表す考え方と探索の基本を解説

迷路を解くとき、分かれ道に来るたびに「右へ行く場合」「左へ行く場合」と枝分かれを書き出していくと、可能性の全体が1本の「木」の形に整理できます。この木こそが探索木で、コンピュータによる問題解決の最も基本的な道具です。この記事では探索木の考え方をやさしく解説します。

📖 ひと言でいうと

探索木とは、問題の「場合分け」を枝分かれする木の形に表し、その枝をたどって答えを探すためのデータ構造です。たとえるならトーナメント表を逆さにしたような図で、出発点（根）から選択肢ごとに枝が分かれ、枝の先でさらに次の選択肢に分かれていきます。「場合分けを続けていけば、いつかは目的の状態にたどり着く」という発想を、コンピュータが扱える形にしたものです。

🖼 1枚でわかる探索木

📘 対策テキストの説明

計算機科学において特定のキーを特定するために使用される木構造のことで、学習結果を木構造で表現できるため解釈性が高い。場合分けを続けていけばいつか目的の条件に合致するという考え方に基づく。不純度が最も減少(情報利得が最も増加)するようにデータを振り分けることを繰り返す。不純度とはクラスの混ざり具合を表す指標でジニ係数やエントロピーがある。バギングを組み合わせた手法をランダムフォレストという。

この定義文は、実は2つの文脈をまとめて述べています。前半の「木構造」「場合分けを続けていけばいつか目的の条件に合致する」が、この章（探索・推論）で学ぶ探索木そのものの説明です。後半の「不純度」「ジニ係数」「ランダムフォレスト」は、同じ木構造を使う機械学習の手法である決定木に関する内容で、機械学習の章で改めて登場します。ここではまず「場合分けを木で表し、たどって答えを探す」という前半の考え方をしっかり押さえましょう。

🔍 しっかり理解する

根・ノード・枝——木の各部の意味

探索木は、次の部品でできています。出発点となる最初の状態を根（ルート）、場合分けで生じるそれぞれの状態をノード（節点）、状態から状態への移り変わり（選択や操作）を枝と呼びます。迷路なら「スタート地点」が根、「各分かれ道での位置」がノード、「右へ進む／左へ進む」が枝にあたります。

ゴールにあたるノードが見つかるまで枝を伸ばし、たどっていくことが「探索」です。つまり探索木は、問題解決を「木のどこかにある目的のノードを見つける作業」に置き換える道具だといえます。

たどり方は2通り——幅優先と深さ優先

同じ探索木でも、どの順番でノードを調べるかで性質が大きく変わります。代表が幅優先探索と深さ優先探索です。

どちらも「探索木のノードを漏れなく調べる」点は同じで、調べる順番だけが違います。詳しくはそれぞれのキーワード解説で扱いますが、「探索木という土俵の上で動く2つの方式」という関係を押さえておくと全体像が見えます。

探索木の限界——組合せ爆発

探索木の弱点は、分岐の数が増えると木が爆発的に大きくなることです。1手ごとに10通りの選択肢がある問題では、3手先で1,000通り、6手先で100万通りのノードが生まれます。オセロや将棋・囲碁のようなゲームでは、すべての場合を書き出した木は天文学的な大きさになり、しらみつぶし（ブルートフォース）では手に負えません。

この限界こそが、探索・推論の章の後半で学ぶ各手法の出発点です。相手と交互に手を打つゲームの局面展開を表した探索木（ゲーム木）に対しては、Mini-Max法で手の価値を評価し、αβ法で「調べても結論が変わらない枝」を刈り取ることで探索量を減らします。さらに囲碁のように木が大きすぎる問題では、モンテカルロ法のようにランダムシミュレーションで枝の良し悪しを見積もる別路線も発展しました。いずれも「探索木が大きすぎて全部は調べられない」という共通の課題への答えなのです。

💡 具体例で考える

「8パズル」（3×3の枠に1〜8の数字タイルを並べ、空きマスを使って正しい並びに戻すパズル）を探索木で考えてみましょう。最初の盤面が根です。空きマスの位置によって、タイルを動かせる方向は2〜4通りあり、それぞれの動かし方が枝になります。動かした後の盤面が新しいノードで、そこからまた枝が伸びます。

こうしてできる木の中から「完成した盤面」というノードを見つけ、根からそこまでの枝のたどり方を読み上げれば、それがそのままパズルの解答手順になります。「解を求めること」と「木の中で目的のノードへの経路を見つけること」が同じだとわかる、探索木らしい例です。

⚠️ よくある誤解・紛らわしい用語

📝 試験でのポイント

📚 まとめ