算法导论22.2 Exercises 答案

发表于 2023-05-04 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 2.4k 阅读时长 ≈ 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$也同样构成一条关键路径。

// 假设数组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’)$，包含以下两种边：

$\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]$。
$\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{fG(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)}$。

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