算法导论25.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

25.3-1

修改后的代码由FIND-AUGMENTING-PATH'给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
FIND-AUGMENTING-PATH'(GM, h)
  Q = Ø
  FL = Ø
  FR = Ø
  for each unmatched vertex l ∈ L
    l.π = NIL
    ENQUEUE(Q, l)
    FL = FL ∪ {l}   // forest F starts with unmatched vertices in L
  repeat
    if Q is empty   // ran out of vertices to search from?
      δ = min { l.h + r.h − w(l, r) : l ∈ FL and r ∈ R − FR }
      for each vertex l ∈ FL
        l.h = l.h − δ   // relabel according to equation
      for each vertex r ∈ FR
        r.h = r.h + δ   // relabel according to equation
      from G, M, and h, form a new directed equality graph GM,h
      FL = Ø
      FR = Ø
      for each unmatched vertex l ∈ L
        l.π = NIL
        ENQUEUE(Q, l)
        FL = FL ∪ {l}
    u = DEQUEUE(Q)                          // search from u
    for each neighbor v of u in GM,h
      if v ∈ L
        v.π = u                             
        FL = FL ∪ {v}                       // discover v, add it to F
        ENQUEUE(Q, v)                       // can search from v later
      else if v ∉ FR                        // v ∈ R, do same as lines 18–22
        v.π = u
        if v is unmatched
          an M-augmenting path has been found (exit the repeat loop)
        else 
          ENQUEUE(Q, v)
          FR = FR ∪ {v}
  until an M-augmenting path has been found
  using the predecessor attributes π, construct an M-augmenting path P by tracing back from the unmatched vertex in R
  return P

缺点在于，每次对相等子图$G_h$更新后，都需要重新对整个图重新进行BFS，而原来的算法FIND-AUGMENTING-PATH只需要按照原来的搜索结果继续往下搜索即可。不过，FIND-AUGMENTING-PATH'的这个改动并没有对渐进时间复杂度$O(n^4)$变坏。

25.3-2

对于任意二分图$G$，考虑其中一个最大匹配$M$。在$M$看来，算法GREEDY-BIPARTITE-MATCHING相当于将选择任意$G$中选择任意一条边$(l,r)$加入候选答案$M’$，并且在此之前$l,r$未曾出现在$M’$中。每次加入一条边进$M’$后，$M$至多有两条边不再可能添加到$M’$中（其中一条包含$l$，另一条包含$r$）。因此，贪心算法GREEDY-BIPARTITE-MATCHING至少可以迭代$\lfloor M/2\rfloor$轮。如果$|M|$是偶数，那么证明完成。如果$M$是奇数，那么迭代$\lfloor M/2\rfloor$轮后，$M$中必定会存在一条边$e$，使得$e$中两个节点尚未出现在$M’$中。也就是说，$G$中仍然必定存在一条边能够加入$M’$中。因此，最终无论如何都有$|M’| \ge |M|/2$，原结论成立。

25.3-3

按照引理25.15，可以知道$l.h+r.h\ge w(l,r),l.h’+r.h’\ge w(l,r)$。

由于$(l,r)\in G{M,h}$，因此有$l.h+r.h=w(l,r)$；由于$(l,r)\not\in G{M,h’}$，那么有$l.h’+r.h’>w(l,r)$。

按照方程25.5对属性$h’$的定义，可知左部节点$l$的$h$属性非递增，有部节点$r$的$h$属性非递减。由于$l.h+r.h=w(l,r)$的下一步就得出了$l.h’+r.h’>w(l,r)$，因此只能有$l.h’=l.h,r.h’=r.h+\delta$，因此按照方程25.5，有$l\in L-F_L,r\in F_R$。

25.3-4

