「安定結婚問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【あんていけっこんもんだい (stable marriage problem)】''' 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮...') |
|||
| 1行目: | 1行目: | ||
'''【あんていけっこんもんだい (stable marriage problem)】''' | '''【あんていけっこんもんだい (stable marriage problem)】''' | ||
| − | 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 $(m, f)$ に対して, $m$ が $f$ より現在の相手を好むか, または $f$ が $m$ より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, | + | 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 $(m, f)$ に対して, $m$ が $f$ より現在の相手を好むか, または $f$ が $m$ より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる. |
2007年7月9日 (月) 14:43時点における版
【あんていけっこんもんだい (stable marriage problem)】
同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 $(m, f)$ に対して, $m$ が $f$ より現在の相手を好むか, または $f$ が $m$ より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる.