「安定結婚問題」の版間の差分
ナビゲーションに移動
検索に移動
細 ("安定結婚問題" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 <math>(m, f) \,</math> に対して, <math>m \,</math> が <math>f \,</math> より現在の相手を好むか, または <math>f \,</math> が <math>m \,</math> より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる. | 同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 <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)】
同数の男性と女性が存在し, それぞれが異性に対して選好順序をもつと仮定する. 男女間の完全マッチングが与えられたとき, それが安定であるとは, マッチングに含まれない男性と女性の任意の対 に対して, が より現在の相手を好むか, または が より現在の相手を好むという性質が成り立つことである. 安定な完全マッチングを求める問題を安定結婚問題と呼ぶ. そのような解は常に存在し, ゲイル・シャプレーの解法により多項式時間で求められる.
