深さ優先探索

「迷路を幅優先探索で解く」で示した迷路を解く問題を、今度は深さ優先探索を使い再帰的なコードで解を求めてみました。
なお、深さ優先探索では、幅優先探索とは異なり、見つかった解が最短距離のルートという保証はありません。

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

今回作成したプログラムでの制約条件

「迷路を幅優先探索で解く」は神の視点で迷路を説いていましたが、こちらは、できるだけ人間が実際に迷路の中を（優先探索を使って）歩いて解くようなアルゴリズムにしてみました。まあ、実際に人間がこの方法で迷路を解くとなると、一歩の距離が正確にわかる必要がありますし、紙と鉛筆が必須だと思いますが…

具体的には、迷路を探索するクラスは、迷路の全体像を事前に把握できないという制約条件を付けています。探索するオブジェクトは、自分のいる前後左右が道なのか壁なのかしか把握できないということです。

さらに、スタート地点が迷路のどこに位置するのかも把握できないものとしています。つまり、迷路を２次元配列で表したときに、その２次元配列のどこからスタートするのかも分からないということです。

そのため、自分のいる位置は、スタート位置からの相対的な位置で把握することとしました。

当たり前ですが、ゴールにたどり着いたのかの判断はできるものとします。

ちなみに、ここで採用したアルゴリズムが実際のロボットに応用できるかどうかの判断は、僕には経験がないのでなんとも言えません。

実行結果

コードを示す前に、実行した結果を載せます。コンソールに表示される記号の意味は以下の通りです。

記号	意味
*	壁
S	スタート地点
G	ゴール地点
空白	通路
・	経路

以下のスクリーンショットは、探索途中の状態です。.NET Coreで作成し、Macで動かしています。

カーソルが動いて試行錯誤しているのをお見せできればいいのですが...

そして、これは探索が終了した時の状態。

幅優先探索か深さ優先探索か

なお、深さ優先探索は、場合によってはまったく見込みのない探索木を探す羽目になりなかなか解が見つからないということが起こりえます。

かといって、幅優先が常に有利かというとそうとも言い切れないのところがこの手のアルゴリズムの難しいところですね。

幅優先は一般に迷路の分岐数が多いとメモリが大量に必要になってしまうという欠点がありますし、探索するオブジェクトが、迷路の全体像を事前に把握できないという状況では幅優先探索は使うのが難しいのではと思います。うまいアイデアが思いつきません。

一方、深さ優先はスタックを食いつぶして実行時にエラーが出てしまうこともありえます。と言っても、.NETでスタックオーバーフローを起こした経験は覚えてる限りはないですが。

まあ、それぞれ一長一短ですね。

定義したクラスなど

定義したクラス/列挙型は以下の通りです。

Maze
　迷路を表すクラス
MazeSolver
　迷路を解くクラス
Position
　位置を表す
Tracks
　動いた経路を記録する
Viewer
　探索状況を表示するクラス
Program
　迷路探索を開始するメインクラス
Direction
　方向を表す列挙型
Place
　場所の種類(壁、道、ゴール、スタート位置)表す列挙型

MazeSolverが迷路を解くクラスです。このクラスでは前述したように、迷路の全体像を見ることはしません。Mazeクラスの一部のメソッドだけを呼び出し、今いる場所の前後左右の状況を調べるだけです。この情報を使い、曲がるのか、進むのか、はたまた今来た道を戻るのかの判断をしています。

それと、オブジェクトが迷路内をどう動いたのかをリアルタイムで分かるようにするために、ちょっと工夫をしています。

そのためにIObservable<T> IObserver<T> インターフェースを使っています。

発行者オブジェクトは、MazeSolverクラスでIObservable<Direction> インターフェースを実装しています。
これで、動くたびに現在の位置（相対位置）を購読者オブジェクトに発行しています。

購読者オブジェクト(IObserver<Direction>)は、Viewerクラスです。Viewerクラスでは、状況をコンソール画面に表示させています。

C#のコード

program.cs

using System;
using System.Diagnostics;

namespace MazeDepthFirstSearch {
    class Program {
        static void Main(string[] args) {
            var sw = Stopwatch.StartNew();

            var maze = new Maze("map2.txt");
            var v = new Viewer(maze);
            var solver = new MazeSolver();
            solver.Subscribe(v);
            var ans = solver.Solve(maze);

            sw.Stop();
            v.Replay(ans);
            Console.WriteLine("{0}ミリ秒", sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }
}

Maze.cs

using System;
using System.IO;

namespace MazeDepthFirstSearch {
    // 迷路クラス
    public class Maze {
        private char[,] _map;
        public int XSize { get; private set; }
        public int YSize { get; private set; }

