算法导论23.1 Exercises 答案

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

23.1-1

运行SLOW-APSP的每步迭代结果：

\(\begin{aligned} &\begin{pmatrix} 0&\infty&\infty&\infty&-1&\infty\\ 1&0&\infty&2&\infty&\infty\\ \infty&2&0&\infty&\infty&-8\\ -4&\infty&\infty&0&3&\infty\\ \infty&7&\infty&\infty&0&\infty\\ \infty&5&10&\infty&\infty&0 \end{pmatrix} \underrightarrow{m=2} \begin{pmatrix} 0&6&\infty&\infty&-1&\infty\\ -2&0&\infty&2&0&\infty\\ 3&-3&0&4&\infty&-8\\ -4&10&\infty&0&-5&\infty\\ 8&7&\infty&9&0&\infty\\ 6&5&10&7&\infty&0 \end{pmatrix} \underrightarrow{m=3} \begin{pmatrix} 0&6&\infty&8&-1&\infty\\ -2&0&\infty&2&-3&\infty\\ -2&-3&0&-1&2&-8\\ -4&2&\infty&0&-5&\infty\\ 5&7&\infty&9&0&\infty\\ 3&5&10&7&5&0 \end{pmatrix}\\ \underrightarrow{m=4} &\begin{pmatrix} 0&6&\infty&8&-1&\infty\\ -2&0&\infty&2&-3&\infty\\ -2&-3&0&-1&2&-8\\ -4&2&\infty&0&-5&\infty\\ 5&7&\infty&9&0&\infty\\ 3&5&10&7&5&0 \end{pmatrix} \underrightarrow{m=5} \begin{pmatrix} 0&6&\infty&8&-1&\infty\\ -2&0&\infty&2&-3&\infty\\ -5&-3&0&-1&-6&-8\\ -4&2&\infty&0&-5&\infty\\ 5&7&\infty&9&0&\infty\\ 3&5&10&7&2&0 \end{pmatrix}\\ \end{aligned}\)

运行FAST-APSP的每步迭代结果：

\(\begin{aligned} &\begin{pmatrix} 0&\infty&\infty&\infty&-1&\infty\\ 1&0&\infty&2&\infty&\infty\\ \infty&2&0&\infty&\infty&-8\\ -4&\infty&\infty&0&3&\infty\\ \infty&7&\infty&\infty&0&\infty\\ \infty&5&10&\infty&\infty&0 \end{pmatrix} \underrightarrow{m=2} \begin{pmatrix} 0&6&\infty&\infty&-1&\infty\\ -2&0&\infty&2&0&\infty\\ 3&-3&0&4&\infty&-8\\ -4&10&\infty&0&-5&\infty\\ 8&7&\infty&9&0&\infty\\ 6&5&10&7&\infty&0 \end{pmatrix} \underrightarrow{m=4} \begin{pmatrix} 0&6&\infty&8&-1&\infty\\ -2&0&\infty&2&-3&\infty\\ -2&-3&0&-1&2&-8\\ -4&2&\infty&0&-5&\infty\\ 5&7&\infty&9&0&\infty\\ 3&5&10&7&5&0 \end{pmatrix}\\ \underrightarrow{m=8} &\begin{pmatrix} 0&6&\infty&8&-1&\infty\\ -2&0&\infty&2&-3&\infty\\ -5&-3&0&-1&-6&-8\\ -4&2&\infty&0&-5&\infty\\ 5&7&\infty&9&0&\infty\\ 3&5&10&7&2&0 \end{pmatrix}\\ \end{aligned}\)

23.1-2

因为这采用了如下事实：从节点\(i\)回到自身的最短路径是一条空路径（没有负环的情况下），因此\(w_{ii}=0\)。

如果不使用\(w_{ii}=0\)，那么\(l_{ij}^{(r)}\)求的是从\(i\)到\(j\)恰好包含\(r\)条边的最短路径。那么到最后，还需要求解\(\displaystyle{\delta(i,j)=\min_{k=1}^n\{l_{ij}^{(k)}\}}\)，这将增加多余的代码量。

23.1-3

由于任何矩阵\(A\)和矩阵\(L^{(0)}\)“相乘”所得到的矩阵为\(A\)，因此\(L^{(0)}\)相当于是普通矩阵乘法中的单位矩阵。

23.1-4

