最適化と組み合わせ爆発

強いチームを作りたいなら、 いい選手を集めるのはもちろん、 勝てる組み合わせにすることが必要です。 できることなら、誰と誰を組み合わせて どう配置するかといった可能性を、 あらゆる状況で 試してみたいと考えることもあるでしょう。 ビーチバレーのように、 ごく少人数のチーム編成で 戦うスポーツなら、総当たり式に 試すことも不可能ではありません。 例えば、全部で４人の選手がいるなら、 そのうち２人を選んで いずれかのポジションに配置する という組み合わせを すべて試すことになるでしょう。 さて、今の例の公式はこのようになります。 n（エヌ）は選ぶことができる 選手の総数で、４です。 r（アール）はそこから１度に 選び出す選手の数で、２です。 計算すると、12 通りの 配置があるとわかります。 この程度なら、全部を試してみて、 納得できる配置を 決められるかもしれません。 では、これより人数が 多い競技ではどうでしょうか。 例えばバスケットボールのチームです。 コートで戦える選手の数は５人です。 全米プロリーグの NBA（エヌビーエー）に 登録できる選手数は１チーム 15 人です。 つまりこの例では、先ほど示した式の n に 15、r に５が入ることになります。 ５人の選手をランダムに選び出して、 全部のポジションに配置して連係を試す場合、 この式になります。 計算すると、 なんと全部で 36 万 360 通りもの 可能性があることがわかります。 すべて試すには、 途方もなく長い時間がかかります。 さらに上には上があります。 野球で考えてみましょう。 例えば、25 人の選手がいて、 その中から９人を選んであらゆる ポジションに配置するパターンを 考えてみます。 この問題を議論しているのを 私が最初に耳にしたのも、 野球の話からでした。 数字はあっという間に 手に負えなくなります。 順列の公式の n に 25 を、 r に９を入れて計算すると、 考えられる選手の配置は、 7,413 億通りを超えることがわかります。 これを１つずつ試そうとするなら、 宇宙の誕生時から これまでの時間に匹敵するか、 それ以上の時間が かかってしまうかもしれません。 最適解を見つけたいのは山々でも、 すべての可能性をランダムに 試していくのは無理なのです。 これを、組み合わせ爆発といいます。…