安定結婚問題

OR事典

安定結婚問題

読み方：あんていけっこんもんだい
【英】：stable marriage problem

同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 に対して, が より現在の相手を好むか, または が より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる.

「OR事典」の他の用語

グラフ･ネットワーク：

基本分割  多品種フロー  多項式時間アルゴリズム  安定結婚問題  完全グラフ  局所点連結度  局所辺連結度

ウィキペディア

安定結婚問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/03/12 04:50 UTC 版)

安定結婚問題（あんていけっこんもんだい、英: stable marriage problem）とはデイヴィッド・ゲールと ロイド・シャプレイによって1962年に提示された問題である。