不是一般性，考虑\(n\)阶级矩阵\(W^a,W^b,W^c\)，那么我们相当于证明\((W^a\cdot W^b)\cdot W^c=W^a\cdot(W^b\cdot W^c)\)。

考虑\((W^a\cdot W^b)\cdot W^c\)的第\(x\)行第\(y\)列的值\(w_{xy}\)以及\(W^a\cdot(W^b\cdot W^c)\)的第\(x\)行第\(y\)列的值\(w_{xy}'\)，那么有

\(\begin{aligned} w_{xy}&=\min_{j=1}^n\{\min_{i=1}^n\{w_{xi}^a,w_{ij}^b\},w_{jy}^c\}\\ &=\min_{j=1}^n\min_{i=1}^n\{w_{xi}^a,w_{ij}^b,w_{jy}^c\}\\ &=\min_{i=1}^n\{w_{xi}^a,\min_{j=1}^n\{w_{ij}^b,w_{jy}^c\}\}\\ &=w_{xy}' \end{aligned}\)

因此，这个矩阵运算的结合律成立，也就是有\((W^a\cdot W^b)\cdot W^c=W^a\cdot(W^b\cdot W^c)\)。

23.1-5

假设现在是求以原点为\(s\)的单源最短路。令\(v^0\)表示一个长度为\(n\)的行向量，其中\(v^0_s=0\)，并且对于\(\forall i\neq s,v_i^0=\infty\)。

那么，对于向量\(v^i\)，有\(v^i=v^{i-1}W\)。那么我们只需要花费\(O(n^3)\)的时间就可以计算出\(v^{n-1}=v^0\cdot W^{n-1}\)。最终，向量\(v^{n-1}\)就代表从原点\(s\)到各点的最短距离值。

在计算\(v^{i}=v^{i-1}W\)的过程就相当于是Bellman-Ford算法中的每一步迭代，\(W\)中的每一个元素\(w_{i,j}\)进行了一次乘法运算后，相当于在Bellman-Ford算法中边\((i,j)\)进行了一次松弛。

23.1-6

对子程序EXTEND-SHORTEST-PATHS和SLOW-APSP改写后的结果如下。事实上，这种更新方式是正确的，因为这相当于是Bellman-Ford算法进行松弛的过程：如果\(v.d>u.d+w(u,v)\)，那么将\(u.d+w(u,v)\)原地赋值给\(c.d\)。只是在这里可以视为相当于对每个节点执行了总共\(n\)次的Bellman-Ford算法，这里的\(l_{\cdot u}\)就相当于Bellman-Ford算法的\(u.d\)。因此，从前往后进行了\(n-1\)次松弛，这个改动是没错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
EXTEND-SHORTEST-PATHS'(L, W, n)
  for i = 1 to n
    for j = 1 to n
      for k = 1 to n
        l_{ij} = min{l_{ij}, l_{ik} + w_{kj}}


SLOW-APSP'(W, L(0), n)
  let L=(l_{ij}) and M = (m_{ij}) be new n × n matrices
  L = L(0)
  for r = 1 to n - 1
    EXTEND-SHORTEST-PATHS'(L, W, n)
  return L

然而，FAST-APSP不能省略\(M\)，因为计算\(M=L^2\)时需要保证\(L\)和\(L\)（左边的和右边的\(L\)）都是正确的。

23.1-7

直接暴力枚举所有节点\(i\)，然后以\(i\)为原点进行BFS。具体做法是，对于图\(G_s=(V,E_s)\)，如果\(l_{sv}=l_{su}+w_{uv}\)，那么\((u,v)\in E_i\)，那么从节点\(i\)开始进行BFS，遍历所有节点最终得到的\(j.\pi\)值填入\(\pi_{ij}\)即可。由于使用的是邻接矩阵，因此进行一次BFS的时间复杂度为\(O(n^2)\)，总共需要花费\(O(n^3)\)的时间才能构建出前驱矩阵\(\Pi\)。整个过程由CONSTRUCT-PI给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//假设子程序BFS-MAT(G, s)用于对图G进行BFS，且其原点为s。这里输入的G是以邻接矩阵来存储。
CONSTRUCT-PI(L, W, n)
  let Π be new n × n matrix
  V = {1, 2, 3, ..., n}
  for s = 1 to n
    E = ∅
    for u = 1 to n
      for v = 1 to n
        if l_{sv} == l_{su} + w_{uv}
        E = E ∪ {(u, v)}
    BFS-MAT((V, E))
    for v = 1 to n
      π_{sv} = v.π
  return Π

23.1-8

将\(\Pi\)中的每一行视为是一个独立的Bellman-Ford算法正在进行松弛操作，并且沿用\(\Pi^{(i-1)}\)的值来构造出\(\Pi^{(i)}\)。需要注意的是，\(\Pi^{(0)}\)的值为全空。具体的过程如下给出，可以发现，SLOW-APSP'''的时间复杂度同样为\(\Theta(n^4)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
EXTEND-SHORTEST-PATHS'''(L, Π, W, n)
  let L' be new n × n matrix by ∞
  Π' = Π
  for i = 1 to n
    for j = 1 to n
      for k = 1 to n
        if l'_{ij} > l_{ik} + w_{kj}
          l'_{ij} = l_{ik} + w_{kj}
          π'_{ij} = k
  return L', Π'


SLOW-APSP'''(W, L(0), n)
  let Π be new n × n matrix by NIL
  L = L(0)
  for r = 1 to n - 1
    L, Π = EXTEND-SHORTEST-PATHS''(L, Π, W, n)
  return L, Π

23.1-9

在整个循环结束后，再进行一次迭代，从而得到\(M=W^{2m},L=W^m,m\ge n-1\)。如果\(M\)和\(L\)不相同，那么说明存在一条长度超过\(n-1\)的最短路，因此这个图有负环。

整个算法由程序FASTER-APSP'给出，其时间复杂度为\(\Theta(n^3\lg n)\)，相比起FASTER-APSP，仅仅是多运行了一次程序EXTEND-SHORTEST-PATHS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FASTER-APSP'(W, n)
  let L and M be new n × n matrices
  L = W
  r = 1
  while r < n - 1
    M = ∞  // initialize M
    EXTEND-SHORTEST-PATHS(L, L, M, n) // compute M = L^2
    r = 2r
    L = M // ready for the next iteration
  M = ∞
  EXTEND-SHORTEST-PATHS(L, L, M, n)
  for i = 1 to n
    for j = 1 to n
      if l_{ij} != m_{ij}
        return False
  return True

23.1-10

最基本的想法很简单：只要找到最小的\(m\)，\(\exists i,l_{ii}^{(m)}<0\)即可。也就是说从\(i\)到\(i\)已经存在一条负数边权的路径。

其中一种最简单的做法是，从小到大枚举\(m\)值，计算出\(L^{(m)}\)后直接判断即可。这个过程由MINIMUM-NEG-CYCLE给出，可以看出这个算法是基于SLOW-APSP的，其时间复杂度为\(O(n^4)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
MINIMUM-NEG-CYCLE(W, L(0), n)
  let L=(l_{ij}) and M = (m_{ij}) be new n × n matrices
  L = L(0)
  // 最短的负环长度可能达到n，需要注意。
  for r = 1 to n
    M = ∞
    EXTEND-SHORTEST-PATHS'(L, W, n)
    L = m
    for i = 1 to n
      if l_{ii} < 0
        return r
  // 不存在负环。
  return -1

另外一种做法则是基于FASTER-APSP的，使用倍增法进行实现。每次将当前矩阵\(L\)尝试乘上一个\(L^{(m)}\)，得到新矩阵\(L'\)。如果仍未检测出负环，那么用\(L'\)代替\(L\)，并将\(m\)翻倍，否则将\(m\)进行减半。

在这种情况下，EXTEND-SHORTEST-PATHS将只会被调用\(O(\lg n)\)次，因此整个程序的时间复杂度为\(O(n^3\lg n)\)。完整过程由MINIMUM-NEG-CYCLE'给出。

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
MINIMUM-NEG-CYCLE'(W, n)
  L = L(1) = W
  m = 1
  k = 1
  while k < n or m > 0
    M = ∞
    if k + m > n
      m = ⌊m / 2⌋
    else
      if L(m) == NIL
        L(m) = ∞
        EXTEND-SHORTEST-PATHS(L(m/2), L(m/2), L(m), n)
      EXTEND-SHORTEST-PATHS(L, L(m), M, n)
      have-neg-cycle = False
      for i = 1 to n
        if m_{ii} < 0
          have-neg-cycle = True
      if have-neg-cycle == True
        m = ⌊m / 2⌋
      else
        L = M
        k = k + m
        m = m * 2
  if k < n
    // 找到了负环。
    return k + 1
  else
    // 没有找到负环。
    return -1