算法导论25.2 Exercises 答案

发表于 2023-07-01 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 3.2k 阅读时长 ≈ 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$中的配偶$\mum(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\muM(\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)$就成为了阻塞对。