探索木とは？迷路で学ぶ仕組みと幅優先・深さ優先探索

探索木とは？迷路で学ぶ仕組みと幅優先・深さ優先探索

探索木とは？迷路で考える基本構造

探索木は、問題を解く途中で生じる選択肢と、その結果を木の形に整理したものです。迷路なら、入口が「根」、現在地などの状態が「ノード」、進める方向が「枝」に相当します。行き止まりやゴールのように、それ以上展開しないノードは「葉」と呼ばれます。

探索木は迷路そのものの絵ではなく、コンピュータがどの候補を、どの順番で調べられるかを表す作業用の構造です。すでに試した道と、これから試す道を分けて管理できるため、人が分かれ道をメモしながら進む試行錯誤を機械で再現できます。

探索木の作り方

探索木を作るときは、最初に「状態」「選択肢」「終了条件」を決めます。迷路なら状態は現在地、選択肢は上下左右のうち壁でない方向、終了条件はゴール到達または行き止まりです。

1. 入口の状態を根ノードにする。
2. 現在地から進める道を列挙し、それぞれを子ノードとして追加する。
3. 子ノードがゴールか行き止まりかを判定する。
4. 未探索の子ノードについて同じ展開を繰り返す。

たとえば最初の分かれ道で「左は行き止まり、右はもう一つの分かれ道」なら、根から左右へ2本の枝を伸ばします。左の枝は葉で終了し、右のノードだけをさらに展開します。この繰り返しで、候補経路が木として見えるようになります。

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

探索木を作っても、すべての枝を同時には調べられません。そこで必要になるのが、次にどのノードを調べるかを決める探索アルゴリズムです。代表例が幅優先探索（BFS）と深さ優先探索（DFS）です。

迷路で「移動回数が最も少ない経路」を探し、どの一歩も同じコストならBFSが適しています。一方、とにかく解が一つ見つかればよく、メモリを抑えたい場合はDFSが候補になります。距離や時間など枝ごとのコストが違う場合は、単純なBFSではなくダイクストラ法やA*探索なども検討します。

探索木とグラフの違い

迷路や道路網の元の構造は、一般に「グラフ」で表されます。グラフでは同じ場所へ別経路から到達でき、A地点からB地点、B地点からA地点へ戻る循環もあります。対して探索木は、ある開始点から選択を展開した探索過程を表します。

同じ場所を別経路から何度も子ノードにすると、木が不要に膨らみ、循環する迷路では探索が終わらない恐れがあります。そのため実装では「訪問済み集合」を用意し、すでに調べた状態を再び展開しないのが基本です。ただし、ゲームのように同じ盤面でも手番や所持品が違えば別状態になるため、何を同一状態とみなすかを先に決める必要があります。

探索木の活用例

探索木は、複数の選択肢から条件を満たす手順や、より良い組合せを探す問題に使えます。

ゲームAIでは、すべての手を最後まで展開すると候補が膨大になるため、一定の深さで局面を評価したり、明らかに不利な枝を調べない「枝刈り」を使ったりします。カーナビの経路探索でも、目的地に近そうな方向を優先するヒューリスティックを使うことで探索量を減らせます。

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

各ノードから平均して多くの枝が伸び、探索の深さも増えると、候補数は急激に増えます。これを組合せ爆発と呼びます。探索木を使えば自動的に高速になるわけではなく、問題の性質に合う探索順序と削減方法が必要です。

• ループがある問題では訪問済み状態を管理する。
• 「最短」が手数、距離、時間、費用のどれを指すか決める。
• BFSの最短性は、各枝のコストが同じなどの条件付きである。
• 候補が多い場合は枝刈り、深さ制限、双方向探索、ヒューリスティックを検討する。
• 完全な探索木を先に作らず、必要なノードだけ順次生成する。

まとめ

探索木とは、初期状態を根、選択肢を枝、到達した状態をノードとして、解の候補を整理する構造です。迷路では分かれ道を展開し、行き止まりなら戻り、未探索の道を順番に調べます。最短手数が必要なら条件を確認してBFS、深い候補を少ないメモリで調べたいならDFSというように、目的に応じて探索方法を選びましょう。循環と候補数の増加を管理することが、探索木を実際の問題に生かす鍵です。

更新履歴