Difference Constraint - Graph Theory

Differential Constraint System

I. What is a differential constraint system:

A system of difference constraints is a method of solving a special set of inequalities with respect to a set of variables.If a system consists of n variables and m constraints, each of which has the form xj-xi<=bk(i,j∈[1,n],k∈[1,m]), then it is calledis a system of difference constraints.That is, a differential constraint system is a method of solving a special set of inequalities with respect to a set of variables.

In layman's terms, a differential constraint system is a group of inequalities, and our goal is to find the maximum or minimum value or whether the differential constraint system has a solution through a given set of constraint inequalities.

For example:

Second, the solution of the differential constraint system:

The differential constraint system can be converted into graph theory to solve, corresponding to the above inequality group, if the maximum value of x3-x0 is required, the superposition inequality can be deduced that x3-x0<=7, the maximum value is 7,We can build a graph with 6 vertices, and for each xj-xi<=bk, create a directed edge from i to j with a weight of bk.By finding the shortest path from x0 to x3 of this graph, we can know that it is also 7. Is this a coincidence?Not really.

The reason why the differentially constrained system can be solved by the shortest path of graph theory is because xj-xi<=bk, it will be found that it is similar to the triangular inequality d[v] <=d[u]+w[ in the shortest pathu,v], that is, d[v]-d[u]<=w[u,v].The process of finding the maximum value is similar to the relaxation process in the shortest path algorithm.

Triangular inequality: (quote Daniel's blog here)

B - A <= c (1)

C - B <= a (2)

C - A <= b (3)

If the maximum value of C-A is required, you can know that max(C-A) = min(b, a+c), which corresponds to the shortest path from C to A in the figure below.

Therefore, to generalize the triangle inequality, there are n variables and m inequalities, and the maximum value of xn-x1 is required, which is to find the shortest path after the map is constructed.

Similarly, if it is required to take the minimum value of xn-x1 in the differential constraint system, it is to find the longest path after mapping.The longest path can be found by spfa, just change the direction of relaxation, ie if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u, v).Of course, we can negate all edge weights in the graph to find the shortest path, and the two are equivalent.

The longest path solution algorithm is proved as follows:

http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html

Finally, there may not be the shortest/longest path after the map is built, because there may be negative/positive loops that decrease/increase infinitely, and the questions generally correspond to different outputs.It is enough to judge whether the differential constraint system has a solution general loop.

3. Application of differential constraint system

Differential constraint systems are widely used and all have a certain background. We only need to construct a differential constraint system according to the meaning of the problem, and then solve it according to the requirements of the problem.

There are three situations in general questions: (1), finding the shortest path (2), finding the longest path (3), judging whether the solution of the differential constraint system exists

Of course these three may also be combined with each other.

The solution of the differentially constrained system is as follows:

1. According to the conditions, express the meaning of the question through the variable group to obtain the inequality group. Pay attention to discover the implicit inequality, such as the implicit inequality relationship between the two variables before and after.

2. Make a map:

First, standardize the inequality group according to the requirements of the title.

(1) If the minimum value is required, then the longest path is found, then all the inequalities are converted into the form of xi – xj >= k, so that the edge of j->i is established, and the weight is kIf there is xi – xj > k in the inequality group, because the general problem is a constraint on the integer variable, it can be transformed into xi – xj >= k+1. If xi – xj=k, then it can be changed toThe following two: xi – xj >= k, xi – xj <= k, further change to xj – xi>= -k, just create two edges.

(2) If the maximum value is obtained, then the shortest path is obtained, and all the inequalities are converted into the form of xi – xj <= k, so that the edge of j->i is established, and the weight is k, if it is like the above two cases, then the same normalization will do.

(3) If you want to judge whether there is a solution in the differential constrained system, it is generally a judgment loop. You can choose to find the shortest path or the longest path, but the inequality standardization is different.Spfa is enough. If the same point is enqueued more than n times among n points, then there is a ring.

It is worth noting that the created graph may not be connected, we only need to add a super source point, for example, if the graph is not connected when finding the longest path, we only need to add a point S, rightEach other point establishes an edge graph with a weight of 0 to be connected, and then starts from the S point to perform the spfa judgment ring.The shortest path is similar.

3. After the graph is built, it can be solved directly by spfa or bellman-ford. The dijstra algorithm cannot be used, because there are generally negative edges, so pay attention to the initialization problem.