前回の投稿から数日、プリクラ問題の議論はますます盛んになっていたようです。またちょっと手出しをしてみたので、その記録を書いておきます。
おさらいすると、プリクラ問題とは「n人の集団でm人ずつプリクラを撮るとき、全てのペアが一緒に撮影されるために必要な最小枚数P(n,m)はどのように求まるか」というものでした。
議論は厳密解の探索が主眼となっているようです。この厳密解というのは結構難しくて、何か適当な方法で解を出すのでは駄目で、それが理論的な下限値であることを証明する必要があります。
つまり真っ直ぐなアプローチとしては、常に効率的な組み合わせを見つける一般的な方法を提案し、また理論値ぴったりの下限値の計算法を求め、これらが一致することを示すことになるわけです。しかし、全ての条件を満たすようにこれを解くのは楽な話ではありません。
ある問題の最小値・最大値がわかっていないというのはそれほど珍しい話ではなく、例えばn次元接吻数(ある球の周囲に何個の球が置けるか)は、いくつかの小さい値についてのみしか知られていません。
計算に関わる話ではビジービーバー関数というものが知られていて、ざっくり「n状態をとる停止するチューリングマシンのうちで最も長く出力を吐き出すもの」という定義です、これは答えがあるにも関わらず計算できないことが示されています。
もう少し近い話ではラムゼーの定理というのもあります。ある大きさの完全グラフをいくつかの色に塗る話で、具体例では「6人いれば互いに知り合いか互いに知らない3人組が必ず存在する」などと表現されます。これも一般のn人の場合は非常に難しい問題になります。
もっと単純な話になると、「この15パズルは最短で何手で解ける？」みたいな問題もあります。
このような一般の場合について理論解が出せないときにしばしば役に立つ強力な武器として、探索があります。つまり、全部の撮影の組み合わせをやってみればいいんですね。あるK枚でやってみて全ての場合で駄目で、またK+1枚で解を見つけた場合、それが文句なく答えになるわけです。6×6のオセロは全ての手が解析され後手必勝が確定しましたし、最近だとルービックキューブの全ての状態は最悪20手で解けるという証明がありました。これらは探索により示されたものです。
さて、プリクラ問題に対して全数探索は役に立つのでしょうか。今回は探索の準備編です。
ここで問題になるのが、「全部」という言葉の重みです。とりあえず一度に3人撮れる(m=3)としてみましょう。
n=3のとき、考えられるグループの数は1つ。グループのとり方も1通りです。
n=10のとき、考えられるグループの種類は10C3=120。ここから最低でも17グループは選ばなければいけないので、考えるべき場合の数は13402965071510936363453147136000通り。ざっくり1340穣通りあります。
n=20のときは考えられるグループの種類が20C3=1140通り。ここから最低67グループを選ぶ必要があるので、場合の数は24632027272265407851755792342941480110542823292787356136303603099978529966590712644203043369231027481876913500通り。えーと…呼び方がありません。
見事に組み合わせ爆発を起こしています。真面目に取り組んだら人手はもちろんのことコンピュータでも解けません。無理に解こうとすると宇宙の年齢というより仏教用語的なレベルの時間が必要になります。
では解けないかというと、それはまた別の話。探索の途中でうまい方法を使ってその先に解がないことを示せれば、そこから先の探索を全て省くことができます。いわゆる枝刈りです。上手な枝刈りを行えば探索の範囲は非常に狭くできるので、現実的な時間で厳密解を出せる範囲がぐっと広がります。
まずは枝刈りの話の前に、探索自体の進め方について。探索は大きく分けて「1手目の全パターン、2手目までの全パターン…」と上から順に全て列挙していく幅優先探索と、「この手順では駄目、次の手順では駄目…」と1セットごとに調べていく深さ優先探索がありますが、今回は場合の数がとても多いので一度に列挙する幅優先探索は使えません。深さ優先探索となりますが、同時に最適値を探す必要があるので、反復深化深さ優先探索と呼ばれる手法を使います。グループ数Kを段階的に増やしていきつつ、何度も深さ優先探索を行う方法ですね。
はじめにm人グループがとれる全てのパターンを列挙します。この中から1つを選びます。次のステップで別のグループを1つ選びます。どこかで条件を満たさなくなれば(=その先どのグループを選んでも解がなければ)1段階戻って別のグループを選びます。これを全てのパターンについて実行し、答えが見つかれば答えはK、なければKを1増やして再びはじめから実行です。
実際にはグループを選ぶ順序には結果は影響しないので、m人グループのパターンに適当に番号をつけておき、2段目からは1段目より後のパターンだけを探していけば十分です。
Kについて順番に増やしていくのは効率が悪いのでは、と思うところですが、ここが反復深化深さ優先探索のおもしろいところで、解が出る直前より小さいKの探索は、一般に(それより大きいKに比べて)非常に短い時間で終わります。これは上記のように場合の数がKに対してものすごい勢いで増えていくためです。
ここからは枝刈りの方法について。
まず、最も簡単なものとして、残りの深さ(グループの数)がkなのに撮り終えていない人がk*m人より多くいれば、そこから先は解なしです。
また、残りの未接続ペアの数がk*(mC2)より多くても解なしです。
もう少しややこしいものについて。グループの順序を例えばm=3なら(0,1,2),(0,1,3,)…(n-3,n-2,n-1)としておきます。このとき、まだ0番目の人が撮り終えていないのに(1,x,x)を撮り始めたら0は最後まで条件を満たしません。あるいは0番目は撮り終えているのに(0,x,x)を撮るのも無駄ですね。(無駄なメンバーを含む撮影が必要なことはありますが、少し考えるとそれは(n-3,n-2,n-1)の場合のみで大丈夫なことがわかります。)
もっとややこしいものについて。(0,1,2),(0,2,3)と(0,1,2),(0,2,4)は3と4が違うだけで全く同じですね。「(0,1,2)を選んだ時点では4は3と同じだから、3を選ばず4だけ選ぶようなパターンは考えるな」としておけば、かなり削られます。
さらにさらにややこしいものについて。(0,1,2),(0,1,3),(0,4,5)と(0,1,2),(0,3,4),(0,1,5)は3と5が違うだけです。ここまでくると細かい条件分けでは追いつかないので、それらのグループで撮影したことにより結果的にできるつながりのグラフが同型かどうか(番号の変更だけで同じグラフになるかどうか)で判断します。グラフの同型性判定はそれ自体が楽な計算ではないので、比較的よく見つかりそうな探索の上流でのみグラフを全て保存しておき、同型性判定を行います。
上記のグラフの同型性判定はどうやるんだ？というところですが、これもそれぞれの人の対応づけを全パターン試す以外にありません。ただし各人の撮影済み枚数(エッジの数)を見れば対応付けは限られているので、それほど酷い計算量にはならなくなっています。(最悪計算量は人数VについてO(V!)程度だけど、一般にはもっと速い。)どちらかと言うとある深さまでのグラフを全て保存するという操作の空間計算量のほうが気になります。
さて、枝刈りを行った探索は組み合わせ爆発に対してどの程度耐えるのでしょうか。また、結果は前回の貪欲法に対してどの程度改善するでしょうか。
結果は次回、探索の結果編へどうぞ。
(動くコードは手元にありますが、記事の公開がいつになるかは未定です。)