算法导论23 Problems 答案

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

23-1

a

这个更新算法由UPDATE-TRANSITIVE-CLOSURE给出。这个算法的基本思想是，在转递闭包从\(i\)到\(j\)中如果可以经过边\((x,y)\)到达（也就是存在\(i\rightarrow x\rightarrow y\rightarrow j\)的路径），那么就将\((i,j)\)添加到\(E^{\ast}\)中。由于对\(V\)中每个节点都进行了两层遍历，因此其时间复杂度为\(O(V^2)\)。

1
2
3
4
UPDATE-TRANSITIVE-CLOSURE(T*, n, x, y)
  for i = 1 to n
    for j = 1 to n
      t_{ij}* = t_{ij}* ∨ (t_{ix}* ∧ t_{yj}*)

b

考虑满足如下性质的图\(G=(V,E)\)：

  1. \(V\)中的所有点划分成均匀的两部分\(V_1,V_2\)，即\(|V_1|=|V_2|=\dfrac{|V|}{2}\)。
  2. 节点集合\(V_1,V_2\)内部是强连通的。
  3. 节点集合\(V_1,V_2\)之间不连通。

那么选择\(u\in V_1,v\in V_2\)，添加这条边到\(E\)中，那么就枚举\(V_1\)中的所有节点\(x\)和\(V_2\)中的所有节点\(y\)，将\((x,y)\)都添加到\(E^{\ast}\)中，这意味着需要添加\(\dfrac{|V|^2}{4}\)条边。因此无论采用什么算法更新传递闭包，其时间复杂度都满足\(\Omega(V^2)\)。

c

首先注意到，当\(t_{ix}^{\ast}=0\)时，这个循环可以跳过，因为从\(i\)不能到达\(x\)，边\((x,y)\)并不能对\(i\)的任何后继\(t_{i\cdot}^{\ast}\)做出任何改动。当\(t_{ix}^{\ast}=1\)时，如果\(t_{iy}^{\ast}=1\)，那么也可以跳过，因为从\(i\)已经可达\(y\)，从\(y\)可以到达的节点在之前就已经维护好，此时从\(i\)也可到达这些节点，因此边\((x,y)\)并没有用处。这个维护算法由UPDATE-TRANSITIVE-CLOSURE'给出。

1
2
3
4
5
6
UPDATE-TRANSITIVE-CLOSURE'(T*, n, x, y)
  for i = 1 to n
    if t_{ix}* == 1 and t_{iy}* == 0 
      for j = 1 to n
        if t_{yj}* == 1
          t_{ij}* = 1

假设每次输入的边\((x,y)\)是不同的，那么最多就会有\(n(n-1)n\)个不同的输入，\(r\)的最大值为\(r=n(n-1)\)。在这\(r\)次对UPDATE-TRANSITIVE-CLOSURE'调用中，到内层for循环最多可以进入\(n(n-1)=O(n^2)\)次，因为第2行中有一个判断\(t_{iy}^{\ast}=0\)的要求，只有满足这个条件内层for循环才能进入；进入内层for循环后，当\(j=y\)时，\(t_{yj}^{\ast}=t_{yy}^{\ast}=1\)必定成立，因此\(t_{iy}^{\ast}\)被赋值成了\(1\)，此后再也不能通过满足\(t_{iy}^{\ast}=0\)这个条件进入内层for循环。

一开始，表\(T^{\ast}\)中最多只有\(n(n-1)=O(n^2)\)个项为\(0\)。因此，这\(r\)次调用总共的时间复杂度为\(O(n)\cdot O(n^2)=O(n^3)=O(V^3)\)。

23-2

a

按照题目6-2中的结论，如果是使用\(d\)叉最小堆，那么调用一次INSERT和DECREASE-KEY都需要\(O(\log_d n)\)的时间；而调用一次EXTRACT-MIN需要\(O(d\log_d n)\)的时间。

如果限定了\(d=\Theta(n^{\alpha})\)，那么调用一次INSERT和DECREASE-KEY都需要\(O(1/\alpha)\)的时间；而调用一次EXTRACT-MIN需要\(O(n^{\alpha}/\alpha)\)的时间。

b

考虑使用Dijskra算法完成这个单源最短路算法，其内部数据结构使用的是\(d\)叉堆。

可知它一共使用了\(|V|\)次INSERT操作，\(|V|\)次EXTRACT-MIN操作和\(|E|\)次DECREASE-KEY操作。那么其总时间复杂度为\(O(V\log_d V+Vd\log_d V+E\log_d V)=O(Vd\log_d V+E\log_d V)\)。

令\(d=|V|^{\epsilon}\)，那么有

\(\begin{aligned} O(Vd\log_d V+E\log_d V)&=O\left(\dfrac{V^{1+\epsilon}}{\epsilon}+\dfrac{E}{\epsilon}\right)\\ &=O\left(\dfrac{2E}{\epsilon}\right)\\ &=O(E) \end{aligned}\)

c

将题目23-2-b介绍的时间复杂度为\(O(E)\)的Dijskra算法作为子程序运行\(|V|\)次，那么就可以以\(O(VE)\)的时间求出无负权边图的全部点对的最短路径。

d

使用Johnson算法可以解决，大致步骤如下。

  1. 通过Bellman-Ford算法可以完成\(h\)的计算，其时间复杂度为\(O(VE)\)。

  2. 通过\(h\)，计算出新的边权权重\(\hat{w}\)，这里需要花费时间\(O(E)\)。

  3. 由于\(\hat{w}\)是非负的，那么使用题目23-2-c介绍的Dijskra算法完成全部点对的最短路径计算，得到\(D'\)，其花费的时间为\(O(VE)\)。

  4. 根据\(D'\)和\(h\)，恢复出使用\(w\)对应的全部点对的最短路径\(D\)，其花费的时间为\(O(V^2)\)。

因此，使用Johnson算法可以以\(O(VE)\)的时间完成对\(D\)的计算。