探索木とは？仕組みと深さ優先・幅優先の違いを迷路で解説

探索木とは？仕組みと深さ優先・幅優先の違いを迷路で解説

探索木とは、ある状態から選べる行動と、その結果生じる状態を木のような枝分かれで表したものです。迷路なら入口を出発点にして、右へ進む、左へ進むといった候補を順に広げます。複雑な選択肢を整理できるため、AIやアルゴリズムの基本として幅広く利用されています。

ただし、探索木を作るだけで自動的に最短経路が得られるわけではありません。どの候補から調べるかを決める「探索アルゴリズム」と、同じ状態を繰り返さないための管理が必要です。この記事では迷路を例に、探索木の構造、深さ優先探索（DFS）と幅優先探索（BFS）の違い、使い分け、実務上の注意点まで説明します。

探索木とは？選択肢を枝分かれで整理する仕組み

探索木は、探索の開始状態を根として、行動によって到達できる状態を子ノードとして広げた構造です。植物の木を上下逆にしたように、根から下へ枝が伸びる図で表すのが一般的です。

「木構造」はデータ同士の親子関係を表す一般的なデータ構造です。一方の「探索木」は、問題を解く途中で現れる候補を木として展開したものを指します。同じ木の形でも、目的が異なります。

また、実際の迷路は一つの場所へ別経路から到達したり、通路が輪になったりするため、本来は「グラフ」です。探索の過程を木として記録すると探索木になります。同じ地点を別ノードとして何度も展開しないよう、訪問済みの状態を管理することが重要です。

探索木で迷路を解く手順

迷路探索では、現在地だけでなく「次に調べる候補」「すでに訪れた場所」「どこから来たか」を記録します。基本的な流れは次のとおりです。

1. 入口を最初のノードとして候補に入れる。
2. 候補から一つ取り出し、その場所が出口かどうかを確認する。
3. 出口でなければ、壁ではない隣接マスを調べる。
4. 未訪問の隣接マスを子ノードとして候補に追加し、親ノードとして現在地を記録する。
5. 候補がなくなるか出口が見つかるまで繰り返す。
6. 出口から親ノードを逆にたどり、入口から出口までの経路を復元する。

訪問済みの記録は、輪になった通路をぐるぐる回るのを防ぎます。親ノードの記録は、探索が終わった後に正解の道筋を取り出すために使います。この二つは役割が異なるので、分けて考えると理解しやすくなります。

行き止まりに着いたときの次の動きは、採用する探索方法で変わります。直前の分岐へ戻って別の道を試すのが深さ優先探索、入口に近い未探索地点から順番に調べるのが幅優先探索です。

深さ優先探索と幅優先探索の違い

探索木の代表的なたどり方が、深さ優先探索（Depth-First Search：DFS）と幅優先探索（Breadth-First Search：BFS）です。どちらも到達可能な範囲を調べられますが、候補を取り出す順番と必要なメモリが異なります。

深さ優先探索は、一つの枝を進めるところまで深く進み、行き止まりなら分岐点へ戻る方法です。後から追加した候補を先に取り出すスタック（LIFO）や再帰処理で実装できます。深い位置に解がありそうな場合や、すべての候補を同時に保持したくない場合に向きます。ただし、最初に見つけた経路が最短とは限らず、非常に深い探索では時間や再帰の深さが問題になります。

幅優先探索は、根に近いノードから深さごとに調べる方法です。先に追加した候補を先に取り出すキュー（FIFO）を使います。各移動のコストが同じ迷路なら、初めて出口に到達した経路は手数が最小です。一方、各層の候補を多く保持するため、分岐が多い問題ではメモリ消費が大きくなります。

どの探索方法を選ぶ？

選び方の基準は、必要な答えと問題の性質です。単に出口へ到達できればよく、解が深い場所にありそうならDFSが候補になります。移動回数が最小の道を求め、すべての移動コストが同じならBFSが分かりやすい選択です。

ただし、道路の距離や所要時間のように枝ごとのコストが異なる場合、BFSでは最小コストを保証できません。その場合はダイクストラ法を使います。さらに、ゴールまでの推定距離を利用して有望な候補を優先したい場合はA*探索が適しています。

探索木の応用例

探索木は迷路だけでなく、現在の状態から複数の選択肢を試し、目標状態へ至る手順を探す問題に利用できます。

将棋のように分岐数が多い問題では、すべての手順を最後まで展開するのは現実的ではありません。そこで、勝ち目の薄い枝を早めに打ち切る枝刈りや、有望さを見積もる評価関数・ヒューリスティックを使います。探索木は選択肢を整理する土台であり、効率は探索順や枝刈りの工夫に大きく左右されます。

探索木を使うときの注意点

最大の課題は、分岐数と深さに応じてノード数が急増する「状態空間爆発」です。1ノードから平均3通りに分かれるだけでも、深さ10では候補が非常に多くなります。探索範囲の上限、枝刈り、良い探索順を設ける必要があります。

• 重複状態：別の経路から同じ状態に着く場合は、訪問済み集合で再展開を防ぎます。
• 循環と無限探索：迷路の輪や終わりのない状態空間には、深さ制限や反復深化などの対策が必要です。
• 最適性の条件：BFSの最短保証は移動コストがすべて同じ場合です。コストが異なるなら別の方法を選びます。
• メモリとの兼ね合い：BFSは浅い最短解に強い一方、幅が広い木では大量の候補を保持します。
• 探索木と元の問題の区別：元の状態空間がグラフなら、探索木の異なるノードが同じ状態を表すことがあります。

まとめ

探索木は、初期状態から選べる行動と到達状態を枝分かれで整理し、答えまでの手順を探すための表現です。迷路では入口が根、地点がノード、通路が枝、出口や行き止まりが葉に対応します。

DFSは一つの枝を深く進むためメモリを抑えやすく、BFSは根に近い層から調べるため、同一コストなら最小手数の経路を見つけられます。重み付きの経路ではダイクストラ法やA*探索も検討します。探索木を活用する鍵は、目的に合う探索順を選び、重複状態と候補数の増加を管理することです。

更新履歴