算法导论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{d_v=\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\)。
对于任意一组解\((y_1,y_2,\dots,y_n)\)，我们需要证明\(y_i\le x_i\)均成立。 对于任意\(v_i\in V-\{v_0\}\)，以及任意一条从\(v_0\)到\(v_i\)的一条最短路径\(v_{j_1},u_{v_{j_2}},\dots,v_{j_k}\)，其中\(j_1=0,j_k=i\)，对于所有\(t=2,3,\dots,k\)，都有\(y_{j_{t+1}}-y_{j_t}\le w(v_{j_{t+1}}-v_{j_t})\)均成立。
因此将这\(k-1\)条不等式左右分别相加，得到\(\displaystyle{y_i-y_0\le\sum_{t=2}^k w(v_{j_{t+1}}-v_{j_t})=\delta(v_0,v_i)}=x_i\)。
也就是有\(y_i-y_0\le x_i\)，由于\(y_0=0\)，因此\(y_i\le x_i\)。也就是说，对于所有\(y\)，都有\(\displaystyle{\sum_{i=1}^n y_i\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) |