カップルの作り方

先日、昼飯にファミレスに入ったら、昼間からパーティールックで決めた男女計10人くらいが、端の席で大声で何か議論をしてました。声がでかいので否応なく聞こえてしまったところによると、どうやらカップリングパーティーの主催者のグループのようです。男性の第1希望と女性の第3希望がマッチした場合と、男性と女性の第2希望同士がマッチした場合を、どちらを優先するかでもめてました。

確かに、大切な問題です。それによって、もしかしたら運命のボタンをかけ違えられてしまう人がいるかもしれません。

でも、僕ら理系人間にとって、このシチュエーションは残念ながら「組み合わせ最適化」と呼ばれる分野の教科書問題にしか見えません。

-----

仮に、20人ずつの男女がカップリングパーティーに参加したとします。全てのカップルの組み合わせは20の階乗通りあるので、2*10^18通り以上の組み合わせが存在します。

まず、出来上がったカップルの満足度を得点に換算します。たとえば第1希望同士のカップルは10点。第2希望同士だったら5点。みたいに。この場合、20組のカップルが全部第1希望同士だったら、その組み合わせの得点は合計で200点ということになります。

この合計点を全ての組み合わせに対して調べて、最も得点の高い組み合わせを求めれば、参加者全員の満足度を最高にすることが出来ます。
2*10^18通り程度であれば、現代のコンピュータはそれほど苦もなく調べ上げられるかもしれません。しかし、この計算は、参加者が1人増えるごとにものすごい勢いで難しくなり、あっという間に年単位の計算時間がかかるようになります。

そこで、組み合わせ最適化手法の出番です。この手法を使うと、全ての組み合わせを調べるよりはるかに少ない時間で、"ほぼ"最高の答えを得ることができます。その代表的な手法の一つが、遺伝的アルゴリズム(GA)と呼ばれる手法です。

GAは、カップルの出来方を生物の遺伝子に見立てて、それをコンピュータの中で仮想的に交配、淘汰させることによって、満足度の高い組み合わせだけを選び出します。詳細はググってみてください。

-----

プログラムが必要なら安く請け負うよ、と、ニヤニヤしながら昼飯をつついたのでした。

Published by

そうへい

都内の某ベンチャーでWebまわりの開発してます。趣味でドラムとパーカッション叩いてます。スノボ、キャンプ、登山、秘湯めぐり等、アウトドア全般イケます。LiverpoolFCのファンです。