        private Position _start;

        // コンストラクタ
        public Maze(string mapfile) {
            ReadMap(mapfile);
            _start = FindPosition('S');
        }

        // Mapデータを読み込む
        public void ReadMap(string mapfile) {
            string[] map = File.ReadAllLines(mapfile);
            this._map = new char[map[0].Length, map.Length];
            for (int y = 0; y < map.Length; y++) {
                var line = map[y];
                for (int x = 0; x < line.Length; x++) {
                    this._map[x, y] = line[x];
                }
            }
            XSize = map[0].Length;
            YSize = map.Length;
        }

        // インデクサ （これは、表示のみに利用する)
        public char this[int x, int y] {
            get { return _map[x, y]; }
        }

        // relativeの場所が何かを返す
        public Place Look(Position relative) {
            var pos = GetAbsolutePosition(relative);
            // pos = GetPosition(pos, direction);
            if (pos.X < 0 || pos.X >= this.XSize)
                return Place.Wall;
            if (pos.Y < 0 || pos.Y >= this.YSize)
                return Place.Wall;
            switch (_map[pos.X, pos.Y]) {
                case 'G':
                    return Place.Goal;
                case 'S':
                    return Place.Start;
                case ' ':
                    return Place.Path;
                default:
                    return Place.Wall;
            }
        }

        // 相対位置から絶対位置に変換 （相対位置は、startの位置を基準とする)
        public Position GetAbsolutePosition(Position relative) {
            return new Position {
                X = _start.X + relative.X,
                Y = _start.Y + relative.Y
            };
        }

        // target で指定した文字がある場所を求める。
        public Position FindPosition(char target) {
            for (int x = 0; x < XSize; x++) {
                for (int y = 0; y < YSize; y++) {
                    if (_map[x, y] == target)
                        return new Position { X = x, Y = y };
                }
            }
            throw new ApplicationException();
        }


        // Positionは値型なので、呼び出し元には影響を与えない
        public static Position GetPosition(Position current, Direction direction) {
            switch (direction) {
                case Direction.South:
                    current.Y++;
                    break;
                case Direction.East:
                    current.X++;
                    break;
                case Direction.North:
                    current.Y--;
                    break;
                case Direction.West:
                    current.X--;
                    break;
            }
            return current;
        }

        // 反対方向を求める
        public static Direction BackDirection(Direction direction) {
            switch (direction) {
                case Direction.South:
                    return Direction.North;
                case Direction.East:
                    return Direction.West;
                case Direction.North:
                    return Direction.South;
                case Direction.West:
                    return Direction.East;
            }
            return Direction.None;
        }
    }
}

Position.cs

using System;
namespace MazeDepthFirstSearch {
    // 位置情報構造体
    public struct Position {
        public int X { get; set; }
        public int Y { get; set; }

        public override string ToString() {
            return $"({X},{Y})";
        }
    }
    // Position
    public enum Direction {
        None,
        East,
        West,
        South,
        North
    }

