课程主页：

https://cs170.org/

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

课程视频：

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

这次回顾HW9。

2. A cohort of spies

最大流问题：

  • 顶点：起点$s$，间谍的出发城市$\cup \{s_i\}$，安全城市$T$，终点$t$
  • 边：分为三部分
    • 起点：$(s ,s_i)$
    • 逃生路径：$(s_i,t_j)$
    • 终点：$(t_i,t), t_i \in T$
  • 容量：
    • 起点：$c(s, s_i)=c$
    • 逃生路径：$c(s_i,t_j)=c$
    • 终点：$c(t_i,t)=c$（这样可以保证不会有超过$c$个人通过每个安全城市）

3. Max Flow, Min Cut, and Duality

(a)

对偶问题：

变量和边的对应关系：

  • $x_1:(S,A)$
  • $x_2:(S,B)$
  • $x_3:(A,T)$
  • $x_4:(A,B)$
  • $x_5:(B,T)$
(b)

考虑分割$(\{S,A\},\{B,T\})$，则令$x_2,x_3,x_4=1$，其余为$0$，那么这样的赋值为可行解，对应的结果为

其余分割同理。

(c)

根据(b)可得，对偶问题计算的是割的最小权重和，即最小割。

4. Zero-Sum Battle

1

设$A$的策略为$(x_1,x_2,x_3)$，那么对于$A$的最优化问题为

Status: Infeasible
x1 = 0.42647059
x2 = 0.48529412
x3 = 0.088235294
z = 0.0
2

设$B$的策略为$(y_1,y_2,y_3)$，那么对于$B$的最优化问题为

Status: Optimal
y1 = 0.34117647
y2 = 0.30588235
y3 = 0.35294118
z = 0.0

代码如下：

from pulp import *

## trainer A
probA = LpProblem("TrainerA", LpMaximize)

x1 = LpVariable("x1", 0, None)
x2 = LpVariable("x2", 0, None)
x3 = LpVariable("x3", 0, None)
z = LpVariable("z", 0, None)

probA += z
probA += z <= -10 * x1 + 4 * x2 + 6 * x3
probA += z <= 3 * x1 - x2 - 9 * x3
probA += z <= 3 * x1 - 3 * x2 + 2 * x3
probA += x1 + x2 + x3 == 1
probA.solve()

print("Status:", LpStatus[probA.status])
for v in probA.variables():
    print(v.name, "=", v.varValue)

# trainer B
probB = LpProblem("TrainerB", LpMinimize)

y1 = LpVariable("y1", 0, None)
y2 = LpVariable("y2", 0, None)
y3 = LpVariable("y3", 0, None)

probB += z
probB += z >= -10 * y1 + 3 * y2 + 3 * y3
probB += z >= 4 * y1 - y2 - 3 * y3
probB += z >= 6 * y1 - 9 * y2 + 2 * y3
probB += y1 + y2 + y3 == 1
probB.solve()

print("Status:", LpStatus[probB.status])
for v in probB.variables():
    print(v.name, "=", v.varValue)

5. Minimum Spanning Trees

(a)

约束条件的解释：

  • $x_{u,v}=1$表示选择这条边，否则表示不选；
  • 约束条件1的含义是，对于任意一个划分，至少选择一个割边；
  • 约束条件2的含义是，边的数量小于等于$|V|-1$

求解完该最优化问题后，优化目标即为MST的权重，$x_{u,v}=1$对应的边即构成MST。

下面说明为什么该优化问题返回的是MST。

首先第二个约束条件可以转换为等号，因为如果等号不成立，那么必然有一个顶点没有被选到，那么该顶点和剩余顶点构成的划分不满足第一个条件，这就产生了矛盾；另一方面，同理可得所有顶点必然要被选择到（不存在一个顶点选择多次的情况），否则依然不满足第一个条件。这说明满足约束条件的必然是一棵树，优化目标为最小化树的权重和。

(b)
  • 约束1：$2^{|V|}$
  • 约束2：$1$
  • 约束3：$|E|$

所以总约束数量为

(c)

约束条件变弱，所以搜索空间增加，从而求得的结果更小。

例子：

考虑下图

a  b
c  d

权重为

(a, b) : 1
(b, c) : 2
(c, d) : 100
(d, a) : 1
(a, c) : 1
(b, d) : 0.5

MST为$(a, b),(a,c),(a,d)$，权重和为$3$。

松弛问题的一个可行解为

该权重和为$2.75$。