算法导论29.2 Exercises 答案

29.2-1

这个最短路问题的对应线性规划问题如下：

$\begin{aligned}
\text{maximize}&& d_x\
\text{subject to}& \
&&d_t&\le d_s+3\
&&d_y&\le d_s+5\
&&d_x&\le d_t+6\
&&d_y&\le d_t+2\
&&d_z&\le d_x+2\
&&d_t&\le d_y+1\
&&d_x&\le d_y+4\
&&d_z&\le d_y+6\
&&d_s&\le d_z+3\
&&d_x&\le d_z+7\
&&d_s&=0
\end{aligned}$

29.2-2

这和第29.2章介绍的线性规划系统类似，如下给出：

$\begin{aligned}
\text{maximize}&& \sum_{v\in V} d_v\
\text{subject to}& \
&&d_v&\le d_u+w(u,v) &&\forall (u,v)\in E \
&&d_s&=0
\end{aligned}$

两条约束和29.2所给出的约束相同，区别在于目标函数。由于目前是希望最大化所有变量$d_v$，但是最短路径的松弛性质仍然保持，因此这时的最优解对应了$s$到所有节点的最短路径长度。

29.2-3

这个最大流问题的对应线性规划问题如下：

$\begin{aligned}
\text{maximize}&& f{sv_1}+f{sv2}\
\text{subject to}& \
&&f{uv}&\ge 0 &&\forall (u,v)\in E \
&&f{sv_1}&\le 16\
&&f{sv2}&\le 14\
&&f{v1v_3}&\le 12\
&&f{v2v_1}&\le 4\
&&f{v2v_4}&\le 14\
&&f{v3v_2}&\le 9\
&&f{v3v_t}&\le 20\
&&f{v4v_3}&\le 7\
&&f{v4t}&\le 4\
&&f{sv1}+f{v2v_1}&= f{v1v_3}\
&&f{sv2}+f{v3v_2}&= f{v2v_1}+f{v2v_4}\
&&f{v1v_3}+f{v4v_3}&= f{v3v_2}+f{v3t}\
&&f{v2v_4}&= f{v4v_3}+f{v_4t}\
\end{aligned}$

29.2-4

这里使用题目24.1-4的结果：

$\begin{aligned}
\text{maximize}&& \sum{(s,v)\in E} f{sv}-\sum{(v,s)\in E} f{vs}\
\text{subject to}& \
&&f{uv}&\ge 0 &&\forall (u,v)\in E \
&&f{uv}&\le c(u,v) &&\forall (u,v)\in E \
&&\sum{(u,v)\in E} f{uv}&=\sum{(v,u)\in E} f{vu} &&\forall u\in V-{s,t}
\end{aligned}$

可见，这里一共有$2|E|+|V|-2=O(V+E)$条约束。

29.2-5

令二分图$G=(V,E),V=L\cup R$。使用第24.3章的结论，我们可以将这个问题转化成最大流问题进行解答：令$V’=V\cup{s,t},E’={(s,l):l\in L}\cup{(r,t):r\in R}\cup E$，对于$\forall (u,v)\in E’$，都有$c(u,v)=1$。那么图$G$的二分图最大匹配数量相当于是图$G’=(V’,E’)$中从$s$到$t$的最大流。这个线性规划将使用题目29.2-4的结论，如下：

$\begin{aligned}
\text{maximize}&& \sum{l\in L}f{sl} \
\text{subject to}& \
&&f{uv}&\ge 0 &&\forall (u,v)\in E’ \
&&f{uv}&\le c(u,v) &&\forall (u,v)\in E’ \
&&\sum{(u,v)\in E’} f{uv}&=\sum{(v,u)\in E’} f{vu} &&\forall u\in V
\end{aligned}$

29.2-6

这意味着对于任意一条路径$p_i$，如果其经过边$(u,v)$，那么这条路径就需要受到这条边容量的限制。因此，对于路径$P$，我们可以写出如下线性规划：

$\begin{aligned}
\text{maximize}&& \sum{i=1}^px_i \
\text{subject to}& \
&&x{i}&\ge 0 &&\forall i\in[1,p] \
&&\sum_{1\le i\le p,(u,v)\in P_i}x_i&\le c(u,v) &&\forall (u,v)\in E \
\end{aligned}$

如果$G$是一个有$\dfrac{|V|(|V|-1)}{2}$条边的有向无环图，那么$p$的值可以达到$2^{|V|-2}$。因此使用这个线性规划求解最大流问题是不明智的，因为约束的大小和数量都太多（呈指数级数量）。

29.2-7

只需要对多商品流问题的目标函数进行修改即可。修改后的线性规划问题如下：

$\begin{aligned}
\text{minimize}&& \sum{(u,v)\in E}a(u,v)\cdot\left(\sum{i=1}^k f{i,u,v}\right) \
\text{subject to}& \
&&\sum{i=1}^kf{i,u,v}&\le c(u,v) &&\forall (u,v)\in E\
&&\sum{(u,v)\in E}f{i,u,v}-\sum{(v,u)\in E}f{i,v,u}&= 0 &&\forall i\in[1,k],\forall u\in V-{s_i,t_i} \
&&\sum{(si,v)\in E}f{i,si,v}-\sum{(v,si)\in E}f{i,v,si}&= d_i &&\forall i\in[1,k]\
&&f{i,u,v}&\ge 0 &&\forall i\in[1,k],\forall (u,v)\in E\
\end{aligned}$