当一个左部节点$l$被访问时，它只有两种情况：如果$l$是尚未被匹配的节点，按照$G{M,h}$的图构造，$l$必定是BFS森林$F$的某一个根，即某个起点。如果$l$是已经被匹配所覆盖的节点，那么必定存在一个右部节点$r$，并且$(r,l)\in E{M,h}$，再从$r$节点访问$l$节点，由于$M$中的边都是不相交的，因此节点$l$在$G_{M,h}$中只有唯一一条入边。因此，$\forall l\in L$，节点$l$只会被访问一次，因此不需要判断是否重新发现。

25.3-5

图$G_{M,h}$不需要显示构造出来，只需要用两个长度为$n$的一维数组标记好$h$值即可。事实上，接下来的操作可以视为是在图的邻接矩阵上进行操作。这个算法由HUNGARIAN''给出。同样的，它的时间复杂度和HUNGARIAN一样，为$O(n^4)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//左部节点用整数1~n来表示，右部节点用n+1~2n来表示，并且函数w(i,j)的定义域是1<=i<=n<j<=2n
HUNGARIAN''(w, n)
  let h[1 : n + n] be new arrays
  for i = 1 to n + n
    if i <= n
      h[i] = max{w(i, j) : n + 1 <= j <= n + n}
    else
      h[i] = 0
  // match[j]表示右部节点j将要匹配的左部节点，如果为0，表示暂时还没有左部节点与之匹配
  let match[1 : n] be any matching in Gh (such as the matching returned by GREEDY-BIPARTITE-MATCHING)
  while match still contain element 0
    P = FIND-AUGMENTING-PATH''(w, n, h, match)
    m = P.size
    for i = 2 to m by 2
      // P[i]一定是右部节点  
      match[P[i]] = P[i - 1]
  return match

FIND-AUGMENTING-PATH''(w, n, h, match)
  Q = Ø
  FL = Ø
  FR = Ø
  for each unmatched vertex l ∈ L
    l.π = NIL
    ENQUEUE(Q, l)
    FL = FL ∪ {l}
  repeat
    if Q is empty
      δ = min { h[l] + h[r] − w(l, r) : l ∈ FL and r ∈ R − FR }
      for each vertex l ∈ FL
        h[l] = h[l] − δ
      for each vertex r ∈ FR
        h[r] = h[r] + δ
      for each vertex l ∈ FL
        for each vertex r ∈ R - FR
          if h[l] + h[r] == w(l, r)
            r.π = l
            if match[r] == 0
              // 代表r仍然未被匹配
              an M-augmenting path has been found (exit the repeat loop)
          else 
            ENQUEUE(Q, r)
            FR = FR ∪ {r}
    u = DEQUEUE(Q)
    if 1 <= u <= n
      // 这时u是左部节点
      for r = n + 1 to n + n
        if h[u] + h[r] == w(u, r) and r ∉ FR 
          r.π = u
          if match[r] == 0
            an M-augmenting path has been found (exit the repeat loop)
          else
            ENQUEUE(Q, r)
            FR = FR ∪ {r}
    else
      // 这时u是右部节点
      l = match[u]
      l.π = u
      FL = FL ∪ {l}
      ENQUEUE(Q, l)
  until an M-augmenting path has been found
  using the predecessor attributes π, construct an M-augmenting path P by tracing back from the unmatched vertex in R
  return P

25.3-6

只需要将所有边权全部取负，得到新边权函数$w’$，再使用$w’$运行原本的匈牙利算法即可。最终所求得的匹配$M$就是最小匹配。

25.3-7

不失一般性，假设$|L|<|R|$，那么为$L$补充$|R|-|L|$个虚拟节点，集合为$L’$，并且将它们对$R$中的所有节点连向所有边，且权值为$0$，最终得到新图$G’$。更正式的说，$G’=(V’,E’),V’=L’\cup L\cup R,\forall l’\in L’,r\in R,w(l,r)=0$。

接下来对新图$G’$运行匈牙利算法得到最大匹配$M’$，对于$R$中的所有节点$r$，如果$r$在$M’$中连向了虚拟结点$L’$，那么$r$在原最大匹配中是孤立节点。最终，从$M’$去掉这些虚拟节点所关联的边那么就得到原图的最大匹配$M$。