Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:
x1 -x2 ≤1
x1 -x4 ≤-4
x2 -x3 ≤2
x2 -x5 ≤7
x2 -x6 ≤5
x3 -x6 ≤10
x4 -x2 ≤2
x5 -x1 ≤-1
x5 -x4 ≤3
x6 -x3 ≤-8
(-5, -3, 0, -1, -6, -8)
Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:
x1 -x2 ≤4
x1 -x5 ≤5
x2 -x4 ≤-6
x3 -x2 ≤1
x4 -x1 ≤3
x4 -x3 ≤5
x4 -x5 ≤10
x5 -x3 ≤-4
x5 -x4 ≤-8
没有解,因为x4 -> x2 -> x3 -> x5 -> x1 -> x4形成了一个负权回路.
Can any shortest-path weight from the new vertex v0 in a constraint graph be positive? Explain.
不可能为正数,因为最大已经是0了.不可能大于0.
Express the single-pair shortest-path problem as a linear program.
将G视为约束图，得到差分约束Ax<=b。设起点为i，终点为j，求解目标为 (xj - xi) 的最大值。
Show how to modify the Bellman-Ford algorithm slightly so that when it is used to solve a system of difference constraints with m inequalities on n unknowns, the running time is O(nm).
V0这个顶点和他的n条权值为0的边其实是没有意义的,一开始初始化的时候可以对所有的点v,令d[v] = 0.
Suppose that in addition to a system of difference constraints, we want to handle equality constraints of the form xi = xj + bk. Show how the Bellman-Ford algorithm can be adapted to solve this variety of constraint system.
xi >= xj + bk
xi <= xj + bk
Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm that runs on a constraint graph without the extra vertex v0.
同练习24.4-5
Let Ax ≤ b be a system of m difference constraints in n unknowns. Show that the Bellman- Ford algorithm, when run on the corresponding constraint graph, maximizes x1+x2+...+xn subject to Ax≤b and xi ≤0 for all xi.
先用Bellman-Ford算法找出一组解,然后找出(x1,x2,...xn)中最大的一个数假设为xi,然后加上d(d可能>0,= 0或者<0)变成0.其他数字也加上d.然后求和.
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system Ax ≤ b of difference constraints, minimizes the quantity (max {xi} - min {xi}) subject to Ax ≤ b. Explain how this fact might come in handy if the algorithm is used to schedule construction jobs.
UNSOLVED
Suppose that every row in the matrix A of a linear program Ax ≤ b corresponds to a difference constraint, a single-variable constraint of the form xi ≤ bk, or a single-variable constraint of the form -xi ≤ bk. Show how to adapt the Bellman-Ford algorithm to solve this variety of constraint system.
新造一个节点u,令约束条件变成xi - xu ≤ bk.
并且初始化d(u) = 0.
Give an efficient algorithm to solve a system Ax ≤ b of difference constraints when all of the elements of b are real-valued and all of the unknowns xi must be integers.
把所有的b向下取整。因为 xi - xj ≤ b 同时 xi - xj 是整数，可得 xi - xj 一定小于等于b向下取整。
Give an efficient algorithm to solve a system Ax ≤ b of difference constraints when all of the elements of b are real-valued and a specified subset of some, but not necessarily all, of the unknowns xi must be integers.
仍然采用最短路径算法，在松弛过程中，若有必要（x.v为整数），取 v.d = {(u.d + w(u, v)) 向下取整}。 证明： 假设这个算法得出的解（最短路径）不满足约束条件，更具体的，xi - xj > bm。 因为我们在松弛过程中，由于向下取整，导致实际取的 v.d ≤ u.d + w(u, v)，而如果取 v.d = u.d + w(u, v) 结果是满足约束条件的，可知一定是j点得最短路径取小了。 另一方面，原来的约束 xi - xj ≤ bm 在约束图中是点j到点i的路径。如果i点在j点之前已经取得最短路径，对j点的循环过程会导致i点最短路径更短，可知i点一定在j点之后取得最短路径。根据松弛过程可知，算出的i点的最短路径一定满足约束，即 xi - xj ≤ bm。 与假设矛盾。 因此，按照该方法算出的结果一定是一个可行解。
Follow @louis1992 on github to help finish this task.
本节部分答案参考自这里