算法导论25.3 Exercises 答案

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

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\)。