算法导论22.2 Exercises 答案

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

22.2-1

整个迭代过程如下：

\(\begin{array}{|l|l|l|}\hline v&d&\pi\\\hline r&0&\text{NIL}\\\hline s&\infty&\text{NIL}\\\hline t&\infty&\text{NIL}\\\hline x&\infty&\text{NIL}\\\hline y&\infty&\text{NIL}\\\hline z&\infty&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline r&0&\text{NIL}\\\hline s&5&r\\\hline t&3&r\\\hline x&\infty&\text{NIL}\\\hline y&\infty&\text{NIL}\\\hline z&\infty&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline r&0&\text{NIL}\\\hline s&5&r\\\hline t&3&r\\\hline x&11&s\\\hline y&\infty&\text{NIL}\\\hline z&\infty&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline r&0&\text{NIL}\\\hline s&5&r\\\hline t&3&r\\\hline x&10&t\\\hline y&7&t\\\hline z&5&t\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline r&0&\text{NIL}\\\hline s&5&r\\\hline t&3&r\\\hline x&10&t\\\hline y&7&t\\\hline z&5&t\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline r&0&\text{NIL}\\\hline s&5&r\\\hline t&3&r\\\hline x&10&t\\\hline y&7&t\\\hline z&5&t\\\hline \end{array}\)

22.2-2

令\(z\)是这个拓扑序列的最后一个节点。我们首先证明\(z\)在图\(G\)中没有出边。如果\(z\)有出边，假设这条出边指向的节点是\(u\)，那么在拓扑序列\(u\)应该在\(z\)后面，这和\(z\)是最后一个节点是矛盾的。因此\(z\)没有出边。

既然\(z\)没有出边，那么它对应的邻接表的槽则是空的，那么自然不需要去遍历\(z\)所对应的槽，因此原结论成立。

22.2-3

改造后的算法如程序DAG-LONGEST-PATHS'所示。为了方便构造出一条路径，避免每个节点都运行一次算法，我们将构造一个虚拟原点\(s\)，它作为所有任务的前驱，最先被执行，并且不需要完成时间。\(E\)中的每一条边\((u,v)\)的边权都相当于是任务\(v\)的完成时间\(T[v]\)。在这里，\(v.d\)是指完成节点\(v\)时的最长时间。最终满足\(v.d\)最大的\(v\)，\(v.\pi\)也同样构成一条关键路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 假设数组T[u]表示完成任务u的时间。
DAG-LONGEST-PATHS'(G, T)
  topologically sort the vertices of G
  // 初始化
  let s be a source node
  INSERT(G.V, s)
  for each u ∈ G.V - {s}
    u.d = -∞
    u.π = NIL
    INSERT(G.Adj[s], u)
  s.d = 0
  s.π = NIL
  for each vertex u ∈ G.V, taken in topologically sorted order
    for each vertex v in G.Adj[u]
      if v.d < u.d + T[v]
        v.d = u.d + T[v]
        v.π = u

另外一种构造思路则是将每个任务节点\(u\)拆分成两个状态：进入状态\(u_i\)和完成状态\(u_o\)，并且连入一条边\((u_i,u_o),w(u_i,u_o)=T[u]\)。对于外部的任务依赖过程，则不需要花费时间。更正式的定义一个新图\(G'=(V',E')\)，包含以下两种边：

  1. \(\forall u\in V,u_i\in V',u_o\in V',(u_i,u_o)\in E',w'(u_i,u_o)=T[u]\)。
  2. \(\forall (u,v)\in E,(u_o,v_i)\in E',w'(u_o,v_i)=0\)。

那么对图\(G'\)进行DAG-LONGEST-PATHS也可以求出一条关键路径，不过构造关键路径时，只记录边权大于\(0\)的边。

\(\star\) 22.2-4

和题目20.4-2类似，考虑使用动态规划的思想来解决本题。

令\(f_G(v)\)表示在有向无环图\(G\)，终点为\(v\)的路径条数。那么可以写出如下状态转移方程：

\(\displaystyle{f_G(v)=1+\sum_{u\in V;(u,v)\in E} f_G(u)}\)

这个方程的意思是，对于所有到达\(u\)的路径，拼接一条边\((u,v)\)就能让它们都到达\(v\)，由于最后一条路径是不同的，因此不会重复计数。

由于\(G\)是一个有向无环图，\(f_G\)并不会形成循环。我们可以考虑从\(G\)的拓扑序列上实现计算\(f_G\)的过程。计算\(f_G(v)\)的算法由CAL-PATHS'过程给出。

因此，整道题目的最终答案为\(\displaystyle{\sum_{u\in V} f_G(v)}\)。

1
2
3
4
5
6
7
8
9
10
11
12
CAL-PATHS'(G)
  topologically sort the vertices of G
  // 初始化
  for each u ∈ G.V
    u.paths = 1
  for each vertex u ∈ G.V, taken in topologically sorted order
    for each vertex v in G.Adj[u]
      v.paths = v.paths + u.paths
  paths = 0
  for each u ∈ G.V
    paths = paths + u.paths = 1
  return paths