安定結婚問題
読み方：あんていけっこんもんだい
【英】：stable marriage problem
【英】：stable marriage problem
同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 
に対して, 
が 
より現在の相手を好むか, または が より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる.
「OR事典」の他の用語
| グラフ･ネットワーク： | 基本分割 多品種フロー 多項式時間アルゴリズム 安定結婚問題 完全グラフ 局所点連結度 局所辺連結度 |
- あんていけっこんもんだいのページへのリンク
