CS170 Efficient Algorithms and Intractable Problems Section6

课程主页：

课程视频：

这次回顾Section 6。

1. Shortest Paths with Dynamic Programming!

记最优解为$d(S,E)$。

(a)

需要解决的子问题是$S\to F$的最短路径，其中$(F,E)\in G$，对于此例，子问题是$S\to B, S\to D$。

(b)

显然

$d(S,E) = \min \left(d(S,B) + 2 , d(S,D) + 1\right)$

(c)

dependency graph是有向无环图。

(d)

拓扑排序。

(e)

一共有$|V|$个子问题，要求解每个问题，需要求解的子问题和每个节点的入度相关。

(f)

所以路径为$SCDE$。

2. String Shuffling

1

定义子问题：$x[:i],y[:j]$能否构成$z[:i+j]$。

2

初始算法：

定义数组$dp[|x| + 1][|y| + 1] = \{0\}$
$dp[0][0] = 1$
for $i=1,\ldots , |x| $:
- $dp[i][0] = dp[i - 1][0] \land (x[i] == z[i])$
for $j= 1, \ldots, |y|$:
- $dp[0][j] = dp[0][j - 1] \land (y[j] == z[j])$
for $i=1,\ldots , |x| $:
- for $j= 1, \ldots, |y|$:
  - $dp[i][j] = (dp[i-1][j] \land (x[i] == z[i + j])) \lor (dp[i][j-1] \land (y[j] == z[i + j]))$

改进算法：

定义数组$dp[|y|] = \{0\}$
$dp[0] = 1$
for $j= 1, \ldots, |y| $:
- $dp[j] = dp[j - 1] \land (y[j] == z[j])$
for $i=1,\ldots , |x|$:
- $dp[0] = dp[0] \land (x[i] == z[i])$
- for $j= 1, \ldots, |y|$:
  - $dp[j] = (dp[j] \and (x[i] == z[i + j])) \lor (dp[j-1] \land (y[j] == z[i + j]))$

该算法的空间复杂度为$O(|y|)$，类似可得空间复杂度为$O(|x|)$的算法，因此空间复杂度可以降低到

$O(\min(|x|,|y|))$

3. Vertex cover

选择树$T$的根节点$r$，定义$dp[i]$为以$i$为根节点的子树对应的最优解，那么可得如下算法：

对于叶节点$i$，$dp[i]=0$
对于非叶节点$i$：
- $dp[i]=\min \left(1 + \sum_{j:(i,j )}dp[j], \sum_{j:(i,j)} \left(1 +\sum_{k:(j,k)} dp[k]\right)\right)$
- 情形1对应选择根节点$i$，情形2对应选择根节点的直接子节点。