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.
UNSOLVED(等写到LP再来解决)
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.
UNSOLVED
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.
UNSOLVED
Follow @louis1992 on github to help finish this task.
本节部分答案参考自这里