前回と前々回のエントリーの問題を総当りで
前々回と前回のエントリで書いた問題を、Perlで総当りで解こうとしてみた。使ったコードは最後に添付。
実行開始から7時間半経過したけど未だに終わる気配がない。馬鹿正直に40人の参加希望者と10個の実験枠を組み合わせたら組み合わせは10^40
通り。今回のコードでは、参加可能枠の配列を使って解空間を狭めたけれど、それでもやはり9 * 8 * 9 * 6 * 6 * 5 * 4 * 6 * 7 * 9 * 6 * 8 * 9 * 6 * 7 * 5 * 9 * 4 * 4 * 5 * 3 * 8 * 6 * 8 * 6 * 8 * 7 * 3 * 7 * 9 * 5 * 9 * 5 * 6 * 8 * 7 * 8 * 8 * 7 * 5 = 1.4271125147448316e+32
通りの解がある。もっと解空間を狭めるアルゴリズムを考えるか、確率的なアルゴリズムを考えるしかないようだ。
ちなみに、7時間半走らせたところ、最適解は最大実験枠が4個で最大参加者数が12人になっている。明らかにまだまだ。