5/23 めっちゃSSを書いた
今日の進捗は凄まじいです。震えて眠れ。
さばです。
めちゃくちゃ文字を書きました。最初は自室で書いていたんですが、昼食がてらスタバに行って、帰ってきてオークスで負けて、またSSを書いて。
我ながら、完璧な一日を過ごしてしまいました。
やっぱり休日はこうあるべきなんですよ。昼過ぎなんかに起きてないで、早いこと目を覚まして朝日を浴びながらSSを書くに限るんです。詰まったら筋トレとか散歩とかしてリフレッシュしたりして。
今日はスタバに行ったのがよかったです。そこで、僕の同級生同士が先日結婚したことも同時に思い出しました。めちゃくちゃおめでたい……二人と同じ塾に通っていたので、当時の塾長が知ったら驚きそうです。
残念ながら僕は結婚ができないんですが、世の中には任意の数の男女から最も安定したカプの組み合わせを求める問題が存在します。
それが、「安定結婚問題」です。カプ厨気味なので、名前からしてワクワクしちゃう………
これを求めるために必要なのが、複数の男女(合コンをイメージすると分かりやすいです)と、各人の異性にたいする好感度のランキングです。ここで不穏な補足なんですが、男女の数は同数じゃなくても大丈夫です。また、男女を完全に区別して考えるため、残念ながら同性に対する嗜好は考慮されません。
例えば、男性A、B、Cと女性1、2、3 がいるとします。Aは2、1、3の順、Bは1、3、2の順、 Cは……という風に、男性三人がそれぞれ女性三人に対しての好感度をランク付けしていきます。同様に、女性も男性三人をランク付けしていくと、次のような表が出来上がります。
名前 | 一位 二位 三位
A | 2 1 3
B | 1 3 2
C | 2 3 1
1 | A B C
2 | A C B
3 | C B A
これを元に、最も安定なペア(なるべく全員の希望通りになるようなペア)を求める問題が、安定結婚問題と呼ばれています。
今回の場合だと、
A ─ 2
B ─ 1
C ─ 3
の組み合わせが安定となります。この安定した組み合わせ(駆け落ちペアが存在しない組み合わせ)のことを、安定マッチングといいます。逆に「駆け落ちペア」が一つでも存在すればそれは不安定であり、これを不安定マッチングと呼びます。駆け落ちペアとは、「お互いとマッチしていない男女のペアで、現在マッチしている相手よりもお互いの方が好きなペア」を指します。言葉で説明するのがすごく難しいのでご容赦ください。
語弊がありますが、第一希望と結ばれなくても第二希望で結ばれればまあ良いよね、みたいな感じです。
今回は第三希望の相手と結ばれることがないように好感度ランキングを設定しましたが、悲しいかな、場合によってはそういうこともありえますし、何なら相手ができない人が出てくることもあります。大事なのは、「必ずしも参加者全員が誰かしらとマッチする必要はない」ということです。
例えば3対3だったとしても二組しか安定して成立しない場合だってあります。前述のとおり、男女の数は同じじゃなくてもいいので、一人だけ溢れてしまうことだってもちろんあります。無情ですが機械に心はないので、そういったマッチングでも駆け落ちペアさえいなければ安定だとされます。
この安定結婚問題を解くアルゴリズムとして、Gale-Shapleyアルゴリズムが知られています。
さらに、安定結婚問題には「絶望の定理」という、厨二っぽい名前の定理があります。
これは「ある安定マッチングでペアを作れなかった人間は、いかなる安定マッチングにおいてもペアを作ることができない」という定理です。簡単に言うと、一つの安定マッチングに入れなかった人はどう頑張っても相手は作れませんよ〜という、まさに絶望の定理です。
安定結婚問題を考えれば誰が来てもお似合いのカップルが作れる!と思いきや、そう上手くいかないのが現実って感じがしますね。
カプ厨気味なので名前を初めて聞いた時はワクワクが止まりませんでしたが、実際に勉強してみると「なんだこの残酷な問題……」という風になったので、カプ厨気味の方はご注意ください。
最後に今日の圧倒的進捗を投げます。
もう、本当に圧倒的なんだから。
○彰杏・冬こは 18117文字(+6340字)
○風いつ 26文字(±0)
○書きかけ 60個(±0)
そうでもねぇな…………ありがとうございました……………
この記事が気に入ったらサポートをしてみませんか?