深さ優先探索アルゴリズムと同じく初期状態からたどり着ける全ての状態を探索するが、初期状態に近い状態から順番に探索するので最短経路が確実に求まる。
例題：迷路の最短路（経路は求めずに距離だけ）
- 問題
- 通路と壁からできている迷路があり、1ターンに隣接する上下左右4マスの通路（いわゆる「4近傍」）へ移動できる。スタートからゴールまで移動するのに必要な最小のターン数を求める（ただし、スタートからゴールまで移動できると仮定）。
- 迷路の例
....####..####.#...# .#.##.......#.#..... .#S#...#.##.#.#..##. .###....#..##....#.# ........####..#####. ##.#..#.#....#.#..#. .#.###..#.#.##..#.#. ...#.#....#.##..###. #..#...#.####G.##.#. ...#.#.#......#...## ##...#.....###.#.#.# #.#..#####.#...####. ###....###.##.###.##
ここで、 S, G, ., # はそれぞれスタート、ゴール、通路、壁を表す。
解（Emacs Lispの場合）
一般的な解法では、迷路と同じサイズの二次元配列を最初に用意しておき、探索をしながらスタート地点からのターン数、すなわち距離の値を配列に記録していく。また、二次元配列を初期化するときに特異な値を代入することで、その座標が探索済みかどうか判断できるようにしておく。この解法を踏まえつつ、次の変更を加えてEmacs Lispで実装した。
- 二次元配列は使わず、探索済みの座標をリストに記録していく
- 探索済み座標のリストには、ターン数もセットで記録する。要素は、行・列・ターン数の3要素をもつリストになるので、たとえば '((0 1 1) (1 0 1) (0 2 2) (1 2 2) ...) というような形になる
- 迷路の座標と一対一に対応する配列を持たないので経路を求めることはできないが、ターン数だけを求めるのでこれでよしとする
;;; 幅優先探索（BFS）の例題：迷路の最短路問題
(defun minimum-distance ()
"カーソルを迷路の下に移動させて実行すると、スタート（S）とゴール（G）の距離をミニバッファに出力。探索した場所を / に置換しながら進む。"
(interactive)
(save-excursion
(search-backward "S")
(let* ((flg t) ;発見したらnil
(dist 0) ;距離
(visited) ;探索済み座標のリスト
(queue (list-next-positions dist))) ;探索する座標のリスト
(while (and queue flg) ;探索対象あり、かつ未発見の場合
(funcall ;queueからpopした要素に関数を適用
(lambda (pos) ;ゴールか調べつつ、queueに追加
(progn
(goto-line (first pos))
(move-to-column (second pos))
(sit-for 0.05)
(cond
((eq (char-after) ?G) ;ゴールかどうか
(message "Answer: %d" (third pos)) ;結果表示
(setf flg nil)) ;while終了
(t (insert ?/)
(delete-char 1)
(backward-char)
(setf queue ;次の探索対象をqueueに追加
(append
queue
(list-next-positions (third pos)) ))))))
(pop queue) )))))
(defun list-next-positions (dist)
"現在のカーソル位置から次の探索位置を求める補助関数。結果はリストにして返す。また、動的スコープを利用してminimum-distance の中の visited も変更する。"
(let* ((row (line-number-at-pos))
(col (current-column))
(poslist `((,(1- row) ,col) ;移動方向 上
(,row ,(1+ col)) ;右
(,(1+ row) ,col) ;下
(,row ,(1- col))))) ;左
(setf visited ;呼び出し元の visited を変更
(mapcar
(lambda (pos) (append pos `(,(1+ dist)))) ;距離を追加
(remove-if
(lambda (pos)
(let ((row (first pos))
(col (second pos)) )
(or (< col 0) ;列がマイナスの場所は対象外
(progn (goto-line (first pos)) ;通路かゴール以外は対象外
(move-to-column (second pos))
(not (find (char-after) '(?. ?G))))
(some (lambda (v) ;探索済みなら対象外
(and (eq row (first v)) (eq col (second v))))
visited))))
poslist)))))
実行＆結果
- *scratch*バッファなどで、".", "#", "S", "G" を使った迷路のASCIIアートを描く（SからGまで辿り着けるようになっていること）。
- M-x minimum-distance を実行する。
- 通路"."が"/"に置換されていき、"G"に逹するとミニバッファにターン数が表示される。
0 件のコメント:
コメントを投稿