組み合わせ爆発の問題を解こうその3 – 幅優先探索(Breadth-first Search,BFS)

Mathematics and Natural Language Processing

2012-09-17Mathematics

幅優先探索は、1手ずつ動かしていく探し方です。では、早速、例題と、そこから1手進めた状態を見てみましょう。

1手目からは、下か左にしか動かせませんでした。では、2手目にはどのような動かし方があるでしょうか。

下に動かして上に動かすというのは意味がありませんから考慮しません。1手目を下に動かした場合は、2手目として “さらに下に動かす”、”右に動かす”、”左に動かす”の3つの動かし方があります。1手目に左に動かした場合は、下に動かすしかありません。

3手目はどうでしょうか。

1手目→2手目では動かし方が2パターンから4パターンに増えましたが、2手目→3手目は4パターンのままです。こういう場合もあるのですね。しかし、一番下のパターン、すなわち、左→下→右に動かした場合、4手目にはここからさらに上、右、下に動かすパターンが生まれます。

このように、1手ずつ動かし方を調べていくと、考えられる動かし方がどんどん増えていくのが、幅優先探索の特徴です。

また、1手ずつ探索するため、一番最初に完成の動かし方が見つかったら、それが最適な動かし方(場合によっては、いくつか考えられる最適な動かし方のうちの1つ)であることもわかります。

では、今回もプログラムを組んで、幅優先探索で解法を見つけるまでの手順を下記に列挙してみます。

深さ優先探索では9198回動かさなければならなかったのに、今回は41回動かせば解答に辿りつけました。これは早いですね。

しかし、幅優先探索にも弱点があります。それは、メモリの使用量が多いこと。n手目にすすめるためにはn-1手目の状態をすべて覚えて置かなければなりません。今回の問題は7手で解けましたが、30手を超えるような動かし方が必要な場合は、ほぼ確実にメモリが足りなくなります。

ということで、幅優先探索でスライドパズルを解くときの特徴は次のとおりです。

次回は、組合せ爆発について、もう少しまとめてみたいと思います。

Topic