迷路を解く
アルゴリズムの基本問題に迷路を解くというものがあります。
迷路をグラフの一種とすることで、グラフの探索アルゴリズムが使えます。
基礎的なグラフの探索アルゴリズムに幅優先探索と、深さ優先探索があります。
幅優先探索と深さ優先探索
それぞれ、どのように動作するのか見てみましょう。
まずは、空の迷路を幅優先探索で解いてみます。
左上をスタート、右下をゴールとすると、探索済みのセルを水色に塗ってます。
幅優先探索だと水が広がるように、探索が進んでいきます。これは、スタート地点から近いセルの順に見ていくというアルゴリズムだからです。余談ですが、幅優先探索は絵の塗りつぶしにも使われてます。
幅優先探索が迷路に向いてるのは、それぞれのセルに最短の前のセルと、そこまでの移動回数を保存しておくことで、迷路を解くと同時に最短経路も割り出せるからです。
こちらは、猪突猛進 深さ優先探索です。とにかく自分がいる場所から先に進んでいきます。
どちらのアルゴリズムでも全部のセルを探索してますが、深さ優先探索の場合の経路は無駄が大きいですね。
まぁ、でも迷路によっては特に変わりません
こちらは、幅優先
こっちは、深さ優先
ゴールがスタート地点より、もっとも遠い場所にある場合で、最短距離が不要な場合は
そんなに変わらなく見えますね。
ゴールが近いと、幅優先探索の方が少ないステップで見つかります。
こちらは、深さ優先探索に不利な例
幅優先
深さ優先
実装
深さ優先探索は、再帰関数で書くことが多いのですが、個人的にはWhileループを使った方法が
オススメです。一旦、やり方を覚えてしまえば、データ構造を変えることで、深さ優先、幅優先どちらもシンプルに書けるからです。
まず、幅優先探索から
基本的に、行けるセルをチェックして、Queueに積んでいきます。
Queueの場合、積まれたセルが一番後回しになるため、近い順に迷路をチェックしていけます。
func BFS(movie []image.Image, m CellMap) []image.Image {
var n Point
// Queue に初期値を積む
queue := []Point{Point{1, 1}}
for len(queue) > 0 {
// queueから取り出す
n, queue = queue[0], queue[1:]
// 行けるセルとをチェック
for _, d := range directions {
if m[n.X+d.X][n.Y+d.Y] == GOAL {
return movie
}
if m[n.X+d.X][n.Y+d.Y] == 0 {
m[n.X+d.X][n.Y+d.Y] = VISITED
// Queueに積む
queue = append(queue, Point{n.X + d.X, n.Y + d.Y})
}
}
movie = shot(movie, m) // GIFアニメを一コマ撮影
}
movie = shot(movie, m) // GIFアニメを一コマ撮影
return movie
}
こちらは、深さ優先。
Queueの代わりに、Stackを使います。Stackでは、最後に追加した要素が、次で使われます。
ですので、見つかった順に深堀していくことができます。
func DFS(movie []image.Image, m CellMap) []image.Image {
stack := []Point{Point{1, 1}}
var n Point
for len(stack) > 0 {
n, stack = stack[0], stack[1:]
m[n.X][n.Y] = VISITED
for _, d := range directions {
if m[n.X+d.X][n.Y+d.Y] == GOAL {
return movie
}
if m[n.X+d.X][n.Y+d.Y] == EMPTY {
stack = append([]Point{Point{n.X + d.X, n.Y + d.Y}}, stack...)
}
}
movie = shot(movie, m)
}
movie = shot(movie, m)
return movie
}
幅優先はQueue 深さ優先は、Stackとすることで基本的なコードの構造は全く同じですし、
デバッグも容易です。
余談
余談ですが、このデータ構造を優先度付きQueue(Priority Queue)にすると、ダイクストラ法を実装できます。ダイクストラ法は、グラフの辺に重み付けがある場合に使う最短経路探索アルゴリズムです。
GoでのStackとQueueの実装にはもっとうまい方法があります。上記のやり方だと、メモリがうまくGCされないのという欠点があります。
リンクリストを使うのが良いでしょう。 container/listを使った例
スライスを使った例でも、stackも最後の要素を使うようにすれば、append部分を早くできますね。