探索木（Search Tree）

Search Tree / State Space Search

探索・推論 重要度：高

概要

探索木（Search Tree）とは、AIが問題を解く際に、解の候補を木構造（ツリー構造）で表現し、その中から最適な解を見つけるために用いるデータ構造です。初期状態をルートノード（根）として、そこから取りうる操作を枝として展開し、目的の状態（ゴール）に到達する経路を探す手法が「探索」です。

探索木は、AIの最も基本的な問題解決手法であり、第1次AIブーム（1950年代～1960年代）から研究されてきました。迷路の解探索、パズルの解法、ゲームの最善手の探索など、幅広い問題に適用できます。探索の方法によって、幅優先探索（BFS）と深さ優先探索（DFS）に大別され、それぞれに計算量やメモリ使用量の特性が異なります。

詳細解説

探索木の基本構造

探索木は、以下の要素で構成されます。

  • ノード（節点）：問題の各状態を表す。ルートノードが初期状態、リーフノードが末端状態を表す。
  • エッジ（枝）：状態間の遷移（操作・アクション）を表す。
  • ルートノード：探索の出発点となる初期状態。
  • ゴールノード：問題の解となる目標状態。

問題を探索木として表現することで、解の探索を体系的に行うことが可能になります。これを「状態空間探索」と呼びます。

幅優先探索（BFS：Breadth-First Search）

幅優先探索は、ルートノードに近い階層から順に、同じ深さのノードをすべて探索してから次の階層に進む手法です。

  • 特徴：最短経路を保証する（コストが均一な場合）
  • メモリ：探索するノードをすべてキューに保存するため、メモリ使用量が大きい
  • 計算量：分岐数をb、深さをdとすると、時間計算量・空間計算量ともにO(b^d)

深さ優先探索（DFS：Depth-First Search）

深さ優先探索は、一つの枝をできるだけ深くまで探索し、行き止まりに達したらバックトラック（後戻り）して別の枝を探索する手法です。

  • 特徴：メモリ効率が良い（現在の経路のみ保存）
  • メモリ：スタック構造を利用し、空間計算量はO(b*d)
  • 注意点：最短経路を保証しない。無限ループに陥る可能性がある

幅優先探索と深さ優先探索の比較

特性幅優先探索（BFS）深さ優先探索（DFS）
探索順序浅い階層から順に探索深い方向へ優先的に探索
最短経路の保証保証される保証されない
メモリ使用量大きい（O(b^d)）小さい（O(b*d)）
データ構造キュー（FIFO）スタック（LIFO）
完全性有限グラフで完全無限グラフで不完全な場合がある

その他の探索手法

基本的な幅優先・深さ優先探索に加え、以下のような発展的手法があります。

  • 反復深化探索（IDDFS）：深さ制限を徐々に増やしながら深さ優先探索を繰り返す。BFSの完全性とDFSのメモリ効率を両立する。
  • ヒューリスティック探索：経験的知識（ヒューリスティック関数）を用いて有望なノードを優先的に探索する。A*アルゴリズムが代表的。
  • 最良優先探索：評価関数に基づいて最も有望なノードを選択する。

歴史・背景

探索アルゴリズムの研究は、AIの黎明期から始まりました。1956年のダートマス会議で人工知能という概念が確立された直後から、問題解決のための探索手法が研究されています。

1960年代には、アレン・ニューウェルとハーバート・サイモンによる「General Problem Solver（GPS）」が開発され、状態空間探索の概念が体系化されました。GPSは、初期状態から目標状態への変換を探索木として表現し、手段目標分析（Means-Ends Analysis）によって問題を解くシステムでした。

その後、1968年にはピーター・ハートらによってA*アルゴリズムが提案され、ヒューリスティック探索の理論的基盤が確立されました。探索木の概念は、現代のAIにおいても、ゲームAI、経路探索、計画立案など多くの分野で活用されています。

具体的な事例

迷路問題への適用

迷路の各交差点をノード、通路をエッジとして探索木を構築します。スタート地点をルートノード、ゴール地点をゴールノードとして、幅優先探索を行えば最短経路が見つかります。深さ優先探索を行えば、メモリを節約しながら解を探すことができますが、最短であるとは限りません。

8パズル問題

3x3のマスに1～8の数字タイルと1つの空きマスを配置し、タイルをスライドさせて目標配置に並び替えるパズルです。各状態をノード、タイルの移動をエッジとする探索木を構築し、ゴール状態に至る操作列を探索します。

カーナビゲーションの経路探索

カーナビゲーションの経路探索も探索木の応用です。交差点をノード、道路をエッジとして、出発地から目的地までの最適経路を探索します。実際にはA*アルゴリズムやダイクストラ法などの効率的な探索手法が用いられます。

G検定での出題ポイント

試験対策のポイント 探索木はG検定で頻出のテーマです。以下のポイントを確実に押さえましょう。
  • 幅優先探索と深さ優先探索の違い（探索順序、メモリ使用量、最短経路の保証）を正確に理解する
  • 探索木の基本用語（ノード、エッジ、ルート、リーフ、深さ、分岐数）を押さえる
  • 計算量の表記（O記法）と、探索手法ごとの計算量の違いを理解する
  • ヒューリスティック探索とA*アルゴリズムの概要を理解する
  • 状態空間探索の概念と、問題を探索木として表現する方法を理解する