深さ優先探索で迷路を解くとは？意味・仕組み・活用例をわかりやすく解説

深さ優先探索で迷路を解くとは？意味・仕組み・活用例をわかりやすく解説

はじめに

迷路をコンピュータに解かせるとき、最初に考えるべきことは「次にどの道を選ぶか」です。分かれ道があるたびに全方向を同時に調べる方法もありますが、深さ優先探索ではまず一つの道を選び、行けるところまで進みます。

この方法は英語では Depth-First Search と呼ばれ、略して DFS とも書かれます。迷路で考えると、入口から通路をたどり、行き止まりなら戻り、まだ試していない分岐へ進むという動きを繰り返します。単純な手順で全体を探索できるため、アルゴリズム学習の初期によく登場します。

この記事では、深さ優先探索の基本、迷路での動き、具体的な手順、実装で使うデータ構造、長所と短所、幅優先探索との違いを順番に整理します。プログラムを書く前に考え方を押さえることで、再帰やスタックを使った実装も理解しやすくなります。

深さ優先探索とは

深さ優先探索とは、分岐を持つ構造の中で、一つの候補をできるだけ深く調べてから、別の候補へ移る探索手法です。迷路であれば、現在地から進める未訪問の道を一つ選び、その先でも同じように未訪問の道を選び続けます。

進める道がなくなった場合は、最後に選択肢が残っていた地点まで戻ります。この「戻って別の選択肢を試す」動きは、バックトラックと呼ばれます。深さ優先探索は、このバックトラックを使って、分岐を一つずつ調べていく方法だと考えると理解しやすいでしょう。

深さ優先探索が使える対象は迷路だけではありません。たとえば、フォルダの中にあるファイルを階層の奥まで調べる処理、家系図や組織図の探索、ゲームで次の手を試す処理、グラフ構造の連結関係の確認にも応用できます。共通しているのは、問題を「地点」と「つながり」に分けて考えられる点です。

迷路での考え方

迷路を深さ優先探索で解く場合、迷路は「壁」と「通れる道」に分けて扱います。さらに、探索中は「現在地」「すでに通った場所」「まだ通っていない場所」「ゴール」を区別します。これにより、同じ場所を何度も行き来して探索が終わらなくなる状態を防げます。

たとえば、現在地から上、右、下、左の順に調べると決めておきます。上に未訪問の通路があれば上へ進み、そこからまた同じ順序で次の通路を探します。進める方向がなければ一つ前の地点へ戻り、まだ試していない方向がないかを確認します。

この探索順は、見つかる経路に影響します。上から先に調べる場合と右から先に調べる場合では、同じ迷路でも最初に見つかる出口までの道が変わることがあります。つまり、深さ優先探索は出口を見つける方法としては有効ですが、常に最短距離の道を返す方法ではありません。

具体的な探索手順

深さ優先探索で迷路を調べる流れは、次のように整理できます。まず入口を現在地にして、そこを訪問済みとして記録します。次に、現在地から移動できる隣のマスを調べ、まだ訪問していない通路があればそのマスへ進みます。

新しいマスに進んだら、そのマスも訪問済みにします。そして、そこからさらに未訪問の通路を探します。この動きを繰り返すことで、探索は迷路の奥へ奥へと進んでいきます。ゴールに着いた時点で探索を止めれば、入口からゴールまでの一つの経路が得られます。

もし現在地から進める未訪問の通路がなければ、直前にいた場所へ戻ります。戻った地点で、まだ試していない方向があればそこへ進みます。すべての候補を試してもゴールが見つからない場合は、その迷路には入口から到達できる出口がないと判断できます。

実装で使うデータ構造

迷路をプログラムで扱う場合、多くは二次元配列で表現します。たとえば、壁を 1、通路を 0、スタートやゴールを別の値で表すと、各マスの状態を機械的に判定できます。現在地は行と列の組み合わせで管理でき、上下左右への移動も座標の増減として書けます。

