×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

迷路を幅優先探索で解く

迷路を解くプログラムです。
ここでは、幅優先探索を用いて解いてみました。
幅優先探索の特徴は、深さ優先探索とは異なり、最初に見つかった経路が最短経路となるという点です。

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

C#でコンソールアプリケーションとして作成しています。
このプログラムでは、テキストファイルで作成した迷路データを読み込むようにしていますので、 データを作成すれば、様々なパターンでの確認ができるようになっています。

* は壁を
S はスタート地点を
G はゴール地点を
空白は道を示しています。

そして得られた結果では、・が経路を示しています。

以下、その実行結果です。

 

作成したクラスは、 MazeSolverとMaze、そして、Position構造体です。

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

迷路データは、テキストファイルとして作成し、それを読み込むようにしています。
今回テストで用いた迷路データの場合は、どれも、1秒未満で解を見つけています。
自動で迷路を作成するプログラムも併せて作成すればよいのでしょうが、今回はそこまではやっていません。

以下 C#のコードを示します。

 

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

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