algorithm - 关于理解稳定匹配和不稳定对的任何提示

Question

我以为我理解稳定匹配，但对配对真的很困惑，有人可以帮我简单地理解这一点吗？

Answer 1

让我们快速记住Gale-Shapley算法：

---

• 1. 选择两组中的一组来提出建议。
  • S从 中选择H。

---

• 2. 尚未被选中的提议组中的一名个人H将向他们最喜欢的选项提出建议。
  • 医院

  ---

  • 接受：如果是医院的第一个报价或者S排名高于他们当前的S排名。

    • 例如：如果 Whittington's( W) 的电流是 Ahmed( A) 并且 Laura( L) 建议为W。L替换为À

  • 拒绝： S排名比他们当前的S排名差。

    • 例如：如果 Whittington's( W) 当前是 Ahmed( A) 并且 Elena( E) 建议为W。E被拒绝。
• 3. 当集合的每个成员都匹配时，循环终止。

所以：

---

Laura( L) 选择 Royal Free( R)

Elena( E) 选择 St. Thomas( T)

Ahmad( A) 选择 Whittington( W)

Simon( S) 选择 HighGate( H) ok。

• 如果 Elena( E) 选择 Royal Free( R)，这将创建一个不稳定的对。既然E被接受了。据 ，相比R，E具有更高的等级L。

• 如果 Simon( S) 选择 Whittington( W)，他将被拒绝。由于他的等级是最低的W。

• 如果 Ahmad( A) 选择 St. Thomas( T)，他将被拒绝。的最高等级H是E。

• 如果 Elena( E) 选择 HighGate( H)，她将被拒绝。由于她的等级是最低的H。

---

对于Gale-Shapley 算法

---

对于不稳定对