安定結婚問題 - Wikipedia

安定結婚問題（あんていけっこんもんだい、英: stable marriage problem）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。 安定結婚問題は n 人の男性と k 人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（英: individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable ma

[Gesaku_G]

・・・さっぱりわかりません

[TOKOROTEN]

対戦のマッチングロジックに使えるかなー。

[matsuokahajime]

このアルゴリズムの説明が新聞記事だと条件が抜けていて終了しないものだった。 ハンガリアンアルゴリズムしか知らなかった立場で言うのは気が引けるが、 最適解を返すアルゴリズムを待ってからで良かった気がする。

[dayafterneet]

ほう・・・

[hiromark]

安定結婚問題のモデルと安定マッチングを見つけるO(N^2)時間アルゴリズム。