算法导论25.2 Exercises 答案

发表于 2023-07-01 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 3.5k 阅读时长 ≈ 3 分钟

25.2-1

用一个单向链表\(L_f\)用于存储所有处于自由状态的女人。用二维数组\(rkl[i,j]\)用来表示女人\(i\)的第\(j\)个排名的男人。用二维数组\(rkr[i,j]\)表示男人\(i\)的第\(j\)个排名的女人。维护一个数组\(pos\)，表示女人的求婚过程。具体过程将由GALE-SHAPLEY'给出，其时间复杂度为\(O(n^2)\)，其中\(match[i]\)表示和男人\(i\)结婚的女人。

// 使用数字1~n表示每个男人和女人
GALE-SHAPLEY'(n, rkl, rkr)
  Let node[1 : n], pos[1 : n], match[1 : n] be new arrays
  // pos-rank[i, j]表示男人i为女人j所给出的排名
  Let pos-rank[1 : n, 1 : n] be a new table
  // 每个链表节点都有一个数据属性id，表示女人编号。
  Let L be a new link list
  for i = 1 to n
    let node[i] be a new node
    node[i].id = i
    INSERT-LIST(L, node[i])
    // 用-1表示男人处于未婚状态
    match[i] = -1
    // 一开始女人都是从头开始求婚
    pos[i] = 1
    for j = 1 to n
      pos-rank[i, rkr[i, j]] = j 
  // 仍然有女人处于自由状态
  while L.size > 0
    // 女人的编号。
    w = L.head.id
    DELETE-LIST(L, L.head)
    m = rkl[w, pos[w]]
    pos[w] = pos[w] + 1
    if match[m] == -1
      match[m] = w
    else
      if pos-rank[i, w] < pos-rank[i, match[m]]
        // 说明现在的女人排名更高
        INSERT(L, node[match[m]])
        match[m] = w
      else
        INSERT(L, node[w])
  return match

25.2-2

两个男人和两个女人之间存在不稳定匹配，考虑如下两个女人Wanda, Emma和两个男人Oscar, Davis。这些女人和男人对异性的排名如下：

Wanda: Oscar, Davis
Emma: Davis, Oscar
Oscar: Wanda, Emma
Davis: Emma, Wanda

那么当前的不稳定匹配如下：

Wanda and Davis
Emma and Oscar

由于WanDa比起Davis，更喜欢Oscar，并且Oscar比起Emma，更喜欢Wanda，因此WanDa and Oscar是一个阻塞对，这不是稳定匹配。类似的，Emma比起Oscar，更喜欢Davis，并且Davis比起Wanda，更喜欢Emma，因此Emma and Davis也是一个阻塞对这同样说明这个匹配不是完美匹配。

25.2-3

我们考虑这个过程是以学生为导向的（这很合理，因为通常都是学生报考学校，然后学校对学生进行评估，再反馈结果）。考虑一共有\(m\)个医院，\(n\)个学生，且\(n\ge m\)。

每间医院都会对每个学生进行排名。每个学生都会对每间医院进行排名。每个学生都有两个状态：自由和已录取。

一开始，每间医院\(h\)的\(h_c\)个名额都处于自由状态，并且每个学生也是出于自由状态。接下来每轮迭代中，每个处于自由的学生\(s\)将按照它们对医院从高到低的排名，向尚未提交过申请的医院\(h\)提交申请。如果\(h\)名额仍未招满，那么\(h\)将会录取\(s\)，并且\(s\)变成已录取状态；否则，\(h\)按照其内部排名，找出当前最差的录取生\(s'\)，和\(s\)进行比较。如果\(s'\)比\(s\)在\(h\)中的排名更好，那么拒绝\(s\)，否则取消\(s'\)并录取\(s\)，同时\(s'\)变成自由状态，\(s\)变成录取状态。

