前回の投稿から数日、プリクラ問題の議論はますます盛んになっていたようです。またちょっと手出しをしてみたので、その記録を書いておきます。
おさらいすると、プリクラ問題とは「n人の集団でm人ずつプリクラを撮るとき、全てのペアが一緒に撮影されるために必要な最小枚数P(n,m)はどのように求まるか」というものでした。
議論は厳密解の探索が主眼となっているようです。この厳密解というのは結構難しくて、何か適当な方法で解を出すのでは駄目で、それが理論的な下限値であることを証明する必要があります。
つまり真っ直ぐなアプローチとしては、常に効率的な組み合わせを見つける一般的な方法を提案し、また理論値ぴったりの下限値の計算法を求め、これらが一致することを示すことになるわけです。しかし、全ての条件を満たすようにこれを解くのは楽な話ではありません。
ある問題の最小値・最大値がわかっていないというのはそれほど珍しい話ではなく、例えばn次元接吻数(ある球の周囲に何個の球が置けるか)は、いくつかの小さい値についてのみしか知られていません。
計算に関わる話ではビジービーバー関数というものが知られていて、ざっくり「n状態をとる停止するチューリングマシンのうちで最も長く出力を吐き出すもの」という定義です、これは答えがあるにも関わらず計算できないことが示されています。
もう少し近い話ではラムゼーの定理というのもあります。ある大きさの完全グラフをいくつかの色に塗る話で、具体例では「6人いれば互いに知り合いか互いに知らない3人組が必ず存在する」などと表現されます。これも一般のn人の場合は非常に難しい問題になります。
もっと単純な話になると、「この15パズルは最短で何手で解ける？」みたいな問題もあります。
このような一般の場合について理論解が出せないときにしばしば役に立つ強力な武器として、探索があります。つまり、全部の撮影の組み合わせをやってみればいいんですね。あるK枚でやってみて全ての場合で駄目で、またK+1枚で解を見つけた場合、それが文句なく答えになるわけです。6×6のオセロは全ての手が解析され後手必勝が確定しましたし、最近だとルービックキューブの全ての状態は最悪20手で解けるという証明がありました。これらは探索により示されたものです。
さて、プリクラ問題に対して全数探索は役に立つのでしょうか。今回は探索の準備編です。