深さ優先探索の実装には、再帰関数またはスタックがよく使われます。再帰関数で書く場合は、ある地点から次の地点へ進む処理の中で、同じ探索関数をもう一度呼び出します。行き止まりになって関数が戻ると、自然に一つ前の分岐へ戻ったことになります。

スタックを使う場合は、これから調べる地点を積み上げて管理します。最後に追加した地点を先に取り出すため、探索は深い方向へ進みやすくなります。再帰も内部的には呼び出し履歴を積み上げているため、考え方としてはスタックに近いものです。

初心者がつまずきやすい点は、訪問済みの記録です。訪問済みを記録するタイミングが遅いと、同じマスを何度も候補に入れてしまうことがあります。通常は、通れるマスに進むと決めた時点、または実際に入った時点で訪問済みにして、再訪問を避けます。

長所と短所

深さ優先探索の大きな長所は、手順が単純で実装しやすいことです。現在の道筋を中心に探索するため、迷路全体のすべての候補を大量に保持しなくても処理を進められます。メモリを抑えたい場面や、解が存在するかどうかを確認したい場面で扱いやすい手法です。

一方で、深さ優先探索には短所もあります。代表的なのは、最短経路を保証しないことです。ゴールがスタートの近くにあっても、最初に選んだ道が長い遠回りであれば、探索はそちらを深く進んでしまいます。その結果、先に見つかった経路が最短ではないことがあります。

もう一つの注意点は、ループへの対策です。迷路やグラフには、進んだ先から以前の地点へ戻れる構造が含まれることがあります。訪問済みを記録しないまま探索すると、同じ地点を何度も通り、処理が終わらなくなる可能性があります。そのため、実装では「どこを調べたか」を必ず管理します。

幅優先探索との違い

迷路探索では、深さ優先探索とよく比較される手法に幅優先探索があります。幅優先探索は、スタート地点から近い場所を順番に広げるように調べる方法です。距離が同じ範囲を一層ずつ調べるため、各移動のコストが同じ迷路では、最初に見つかったゴールまでの経路が最短になります。

深さ優先探索は、近い場所を均等に調べるのではなく、一つの道を深く進みます。そのため、探索の途中で長い遠回りに入り込むことがあります。ただし、再帰やスタックで書きやすく、問題の構造を奥までたどる処理には向いています。

使い分けの目安は目的です。とにかく出口があるかを確認したい、構造を一通りたどりたい、メモリを抑えたい場合は深さ優先探索が候補になります。最短経路が必要で、各移動の重みが同じであれば、幅優先探索を検討するとよいでしょう。

プログラムで試すときの注意点

Pythonなどで深さ優先探索を書くときは、まず迷路の表現を決めます。二次元配列、スタート位置、ゴール位置、壁の値、通路の値をそろえておくと、探索処理が読みやすくなります。方向の順序も固定しておくと、結果を再現しやすくなります。

再帰で実装する場合は、迷路が非常に大きいと再帰呼び出しが深くなりすぎることがあります。学習用の小さな迷路では扱いやすい一方、大規模なデータではスタックを明示的に使う実装のほうが管理しやすい場合があります。

また、探索結果として何を返すかも先に決めておくとよいでしょう。ゴールに到達できるかだけを知りたいのか、実際の経路を出力したいのか、訪問した順番を可視化したいのかによって、保存すべき情報が変わります。経路を復元したい場合は、各マスに「どこから来たか」を記録する方法が有効です。

まとめ

深さ優先探索は、分岐のある問題で一つの道をできるだけ深く進み、行き止まりなら戻って別の道を試す探索手法です。迷路では、入口から未訪問の通路を進み、行き止まりでバックトラックしながら出口を探します。

この方法は、考え方が直感的で、再帰関数やスタックを使って実装しやすいことが特徴です。一方で、最短経路を保証しないこと、訪問済み管理をしないとループすることには注意が必要です。迷路探索を通じて深さ優先探索を理解すると、木構造、グラフ、ファイル階層、ゲーム探索など、さまざまな問題への応用も見えやすくなります。

更新履歴