はじめに
アルゴリズム、というか競技プログラミングに関するネタです。
昨日までの自分にとって有益な情報なので、Qiitaに載せておきます。
これまで再帰を使った深さ優先探索しか理解できておらず、しかも理解が甘くて使おうとしても毎度ワタワタする始末。これではいかんと思い、以下3つのパターンについて極力シンプルな形で実装してみました。
- 深さ優先探索（DFS, Depth-First Search）
- 再帰による実装
- スタックによる実装
- 幅優先探索（BFS, Breadth-First Search）
- キューによる実装
すべてRubyでの実装です。Ruby 2.3.3での動作を確認しています。
お題
アルファベット
A, B, Cからなる、3文字以下の文字列の組み合わせをすべて取得する。
このお題を、全探索で解きます。この手の全探索だと"迷路を解く"問題が定番ですが、シンプルさを重視した結果こんなお題です。
深さ優先探索
再帰による実装
文字数が3文字になるまで、現在の文字列に追加の一文字を足して同じメソッドに突っ込む、というスタイルです。停止条件におけるreturnがキモ。
個人的にはこれが一番腑に落ちるスタイル（元々これしか使えていなかったというのもあるけど）。ただ、停止条件やその他の処理が複雑になると途端にわけが分からなくなるのもこのパターンかなぁ、という気がしています。
$debug = true
def recursive_dfs(patterns, string="")
# 文字列を配列に格納する
patterns << string unless string.empty?
# 停止条件: 文字列長が3文字になること
if string.length == 3
patterns << "<leaf>" if $debug
return
end
# 分岐処理
recursive_dfs(patterns, string+"A")
recursive_dfs(patterns, string+"B")
recursive_dfs(patterns, string+"C")
end
patterns = [] # 結果を格納する配列を用意しておく
recursive_dfs(patterns)
p patterns # 組み合わせの表示
# => ["A", "AA", "AAA", "<leaf>", "AAB", "<leaf>", "AAC", "<leaf>", "AB", "ABA", "<leaf>", "ABB", "<leaf>", "ABC", "<leaf>", "AC", "ACA", "<leaf>", "ACB", "<leaf>", "ACC", "<leaf>", "B", "BA", "BAA", "<leaf>", "BAB", "<leaf>", "BAC", "<leaf>", "BB", "BBA", "<leaf>", "BBB", "<leaf>", "BBC", "<leaf>", "BC", "BCA", "<leaf>", "BCB", "<leaf>", "BCC", "<leaf>", "C", "CA", "CAA", "<leaf>", "CAB", "<leaf>", "CAC", "<leaf>", "CB", "CBA", "<leaf>", "CBB", "<leaf>", "CBC", "<leaf>", "CC", "CCA", "<leaf>", "CCB", "<leaf>", "CCC", "<leaf>"]
ちなみに、停止条件（文字列長が3文字）のタイミングが明確になるように、組み合わせ結果に<leaf>という文字列を追加しています。先頭行を$debug = falseとすればこの処理は行われません（他パターンのコードでも同様）。
再帰のネストが深くなりやすい点については注意した方がいいかもしれません。
スタックによる実装
同じく深さ優先探索ですが、再帰ではなくスタックを用います。現在の文字列に一文字追加したものをスタックに積んでいきループで処理する、という構造にすることで再帰を回避しています。
そのため、再帰による実装と違ってネストが深くならないところはメリットですね。
$debug = true
def iterative_dfs(patterns)
# スタックとなる配列を用意し、初期状態である空文字列を格納する
stack = [""]
until stack.empty?
# スタックから1つ取り出す（末尾から取り出すのでpopを使う）
string = stack.pop
# 文字列を配列に格納する
patterns << string unless string.empty?
# 停止条件: 文字列長が3文字になること
if string.length == 3
patterns << "<leaf>" if $debug
else
# 分岐処理
stack << string+"C"
stack << string+"B"
stack << string+"A"
end
end
end
patterns = [] # 結果を格納する配列を用意しておく
iterative_dfs(patterns)
p patterns # 組み合わせの表示
# => ["A", "AA", "AAA", "<leaf>", "AAB", "<leaf>", "AAC", "<leaf>", "AB", "ABA", "<leaf>", "ABB", "<leaf>", "ABC", "<leaf>", "AC", "ACA", "<leaf>", "ACB", "<leaf>", "ACC", "<leaf>", "B", "BA", "BAA", "<leaf>", "BAB", "<leaf>", "BAC", "<leaf>", "BB", "BBA", "<leaf>", "BBB", "<leaf>", "BBC", "<leaf>", "BC", "BCA", "<leaf>", "BCB", "<leaf>", "BCC", "<leaf>", "C", "CA", "CAA", "<leaf>", "CAB", "<leaf>", "CAC", "<leaf>", "CB", "CBA", "<leaf>", "CBB", "<leaf>", "CBC", "<leaf>", "CC", "CCA", "<leaf>", "CCB", "<leaf>", "CCC", "<leaf>"]
以下、処理の流れを追ってみます。
スタックには初期値である空の文字列""だけが格納されている状態です。
空文字列とは言ってもスタック自体が空というわけではないので、untilループがスタートします。
スタックから""を取り出しますが、空文字列なのでpatternsには格納しません。
スタックはこれで空っぽになりました。
""の文字列長は0なので、一文字を追加した"C", "B", "A"をスタックに積みます。
スタックの中身は"C", "B", "A"です。
スタックは空ではないため、untilループが続行します。
末尾から"A"を取り出してpatternsに格納します。
スタックには"C", "B"が残ります。
"A"の文字列長は1なので、一文字を追加した"AC", "AB", "AA"をスタックに積みます。
スタックの中身は"C", "B", "AC", "AB", "AA"です。
スタックは空ではないため、untilループが続行します。
末尾から"AA"を取り出してpatternsに格納します。
スタックには"C", "B", "AC", "AB"が残ります。
"AA"の文字列長は2なので、一文字を追加した"AAC", "AAB", "AAA"をスタックに積みます。
スタックの中身は"C", "B", "AC", "AB", "AAC", "AAB", "AAA"です。
スタックは空ではないため、untilループが続行します。
末尾から"AAA"を取り出してpatternsに格納します。
スタックには"C", "B", "AC", "AB", "AAC", "AAB"が残ります。
"AAA"の文字列長は3なので、停止条件に合致します。
スタックへの追加は行いません。
スタックの中身は"C", "B", "AC", "AB", "AAC", "AAB"です。
スタックは空ではないため、untilループが続行します。
末尾から"AAB"を取り出してpatternsに格納します。
スタックには"C", "B", "AC", "AB", "AAC"が残ります。
"AAB"の文字列長は3なので、停止条件に合致します。
スタックへの追加は行いません。
スタックの中身は"C", "B", "AC", "AB", "AAC"です。
以下略。最後にはスタックに残った"CCC"を取り出して終わります。
分岐処理での文字追加をアルファベットの逆順にしているのは、再帰による実装と結果の出力を同じにしたかったためという表示上の都合です。"A", "B", "C"の順番だとどうなるか分からない場合は実際にそう書き換えて実行してみよう。
幅優先探索
キューによる実装
今度は幅優先探索です。とは言っても、スタックによる深さ優先探索とほとんど同じで、現在の文字列に一文字追加したものをキューに積んでいく、という処理を行っています。実質的に違っているのはスタックかキューかという部分だけ、つまり積んだものを末尾から取り出すか先頭から取り出すかの違いでしかありません。
$debug = true
def iterative_bfs(patterns)
# キューとなる配列を用意し、初期状態である空文字列を格納する
queue = [""]
until queue.empty?
# キューから1つ取り出す（先頭から取り出すのでshiftを使う）
string = queue.shift
# 文字列を配列に格納する
patterns << string unless string.empty?
# 停止条件: 文字列長が3文字になること
if string.length == 3
patterns << "<leaf>" if $debug
else
# 分岐処理
queue << string+"A"
queue << string+"B"
queue << string+"C"
end
end
end
patterns = [] # 結果を格納する配列を用意しておく
iterative_bfs(patterns)
p patterns # 組み合わせの表示
# => ["A", "B", "C", "AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC", "AAA", "<leaf>", "AAB", "<leaf>", "AAC", "<leaf>", "ABA", "<leaf>", "ABB", "<leaf>", "ABC", "<leaf>", "ACA", "<leaf>", "ACB", "<leaf>", "ACC", "<leaf>", "BAA", "<leaf>", "BAB", "<leaf>", "BAC", "<leaf>", "BBA", "<leaf>", "BBB", "<leaf>", "BBC", "<leaf>", "BCA", "<leaf>", "BCB", "<leaf>", "BCC", "<leaf>", "CAA", "<leaf>", "CAB", "<leaf>", "CAC", "<leaf>", "CBA", "<leaf>", "CBB", "<leaf>", "CBC", "<leaf>", "CCA", "<leaf>", "CCB", "<leaf>", "CCC", "<leaf>"]
深さ優先探索の場合の出力結果と異なり、1文字の結果、2文字の結果、3文字の結果というように文字列長ごとに結果が並びます。これが都合良い、というケースもあるでしょうね。まぁ別のやり方使ってからソートすればいいという気もしますが。
こちらも、処理の流れを追っておきます。
キューには初期値である空の文字列""だけが格納されている状態です。
空文字列とは言ってもキュー自体が空というわけではないので、untilループがスタートします。
キューから""を取り出しますが、空文字列なのでpatternsには格納しません。
キューはこれで空っぽになりました。
""の文字列長は0なので、一文字を追加した"A", "B", "C"をキューに積みます。
キューの中身は"A", "B", "C"です。
キューは空ではないため、untilループが続行します。
先頭から"A"を取り出してpatternsに格納します。
キューには"B", "C"が残ります。
"A"の文字列長は1なので、一文字を追加した"AA", "AB", "AC"をキューに積みます。
キューの中身は"B", "C", "AA", "AB", "AC"です。
キューは空ではないため、untilループが続行します。
先頭から"B"を取り出してpatternsに格納します。
キューには"C", "AA", "AB", "AC"が残ります。
"B"の文字列長は1なので、一文字を追加した"BA", "BB", "BC"をキューに積みます。
キューの中身は"C", "AA", "AB", "AC", "BA", "BB", "BC"です。
キューは空ではないため、untilループが続行します。
先頭から"C"を取り出してpatternsに格納します。
キューには"AA", "AB", "AC", "BA", "BB", "BC"が残ります。
"C"の文字列長は1なので、一文字を追加した"CA", "CB", "CC"をキューに積みます。
キューの中身は"AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC"です。
キューは空ではないため、untilループが続行します。
先頭から"AA"を取り出してpatternsに格納します。
キューには"AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC"が残ります。
"AA"の文字列長は2なので、一文字を追加した"AAA", "AAB", "AAC"をキューに積みます。
キューの中身は"AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC", "AAA", "AAB", "AAC"です。
中略。
キューは空ではないため、untilループが続行します。
先頭から"AAA"を取り出してpatternsに格納します。
キューには"AAB", "AAC", "ABA", "ABB", "ABC", ..., "CCB", "CCC"が残ります。
"AAA"の文字列長は3なので、停止条件に合致します。
キューへの追加は行いません。
キューの中身は"AAB", "AAC", "ABA", "ABB", "ABC", ..., "CCB", "CCC"です。
以下略。最後にはキューに残った"CCC"を取り出して終わります。
注意点
スタックによる深さ優先探索とキューによる幅優先探索は実装コードがほぼ同じですが、キューによる幅優先探索には、『探索するパターンが増えると、キューが巨大化する傾向にある』という欠点があります。
お題の通りの条件では、スタックの最大長が7なのに対してキューの最大長は27です。これくらいだとそれほど大差はありません。
ですが、たとえば文字の種類が"A"から"E"までの5種類で文字列長が8文字以下、という条件の場合だと、スタックの最大長が33なのに対してキューの最大長は390,625となります。
おわりに
シンプル化するとどれもかなりカンタンなコードになりますねぇ。
これらの中だとスタックによる深さ優先探索が一番混乱しにくいコードを書けそうだと感じました。ただ、今の所再帰による実装の方に慣れてしまっているので、分岐処理を"スタックに収められる形で書く"ことに難儀しそうな気も……。
文中の間違いの指摘や改善のためのアドバイスなど、大歓迎です。