ゲール=シャプレーアルゴリズム~最強のまとめ役2
それでは、先ほどの合コンの例でゲール=シャプレーアルゴリズムを具体的にやってみよう。
◆ステップ1
男性が一番好きな人に告白。女性はその中で一番好きな人をキープ!
![85](./images/85.png)
上の赤い矢印が告白、赤い丸がキープである。ここではのびただけが拒否されたことになる。
◆ステップ2
拒否された男性(のびた)は次に好きな女性に告白。告白された女性は、一番好きな人をキープ!
![86](./images/86.png)
沙織は、キープしていた星矢よりも好きなのびたから告白されたのでそちらをキープ。ここでは、星矢が拒否されたことになる。
◆ステップ3
拒否された人(星矢)は次に好きな人に告白。告白された女性は、一番好きな人をキープ!
![87](./images/87.png)
しずかは、キープしていたカツオよりも好きな星矢から告白されたのでそちらをキープ。カツオが拒否される。
◆ステップ4
拒否された人(カツオ)は次に好きな人に告白。告白された女性は、一番好きな人をキープ!
![88](./images/88.png)
3組が完成したので終了だ。
結果は次のようになった。
![84](./images/84.png)
これは、先ほど見たコアの結果と同じだ。誰も駆け落ちしない、望ましい結果となっている。
このゲール=シャプレーアルゴリズムは、仕組みはいたって単純だ。しかし、男と女が何人いようが、良い結果を教えてくれる。もちろん、特定の誰か以外には付き合いたくないという人(第2希望や第3希望がない人)や、ここにいる全員がイヤだという人がいても問題なく、コアを導いてくれる。
すべての組み合わせを考え、それぞれの場合で「これの場合では駆け落ちできるからダメだ…」と探していくよりも効率的なのは間違いない。