はてなブックマーク

迷路を解く アルゴリズムの基本問題に迷路を解くというものがあります。 迷路をグラフの一種とすることで、グラフの探索アルゴリズムが使えます。 基礎的なグラフの探索アルゴリズムに幅優先探索と、深さ優先探索があります。 幅優先探索と深さ優先探索 それぞれ、どのように動作するのか見てみましょう。 まずは、空の迷路を幅優先探索で解いてみます。 左上をスタート、右下をゴールとすると、探索済みのセルを水色に塗ってます。 幅優先探索だと水が広がるように、探索が進んでいきます。これは、スタート地点から近いセルの順に見ていくというアルゴリズムだからです。余談ですが、幅優先探索は絵の塗りつぶしにも使われてます。 幅優先探索が迷路に向いてるのは、それぞれのセルに最短の前のセルと、そこまでの移動回数を保存しておくことで、迷路を解くと同時に最短経路も割り出せるからです。 こちらは、猪突猛進　　深さ優先探索です。とにか