课程主页:

https://cs170.org/

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

课程视频:

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

这次回顾Section 8。

1. Taking a Dual

对偶问题为

2. Weighted Rock-Paper-Scissors

(a)
r p s
r 0 -5 3
p 5 0 -1
s -3 1 0
(b)

假设策略为$(x_1,x_2,x_3)$,那么LP问题为

3. Domination

(a)

由于$E$支配$D$,所以选择$D$的概率为$0$。

(b)

注意到删除行$D$之后,列$A$严格最优,而列是选择最小值,所以选择$A$的概率为$0$。

(c)

由于列必然不选择$A$,所以剩下可选的行为

	B	C
E	2	-2
F	-2	2

由课本上的讨论可得选择$E,F$的概率都为$\frac 1 2$

4. MT2 Practice: Greedy

(a)
(a1, b1) = (0, 2)
(a2, b2) = (1.5, 2.5)
(a3, b3) = (2.1, 4)

显然最优解为$2$,但是算法$A$给出的结果是$1$。

(b)

利用反证法证明。

假设算法$B$给出的区间集合为$C_1$,如果存在元素更多的区间集合$C_2 $,对应的区间元素分别为

那么根据算法$B$的特点,可以将$C_2$中第一个元素替换为$C_1$中第一个元素,这是因为显然有

这样得到的新集合依然是不相交区间,并且可以将$C_2$中第二个元素替换为$C_1$中第二个元素,如果$|C_2|>|C_1|$,那么经过$|C_1|$次替换后$C_2$还有元素,该元素和$C_1$中最后一个区间不相交,但是根据算法$B$,必然不存在这样的区间,所以必然有

(c)

假设算法$A$得到的区间集合为$C_1$,算法$B$得到的区间集合为$C_2$,对应的区间元素分别为

考虑$(a^{1}_i, b^1_i)$,或者该区间属于$C_2$,或者该区间最多和$C_2$中两个区间相交,这是因为如果和$c_2$中大于两个区间相交,那么必然存在区间$(a_j^2,b_j^2)$满足

因为选择$(a_i^1,b_i^1)$是合理的,所以将其替换为$(a_j^2,b_j^2)$也是合理的,但是根据算法$A$,应该选择$(a_j^2,b_j^2)$,这就产生了矛盾,所以$(a^{1}_i, b^1_i)$最多和$C_2$中两个区间相交,根据此对应关系,我们可得

5. MT2 Practice: MSTs

(a)

如果边的权重不同,那么每次选择最小割时必然是唯一的,所以MST唯一。

(b)

不正确,考虑下图

a					e
	c --------- d
b					f

其中边为$(a, b),(b, c),(a, c);(d,e),(e,f),(d,f);(c,d)$,假设$(c,d)$的权重最大,显然必然包含这条边。

(c)

结论是正确的。

记权重最小的唯一边为$a$,利用反证法,如果$a$不属于某个MST,那么在MST中添加$a$必然得到环,删除环中某条边得到MST,但是总权重显然更小,这就产生了矛盾。

备注:

这一这题和(b)存在区别,因为(b)可能给出如下证明:

记权重最大的唯一边为$a$,利用反证法,如果$a$属于MST,那么在MST中添加图中任意其他边$b$,然后删除$a$依然得到MST,但是总权重显然更小,这就产生了矛盾。

该证明是错误的,因为不一定存在另一条边$b$,使得将其添加到MST后形成环。

6. MT2 Practice: Dynamic Programming

(a)

考虑如下例子

1: 2
2: 3
3: 1
4: 1

贪心算法产生的路径是

1, 3, 4, 5

最优路径为

1, 2, 5
(b)

记$a[i]$为到达$i$的最少步骤数,给出如下算法

  • $a[1]=0$
  • $a[i]=\infty, i=2,\ldots,n$
  • for $i=2,\ldots,n$
    • for $j=1,\ldots,\min(i-1, d(i))$
      • if $i-j \ge 1$:
        • $a[i]=\min(a[i],a[i-j] + 1)$
  • return $a[n]$