迷路を深さ優先探索で解く

迷路を幅優先探索で解く」で示した迷路を解く問題を深さ優先探索を使い再帰的なコードで解を求めています。

幅優先探索については、 Wikipedia 「幅優先探索」を参照してください。

深さ優先探索では、最初に見つかった解が最短距離のルートという保証はありません。
解が一つしかないような迷路では、問題ありませんが、解が多数ある場合には、最短経路を得るのに 枝刈りをして最短経路となる見込みのない探索は途中で終了するようなコードを書く必要があります。
ここでは、そこまでしていません。 最初に見つかった経路を解としています。

なお、深さ優先探索は、場合によっては探索木が深すぎてなかなか解が見つからないということが 起こりえます。 試しに、以下のような迷路を解いてみたら、僕のPCでは、32秒もかかってしまいました。


幅優先探索だと9ミリ秒で解を求めているので、その差は歴然です。
かといって、幅優先が常に有利かというとそうとも言い切れないのところが この手のアルゴリズムの難しいところですね。

ちなみに、以下のような迷路では、9ミリ秒という短い時間で解を求めています。

幅優先は一般に迷路の分岐数が多いとメモリが大量に必要になり、それにつれて計算量も 増えてしまいます。

 「迷路を幅優先探索で解く」同様、C#でコンソールアプリケーションとして作成しています。 作成したクラスは、MazeSolverとMaze そして Position構造体です。これは「迷路を幅優先探索で解く」と同じですが、そのMazeクラスも含めその実装は異なっています。

Mazeは迷路を表すクラスで、ある地点の四方の位置を列挙したり、ゴールまでたどり着いたかなどのメソッドを持ちます。 Positionは迷路の位置をX,Y座標で示します。 MazeSolverは、迷路を探索するクラスです。

 以下、C#のコードです。

 

 

テストで使用した迷路データを2つほど示します。これをテキストファイルとして、このプログラムに読み込ませれば、解を表示してくれます。

■テストデータ1
******************************
S *     *     *              *
* * * *** ***** ************ *
* * * * *  * ** *        * * *
* * * * *  * ** * *** *  * * *
*   *           * *   *      *
***************** ***** ******
*                     *    * G
*** ********* ************** *
*    * * *       *           *
* **** * * ***** *** **** ****
*      * * *   * *   *     * *
***  * * * ***** *** ******* *
*    *   *       *         * *
* ***************** **** * * *
*     *      *      *  * * * *
* ***** **** * **** **** * * *
*       *      *         *   *
******************************

■テストデータ2
*S*****************************
*   *                   *     *
*** ******* ***** * *** *** * *
*         * *   * *   *     * *
***** *** * *** * *** *** *****
*   * *   *     *       *     *
*** * *** * * *** * * ******* *
*     *   * *   * * *   *     *
*** ***** *** * * * *** * *****
*     *         * * *   *   * *
* *********** ********* ***** *
* * *   *   * *   *     *     *
* *** * * *** * *** ***** *** *
*     *     *   *     *     * *
* ********* ********* * ***** *
* *   *     *         * *     *
* * ******* *** ******* *** ***
* * * *   * *   * *     * *   *
*** * * *** * *** * * *** * * *
*           *       *     * * *
*****************************G*