算法导论22.4 Exercises 答案
22.4-1
可以知道，约束图$G=(V,E)$为：$V={v_0,v_1,v_2,v_3,v_4,v_5,v_6},E$为下表：
$\begin{array}{|l|l|}\hline
e&w(e)\\hline
(v_0,v_1)&0\\hline
(v_0,v_2)&0\\hline
(v_0,v_3)&0\\hline
(v_0,v_4)&0\\hline
(v_0,v_5)&0\\hline
(v_0,v_6)&0\\hline
(v_2,v_1)&1\\hline
(v_4,v_1)&-4\\hline
(v_3,v_2)&2\\hline
(v_5,v_2)&7\\hline
(v_6,v_2)&5\\hline
(v_6,v_3)&10\\hline
(v_2,v_4)&2\\hline
(v_1,v_5)&-1\\hline
(v_4,v_5)&3\\hline
(v_3,v_6)&8\\hline
\end{array}$
最终对原点$0$执行Bellman-Ford算法，得到原差分约束的一个解为：
$(x_1,x_2,x_3,x_4,x_5,x_6)^T=(-5,-3,0,-1,-6,-8)^T$。
22.4-2
可以知道，约束图$G=(V,E)$为：$V={v_0,v_1,v_2,v_3,v_4,v_5},E$为下表：
$\begin{array}{|l|l|}\hline
e&w(e)\\hline
(v_0,v_1)&0\\hline
(v_0,v_2)&0\\hline
(v_0,v_3)&0\\hline
(v_0,v_4)&0\\hline
(v_0,v_5)&0\\hline
(v_2,v_1)&4\\hline
(v_5,v_1)&5\\hline
(v_4,v_2)&-6\\hline
(v_2,v_3)&1\\hline
(v_1,v_4)&3\\hline
(v_3,v_4)&5\\hline
(v_5,v_4)&10\\hline
(v_3,v_5)&-4\\hline
(v_4,v_5)&-8\\hline
\end{array}$
最终运行Bellman-Ford算法后，发现了一个负环$(v_1,v_4,v_2,v_3,v_5,v_1)$，其权值为$-1$。因此该差分约束无解。
22.4-3
不会。因为对于所有$v\in V-{v_0}$，$E$中都有一条边$(v_0,v)$，其权值为$0$。这说明从$v_0$到每个节点至少有一条长度为$0$的路径。随着Bellman-Ford算法对每一条边进行松弛，$v.d$的值只会递减。因此，在这个系统下不会有任何含有正数的解。
22.4-4
令$G=(V,E)$，那么$s$到$t$的最短路径问题表示成一个线性规划问题是：
$\begin{aligned}
\text{maximize}&& d_t\
\text{subject to}& \
&&d_v&\le d_u+w(u,v) &&\forall (u,v)\in E \
&&d_s&=0
\end{aligned}$
取最大值的原因是，$\displaystyle{dv=\min{(u,v)\in E}{d_u+w(u,v)}}$，即$d_v$是小于等于$d_u+w(u,v)$中的最大值。
22.4-5
在Bellman-Ford的角度看来，边$(v_0,v)$的权值为$0$是使所有节点$v\in V-{v_0}$，$v.d\le 0$均成立。因此我们修改程序BELLMAN-FORD，使得其初始化时所有节点$u$为$u.d=0$即可。并且，这个算法是接受边权三元组输入，而不是邻接表输入。此时的时间复杂度将达到$O(nm)$。
22.4-6
如果满足$x_i=x_j+b_k$，那么也就是同时满足$x_i\le x_j+b_k,x_i\ge x_j+b_k$，进行变换后，得到两条不等式：
$\begin{aligned}
x_i-x_j&\le b_k\
x_j-x_i&\le -b_k
\end{aligned}$
将它们都添加到差分约束系统中即可。
22.4-7
这道题是22.4-5的实现，由过程DIFFERENCE-CONSTRAINTS-SOLVER给出，其时间复杂度为$O(nm)$。
1 | DIFFERENCE-CONSTRAINTS-SOLVER(G) |
$\star$ 22.4-8
由于$\forall v_i\in V-{v_0}$，都有$(v_0,v_i)\in E,w(v_0,v_i)=0$，因此$x_i=\delta(v_0,v_i)\le w(v_0,v_i)=0$。
对于任意一组解$(y1,y_2,\dots,y_n)$，我们需要证明$y_i\le x_i$均成立。
对于任意$v_i\in V-{v_0}$，以及任意一条从$v_0$到$v_i$的一条最短路径$v{j1},u{v{j_2}},\dots,v{jk}$，其中$j_1=0,j_k=i$，对于所有$t=2,3,\dots,k$，都有$y{j{t+1}}-y{jt}\le w(v{j{t+1}}-v{j_t})$均成立。
因此将这$k-1$条不等式左右分别相加，得到$\displaystyle{yi-y_0\le\sum{t=2}^k w(v{j{t+1}}-v_{j_t})=\delta(v_0,v_i)}=x_i$。
也就是有$yi-y_0\le x_i$，由于$y_0=0$，因此$y_i\le x_i$。也就是说，对于所有$y$，都有$\displaystyle{\sum{i=1}^n yi\le\sum{i=1}^n x_i}$，因此原结论成立。
$\star$ 22.4-9
此处假设这个差分约束系统中不存在无解的情况，也就是约束图不存在负环。
由于Bellman-Ford算法在这个过程中求解的是最短路，因此随着整个松弛过程的进行，每个$x_i$都在减小。最终当$x_i=\delta(v_0,v_i)$时，$x_i$将不再减小。所有$x_i$都将最小化，也就是$\max{x_i}$最小化。
在最小化$\max{x_i}$的基础上，最小的$v_j.d$都应该最大化以确保从$v_0$到$v_j$的路径是一条真实的路径值。因此$\min{x_i}$被最大化。
在安排工程进度上，$\max{x_i}-\min{x_i}$相当于是最小化第一个工作开始到最后一个工作的这段时间。也就是通过合理安排这个工程内部的工作顺序，从而使得整个工程的时间最小化。
22.4-10
与当初的做法类似，考虑对约束图$G$添加额外原节点$v_0$，并且保证$x_0=\delta(v_0,v_0)=0$成立。
对于单个变量的约束条件$x_i\le b_k$，可以改写成$x_i-x_0\le b_k$，那么可以添加一条边$(v_0,v_i)$到$E$中，并且权值$w(v_0,v_i)=b_k$。
对于单个变量的约束条件$x_i\ge b_k$，可以改写成$x_0-x_i\le-b_k$，那么可以添加一条边$(v_i,v_0)$到$E$中，并且权值$w(v_i,v_0)=-b_k$。
接下来只需要对$G$以$v_0$为起点运行Bellman-Ford算法即可。如果$G$包含了负环，那么Bellman-Ford算法会报告这个约束系统无解。
22.4-11
对于所有$b_k$，令$b_k’=\lfloor b_k\rfloor$，那么可以求解新的差分约束系统$x_i-x_j\le b_k’$即可。此时依照Bellman-Ford算法，求解出来的结果必定是整数。并且，由于$x_i-x_j\le b_k’\le b_k$，因此这个约束实际上是比原约束条件更强，因此必定能求解出对应的结果。
$\star$ 22.4-12
和题目22.4-11的区别在于只要求部分$x_i$必须是整数。因此为每个节点$v$添加一个布尔属性is-int来表示当前节点所求距离是否必须为整数。在松弛时，如果$v.d$是整数，那么使用值$v.d=\lfloor u.d+w(u,v)\rfloor$进行松弛，否则正常松弛即可，从而使结果仍然满足不等式的条件。整个算法由DIFFERENCE-CONSTRAINTS-SOLVER'给出，其时间复杂度和Bellman-Ford算法相同，为$O(n^2+mn)$。
1 | RELAX''(u, v, w) |