「全部調べる」は悪くない――全探索から始める問題解決

「全部調べるなんて、力技で美しくない」と思っていませんか。確かに、エレガントな解法はかっこいいものです。けれども、問題解決の第一歩として、全部を漏れなく調べる「全探索」は、とても頼りになります。この記事では、全探索の使い方と、その強みと限界を、具体的な問題で見ていきます。

全探索とは、「漏れなく、順番に」調べること

問題：100円玉、50円玉、10円玉を何枚でも使って、ちょうど200円を作る方法は何通りありますか。

ただ闇雲に書き出すと、漏れや重複が出ます。全探索のコツは、順番を決めることです。大きい硬貨の枚数から決めていきます。

• 100円玉が0枚のとき：200円を50円玉と10円玉で作ります。50円玉は0枚から4枚の5通り（残りは10円玉で埋めます）。
• 100円玉が1枚のとき：残り100円。50円玉は0枚から2枚の3通り。
• 100円玉が2枚のとき：残り0円。1通り。

合計 $5+3+1=9$ 通りです。順番を決めたおかげで、漏れなく数えられました。10円玉の枚数は、他が決まれば自動的に決まるので、数える必要がありません。

全探索から、規則が見えてくる

問題：2桁の整数で、十の位と一の位を入れ替えると、元の数より27大きくなるものをすべて求めなさい。

十の位が1から9、一の位が0から9の90通りを、全部試すのは大変です。そこで、いくつか試してみましょう。14を入れ替えると41で、$41-14=27$。25を入れ替えると52で、$52-25=27$。36は63、47は74、58は85、69は96で、どれも差が27です。

ここで、「十の位と一の位の差が3になっている」ことに気づけます。式で確かめましょう。十の位を $a$、一の位を $b$ とすると、元の数は $10a+b$、入れ替えた数は $10b+a$ です。

$$(10b+a)-(10a+b)=9(b-a)$$

この式は、入れ替えた数と元の数の差が、一の位と十の位の差の9倍になることを表しています。これが27になるのは、$b-a=3$ のときです。$a$ は1から6までで、答えは14、25、36、47、58、69の6個です。全探索で規則を見つけ、式で理由を説明できました。

全探索の落とし穴と、限界

全探索は反例を探すのにも強い方法です。$n^2+n+41$ という式に、$n=0,1,2,\ldots$ を入れてみてください。$n=0$ から $n=39$ まで、結果は41、43、47、53、……と、すべて素数になります。この規則を見つけたら、「いつでも素数になる」と信じたくなるでしょう。

ところが、$n=40$ では $40^2+40+41=1681=41^2$ となり、素数ではありません。40回連続で成り立っても、それは証明にはなりません。全探索で見つかるのは、あくまで「その範囲では成り立つ」という事実です。

もう一つの限界は、調べる量の爆発です。30個の物から、取る・取らないを選ぶ場合の数は $2^{30}=1{,}073{,}741{,}824$、つまり約10億通りにもなります。人の手では無理で、コンピュータでも工夫が必要になります。

全探索を賢く使うコツ

全探索を始めるとき、次の3つを意識してみてください。

1. 調べる順番を決めて、漏れと重複を防ぐ。
2. 小さい範囲から始めて、規則を探す。
3. 規則が見つかったら、理由を式や図で説明する。

全探索は終点ではなく、始点です。調べた結果から、「全部調べなくても分かる理由」を探すことで、問題の構造が見えてきます。

まとめ

全探索は、順番を決めて漏れなく調べれば、立派な問題解決の方法です。規則を見つけるきっかけになり、反例の発見にも強い反面、「調べた範囲で成り立つ」ことは証明にならず、量が増えると限界が来ます。解き方が思いつかないときは、まず小さい範囲で、全部調べてみてください。