「安定結婚問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【あんていけっこんもんだい (stable marriage problem)】''' 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (3人の利用者による、間の3版が非表示) | |||
| 1行目: | 1行目: | ||
'''【あんていけっこんもんだい (stable marriage problem)】''' | '''【あんていけっこんもんだい (stable marriage problem)】''' | ||
| − | 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 | + | 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 <math>(m, f) \,</math> に対して, <math>m \,</math> が <math>f \,</math> より現在の相手を好むか, または <math>f \,</math> が <math>m \,</math> より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる. |
| + | |||
| + | [[Category:グラフ･ネットワーク|あんていけっこんもんだい]] | ||
2008年11月6日 (木) 13:17時点における最新版
【あんていけっこんもんだい (stable marriage problem)】
同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 に対して, が より現在の相手を好むか, または が より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる.
