探索木とは
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推論へ応用する研究が広がった。
ワークフロー
初期状態をルートノードとして設定 → 取りうる行動・選択ごとに子ノードを生成し木を展開 → 評価関数で各ノードの有望さを判定 → 有望な経路を優先的に深掘り、見込みの薄い経路は打ち切る(枝刈り) → 目標状態や最適解に達したノードを解として出力。
コード例
幅優先探索(BFS)による探索木の走査
from collections import deque
def bfs(root, goal, get_children):
queue = deque([root])
visited = {root}
while queue:
node = queue.popleft()
if node == goal:
return node
for child in get_children(node):
if child not in visited:
visited.add(child)
queue.append(child)
return None利点
- 取りうる選択肢を体系的に管理でき、有望な経路の優先探索や見込みの薄い経路の打ち切りがしやすい
- 1本道の逐次的な探索と異なり、複数の分岐を比較検討したうえで最終的な解を選べる
- minimax法やA*等、目的に応じた探索アルゴリズムを組み合わせて適用できる
欠点
- 取りうる選択肢の数が多い問題では、木のノード数が指数的に増加し計算コストが膨大になる(組み合わせ爆発)
- 有望な経路を判定する評価関数の設計次第で探索の質が大きく左右される
- 深さや分岐数が大きい場合、メモリ使用量も探索の妨げになりうる
比較
関連用語
よくある質問
探索木とビームサーチの違いは？
探索木は木構造を用いた探索手法全般を指す総称であり、ビームサーチは各深さで有望な候補を一定数に絞り込みながら進める、探索木の探索範囲を効率化する具体的な手法の1つにあたる。