CS170 Efficient Algorithms and Intractable Problems Section4

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 4。

1. Minimum Spanning Trees (short answer)

(a)

初始化$X= E’$，对$(u, v)\in E’$，令

• $\mathrm{union}(u,v)$

剩余部分不变。

(b)

对每条边加上权重$d$，使得每条边的权重都为正数，然后计算MST，注意MST包括的边数恒定，所以新旧MST的权重对应关系为

$$w\leftrightarrow w + |V| d$$

由此可得变换后的MST和原始的MST一一对应。

(c)

构造新图$G’$，令$w(u,v)=-w(u,v)$，然后计算$G’$的MST即可。

2. Picking a Favorite MST

对于Kruskal算法，每轮迭代中选择属于$F$的边；对于Prim算法，只有当$(v,z)\in F$时才更新cost。

3. MST Variant

这部分参考了习题解答。

伪代码如下：

• 在$G=(V,E)$上计算MST，得到$T_0$，权重为$w(T_0)$
• 初始化$T_1= T_0$
• for $s\in S$:
  • $T_2=T_0\cup \{s\}$
  • 在$T_2$包含的环中删除权重最大边。
  • if $w(T_1) < w(T_2)$:
    • $T_1 = T_2$
• return $T_1 $

算法是简洁明了的，下面证明其正确性。

假设$T_2$是满足条件的MST，那么

$$w(T_2)\le w(T_1)$$

如果$T_2$不包含属于$S$的边，那么$T_1=T_2= T_0$，结论成立。

如果$T_2$包含属于$S$的边，不妨设为$s_2$，考虑$T_1$中同样属于$S$的边$s_1$，注意$s_2$为一个分割，节点被划分为$V_1,V_2$，假设在$E$中跨越该分割的最小边为$s_3$。

如果$s_1=s_2=s$，那么$T_2 -\{s\} +\{s_3\}$是$G=(V,E)$上一棵最小生成树，假设$w(T_2) < w(T_1)$，那么

$$w(T_2 -\{s\}+ \{s_3\}) < w(T_1 -\{s\} +\{s_3\})= w(T_0)$$

这就与$T_0$的定义矛盾。

如果$s_1\neq s_2$，注意到在上述算法中必然考虑过$s_2$，而$T_0 +\{s_2\}-\{s_3\}$必然算法中选择的树权重更大（注意$s_3$的定义），因此

$$w(T_1) \le w(T_0 +\{s_2\}-\{s_3\})$$

假设$w(T_2) < w(T_1)$，那么

$$w(T_2 -\{s_2\}+ \{s_3\}) < w(T_1 -\{s_2\} +\{s_3\}) \le w(T_0 +\{s_2\}-\{s_3\}-\{s_2\} +\{s_3\})=w(T_0)$$

注意$T_2 -\{s_2\} +\{s_3\}$是$G=(V,E)$上一棵最小生成树，这就与$T_0$的定义矛盾。

因此，我们总有

$$w(T_2)\ge w(T_1)$$

结合反方向的不等式可知

$$w(T_1)=w(T_2)$$

4. Service scheduling

$$\begin{aligned} T&=\sum_{i=1}^{n}(\text{time spent waiting by customer }i)\\ &= \sum_{i=1}^{n} \sum_{j=1}^i t_j \\ &= \sum_{j=1}^n \sum_{i=j}^n t_j \\ &=\sum_{j=1}^n (n-j+1)t_j \end{aligned}$$

要使得上式最小，根据排序不等式，应该满足如下条件：

$$t_1\le t_2 \le \ldots \le t_n$$

因此算法如下：

• 将$t_i$从小到大排序。
• 计算$\sum_{j=1}^n (n-j+1)t_j$。