什麼是穩定匹配？

Question

所以我的問題是指什麼是「穩定匹配」？我意識到穩定婚姻問題，並且所有解決方案似乎都表明您完成了「穩定匹配」。但我不確定這實際上是什麼意思。

Answer 1

我會盯着wiki上的.gif，因爲它實際上是對機制的一個很好的解釋。

在穩定的匹配，我們保證在兩盤（男&女人，孩子&玩具，人&度假目的地，等等）都放在一對與一個元件與另一組，並且對是「最好的所有元素可用匹配「

我們確定什麼是」最佳可用匹配「的方式是想象一個集合中的每個元素已經將它們的偏好排列在相反集合的元素上。目標是滿足每個人的喜好。堅持婚姻問題，想象每個男人都有一個排名的女人名單，每個女人都有一個排名的男人名單。我們的目標是將他們匹配在一起，確保每個人都能獲得他們名單上的最高人選。

請記住，這需要幾個步驟（或輪次）才能實現。在婚姻的例子中，要記住的另一件事是每一方只能做一件事。所以在我們的例子中，女性接受，男性提出。此外，該提案不具約束力。這意味着，如果在第一輪中，女人從她最喜歡的2號球員那裏得到一個提議，並且在下一輪她從她的＃1男子那裏得到一個提議，她可以拒絕＃2並且拿到＃1。維基百科表示，它比我更好...

算法完成後，愛麗絲和鮑勃都不可能在他們當前的合作伙伴上互相優先。如果鮑勃偏愛愛麗絲到現在的伴侶，他必須在向愛麗絲提出現在的伴侶之前提出建議。如果愛麗絲接受了他的提議，但最終還沒有與他結婚，她肯定會把他拋棄給她喜歡的人，因此她不喜歡鮑勃而不是她現在的伴侶。如果愛麗絲拒絕了他的提議，她已經和她比她更喜歡的人在一起了。

基本上，沒有人得到在婚姻shadge，因爲這對是有限的選擇對另一個最高的偏好。