更具体的过程由GALE-SHAPLEY''给出，\(rkl\)是每个学生对每间医院的排名，\(rkr\)是每间医院对每个学生的排名。由于使用了最大堆来维护每个医院的最差学生，因此其时间复杂度为\(O(nm\lg n)\)，其它细节和题目25.2-1一致。

// 使用数字1~n表示每个学生，使用数字1~m表示每间医院
GALE-SHAPLEY''(n, m, rkl, rkr, hc)
  Let node[1 : n], pos[1 : m], match[1 : m] be new arrays
  // pos-rank[i, j]表示医院i为学生j所给出的排名
  Let pos-rank[1 : m, 1 : n] be a new table
  Let L be a new link list
  for i = 1 to n
    // 每个链表/堆节点都有两个数据属性key和id，其中key是表示排序关键字（也就是当前学生在医院h的排名），id表示学生编号
    let node[i] be a new node
    node[i].id = i
    INSERT-LIST(L, node[i])
    // 一开始学生都是从头开始进行申请
    pos[i] = 1
  for i = 1 to m
    for j = 1 to n
      pos-rank[i, rkr[i, j]] = j
    Let match[i][1 : hc[i]] be a new array

  // 仍然有学生处于自由状态
  while L.size > 0
    // 学生的编号
    s = L.head.id
    DELETE-LIST(L, L.head)
    h = rkl[w, pos[w]]
    pos[w] = pos[w] + 1
    if match[h].size < hc[h]
      node[s].key = pos-rank[h, s]
      MAX-HEAP-INSERT(match[h], node[s], hc[h])
    else
      // x是match[h]中最差的学生
      x = MAX-HEAP-MAXIMUM(match[h]).id
      if pos-rank[h, s] < pos-rank[h, x]
        MAX-HEAP-EXTRACT-MAX(match[h])
        INSERT(L, node[x])
        node[s].key = pos-rank[h, s]
        MAX-HEAP-INSERT(match[h], node[s], hc[h])
      else
        INSERT(L, node[s])
        // 如果s比h中录取的学生都要差，那么把s插回L中。
  return match

25.2-4

本题的证明将参考论文。

令女人的集合为\(X\)，男人的集合为\(Y\)。那么有\(|X|=|Y|=n\)。令\(M\)表示从GALE-SHAPLEY算法得到的面向女人得到的最优稳定匹配，令\(\mu_M(x)\)表示某组匹配\(M\)中\(x\)的配偶。在某组匹配\(M\)中，定义女人\(w\)爱慕男人\(m\)如下：\(w\)比起她的配偶\(\mu_M(w)\)，更喜欢男人\(m\)。也就是说，如果某个匹配\(M\)中，两个人\(w,m\)相互爱慕，那么\((w,m)\)成为一个阻塞对。

