探索木とは
Search Tree / Tree Search
各ノードが状態、各エッジが行動・選択を表す木構造を辿ることで、目標状態や最適解を探し出す探索手法
ひとことで言うと
選択肢を枝分かれさせながらたどり、目的の答えを探し出すための木のような構造。
概要
探索木とは、ある初期状態から出発し、取りうる行動・選択のたびに枝分かれしていく木構造を構築・辿ることで、目標状態や最適な解に至る経路を探し出す探索手法の総称。 ルートノードが初期状態を、各エッジが可能な行動や選択を、子ノードがその結果得られる状態を表す。 チェスや将棋のようなゲームAIにおけるゲーム木探索(minimax法・モンテカルロ木探索)、経路探索のA*アルゴリズムなど、古典的な人工知能分野で幅広く使われてきた。 近年ではLLMの推論においても、1つの回答系列だけでなく複数の思考の分岐を木構造として探索し評価する「Tree of Thoughts」のような手法に応用されている。
背景
取りうる選択肢が多岐にわたる問題では、思いつく手を1つずつ順に試すだけでは、より良い解を見逃したり行き詰まった際に引き返せなかったりする課題があった。 探索木は、可能な選択肢を体系的に枝分かれさせて管理し、有望な経路を優先的に深掘りしたり見込みの薄い経路を打ち切ったりする手法として使われてきた。
歴史
1950年代: チェス等のゲームAIにおいて、相手の最善手を仮定して自分の最善手を選ぶminimax法が探索木の代表的な応用として研究される。 1968年: HartらがA*アルゴリズムを発表し、目標までの推定コストを使って探索範囲を絞り込む枝刈り手法を確立。 2023年: YaoらがLLMに複数の思考過程を木構造として展開・評価させる「Tree of Thoughts」を提案し、探索木の考え方をLLM推論へ応用する研究が広がった。
利点
- 取りうる選択肢を体系的に管理でき、有望な経路の優先探索や見込みの薄い経路の打ち切りがしやすい
- 1本道の逐次的な探索と異なり、複数の分岐を比較検討したうえで最終的な解を選べる
欠点
- 取りうる選択肢の数が多い問題では、木のノード数が指数的に増加し計算コストが膨大になる(組み合わせ爆発)
- 有望な経路を判定する評価関数の設計次第で探索の質が大きく左右される