    public enum Place {
        Wall,
        Path,
        Goal,
        Start
    }
}

MazeSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace MazeDepthFirstSearch {
    // 深さ優先探索
    // 自分がいる絶対的な位置を知ることはできないものとする。
    // スタート位置を(0,0とし、どのように進んだかを自分自身で把握することで
    // 相対的な位置だけはわかる。
    // 迷路についてわかるのは自分の周りが道なのか壁なのかゴールなのかだけとする。
    public class MazeSolver : IObservable<Direction> {
        private Maze _maze;

        // 解く。必ず解が存在することが前提。
        public IEnumerable<Direction> Solve(Maze maze) {
            _maze = maze;
            _footprint.Add(_current);
            _Solve();
            return _path.Reverse();
        }

        // ４つの方向を列挙する （直前の方向を最初にする)
        public IEnumerable<Direction> Directions() {
            if (_lastDirection != Direction.None)
                yield return _lastDirection;
            if (_lastDirection != Direction.South)
                yield return Direction.South;
            if (_lastDirection != Direction.East)
                yield return Direction.East;
            if (_lastDirection != Direction.North)
                yield return Direction.North;
            if (_lastDirection != Direction.West)
                yield return Direction.West;
        }

        private Position _current = new Position { X = 0, Y = 0 };

        private List<Position> _footprint = new List<Position>();

        private Stack<Direction> _path = new Stack<Direction>();

        private Direction _lastDirection = Direction.None;

        // Solveの下請け 再帰的に呼び出される
        private bool _Solve(int level = 0) {
            foreach (var direction in Directions().ToList()) {
                var temp = Maze.GetPosition(_current, direction);
                switch (_maze.Look(temp)) {
                    case Place.Goal:
                        return true;
                    case Place.Start:
                        return false;
                    case Place.Path:
                        if (!AlreadyPassed(temp)) {
                            Walk(direction);
                            if (_Solve(level + 1))
                                return true;
                            Back(direction);
                        }
                        break;
                }
            }
            return false;
        }

        // 指定した方向へ歩く。
        private void Walk(Direction direction) {
            _current = Maze.GetPosition(_current, direction);
            _footprint.Add(_current);
            _path.Push(direction);
            _lastDirection = direction;
            Publish(direction);
        }

        // 逆の方向に戻る。
        public void Back(Direction direction) {
            var dir = Maze.BackDirection(direction);
            _current = Maze.GetPosition(_current, dir);
            Publish(dir);
            _path.Pop();
        }

        // 逆戻りする
        private void TurnBack(Direction direction) {
            while (true) {
                var dir = Maze.BackDirection(_path.Pop());
                Back(dir);
                foreach (var nd in Directions()) {
                    var temp = Maze.GetPosition(_current, nd);
                    if (_maze.Look(temp) == Place.Path && !AlreadyPassed(temp))
                        // その方向が指す場所は、まだ試していない （_footprintにない) なら、もう戻らなくて良い
                        return;
                }
                // 行くべき道がないから、さらに戻る
            }
        }

        // 指定した方向は既に通った場所か
        private bool AlreadyPassed(Position pos) {
            return _footprint.Exists(p => p.X == pos.X && p.Y == pos.Y);
        }

        // このプログラムでは購読者は、Viewerオブジェクトの一つだけ。
        private List<IObserver<Direction>> _observers = new List<IObserver<Direction>>();

        // 終了を通知する
        private void Complete() {
            foreach (var observer in _observers) {
                observer.OnCompleted();
            }
        }

        // 状況変化を知らせるために購読者に通知する
        private void Publish(Direction state) {
            foreach (var observer in _observers) {
                observer.OnNext(state);
            }
        }

        // observer(購読者) が通知を受け取れるようにする
        public IDisposable Subscribe(IObserver<Direction> observer) {
            _observers.Add(observer);
            return observer as IDisposable;
        }
    }
}

Viewer.cs

using System;
using System.Collections.Generic;

namespace MazeDepthFirstSearch {
    class Viewer : IObserver<Direction> {
        private Maze _maze;

        public Viewer(Maze maze) {
            _maze = maze;
            Console.SetCursorPosition(0, 0);
            Print();
        }

        public void OnCompleted() {
        }

        public void OnError(Exception error) {
        }

        private Position _current = new Position { X = 0, Y = 0 };

        // 状態が変化した （引数 d には、動いた方向が渡ってくる)
        public void OnNext(Direction d) {
            // d方向に一つ動いた位置を新しい位置にする
            _current = Maze.GetPosition(_current, d);
            // 絶対位置を求め
            var pos = _maze.GetAbsolutePosition(_current);
            // 足跡を残す
            Console.SetCursorPosition(pos.X, pos.Y);
            Console.Write('.');
            Console.SetCursorPosition(pos.X, pos.Y);
            System.Threading.Thread.Sleep(100);
        }

        public void Replay(IEnumerable<Direction> path) {
            var current = new Position { X = 0, Y = 0 };
            foreach (var d in path) {
                current = Maze.GetPosition(current, d);
                var pos = _maze.GetAbsolutePosition(current);
                Console.SetCursorPosition(pos.X, pos.Y);
                Console.Write('.');
                Console.SetCursorPosition(pos.X, pos.Y);
                System.Threading.Thread.Sleep(0);
            }
            Console.SetCursorPosition(0, _maze.YSize + 1);

        }

        // 迷路をConsoleに表示する
        public void Print() {
            for (int y = 0; y < _maze.YSize; y++) {
                for (int x = 0; x < _maze.XSize; x++) {
                    Console.Write(_maze[x, y]);
                }
                Console.WriteLine();
            }
        }
   }
}

この記事は、Gushwell's C# Programming Pageで公開したものをソースコードも含め加筆・修正したものです。