使用反证法证明，假设存在这样一个匹配\(M'\)，使得每一个女人\(w\in X\)，比起匹配\(M\)中的配偶\(\mu_m(w)\)，更喜欢匹配\(M'\)中的配偶\(\mu_{M'}(w)\)。最终证明这样的\(M'\)并不存在。接下来先证明一个引理。

首先证明引理：令\(f\)和\(g\)是一个从有限集\(X\)到有限集\(Y\)的函数，并且\(f\)是双射的。那么存在一个非空子集\(A\subseteq X\)使得\(f\)和\(g\)是从有限集\(A\)到有限集\(f(A):\{f(x)\mid x\in A\}\)的双射函数。

证明：令\(h=f^{-1}\circ g\)，那么函数\(h\)将从\(X\)映射回\(X\)。可见，\(h^0(X)=X\)，由于\(g\)不一定是满射的，因此\(h(X)\subseteq X\)。也就是说，\(\forall n\ge 0\)，都有\(h^{n+1}(X)\subseteq h^n(X)\)，那么必定存在\(k\)使得\(h^{k+1}(X)=h^k(X)\)，令集合\(A=h^k(X)\)，那么集合\(X\)为所求。

接下来声称：在面向女人的最优匹配\(M\)中，存在一个男人\(m\in Y\)，没有女人爱慕他。使用反正法证明，假设对于所有男人\(m\)，都有女人爱慕她。那么令\(\alpha_{M}(m)\)表示对于某个匹配\(M\)，男人\(m\)的所有爱慕者中，\(m\)最喜欢的那个女人。根据上面的引理，存在一个男人的非空子集\(\hat{Y}\subseteq Y\)使得\(\mu_M(\hat{Y})=\alpha_M(Y)\)。现在定义匹配\(\hat{M}\)是只包含了男人\(\hat{Y}\)和女人\(\mu_M(\hat{Y})\)，并且匹配函数\(\mu_{\hat{M}}\)是一个从有限集\(\hat{Y}\)到有限集\(\mu_{M}(\hat{Y})\)的函数。可以证明，\(\hat{M}\)是一个稳定匹配。因为如果\(\hat{M}\)中存在一个阻塞对\((w,m)\)，那么\(m\in \hat{Y}\)，并且女人\(w\)爱慕他，但是\(m\)在\(\hat{M}\)中已经和他最喜欢且爱慕他的人\(\alpha_M(m)\)进行匹配（不爱慕\(m\)的女人根本不会作为出现在\(\alpha_M(m)\)的候选中），和\(m\)最爱慕\(\alpha_M(m)\)矛盾（在于这里认为男人\(m\)比起\(\alpha_M(m)\)，更喜欢\(w\)）。因此这样的阻塞对不存在。

但是对于所有女人\(w\in\mu_M(\hat{Y})\)，\(w\)更喜欢在匹配\(M'\)中的配偶\(\mu_{\hat{M}}(w)\)，而不是原本匹配\(M\)中的配偶\(\mu_M(w)\)。这与稳定匹配\(M\)中的配偶是\(w\)的最优配偶矛盾。因此原来的声称成立，必定存在一个男人\(m\)没有爱慕他的女人。

接下来证明稳定匹配问题的弱帕累托最优性。假设存在一个匹配\(M'\)，使得其中每一个女人的配偶都比\(M\)中的更优，那么说明在匹配\(M\)中，每一个男人都必定存在爱慕他的女人，这和上面的声称是矛盾的。因此题目中的结论成立。

25.2-5

本题的图和原本的题目的区别在于，这时的评价图是一个完全图，而不是一个完全二分图。

假设目前有如下\(4\)个人Brent, Davis, Hank, Oscar，他们对其他\(3\)人的排名如下：

Brent: Davis, Hank, Oscar
Davis: Hank, Brent, Oscar
Hank: Brent, Davis, Oscar
Oscar: Brent, Davis, Hank

那么可以发现，一共有\(3\)组不同的匹配，并且可以说明这\(3\)组不同的匹配都不是稳定的。

考虑如下匹配：

Brent and Davis
Hank and Oscar

可见，Davis比起Brent，更喜欢Hank，而Hank比起Oscar，更喜欢Davis，因此Davis and Hank是一个阻塞对，这不是一个稳定的匹配。

考虑如下匹配：

Brent and Hank
Davis and Oscar

可见，Brent比起Hank，更喜欢Davis，而Davis比起Oscar，更喜欢Brent，因此Brent and Davis是一个阻塞对，这不是一个稳定的匹配。

考虑如下匹配：

Brent and Oscar
Davis and Hank

可见，Brent比起Oscar，更喜欢Hank，而Hank比起Davis，更喜欢Brent，因此Brent and Hank是一个阻塞对，这不是一个稳定的匹配。

这说明上面给出的示例无法产生一个稳定的匹配。产生这种现象的原因如下：

令\(P\)表示这些人的集合，其中一个人\(z\)在其他所有人排名都是在最后，但是对于一个匹配\(M\)而言，必定存在一个人\(x\)和\(z\)进行匹配。对于其他人\(P=\{x,z\}\)，只要至少\(|P|-2\)个人（设其为\(y\)）对\(x\)的排名不是倒数第二名，那么\((x,y)\)就成为了阻塞对。