当前位置:网站首页>Difference Constraint - Graph Theory
Difference Constraint - Graph Theory
2022-08-09 07:05:00 【swust_fang】
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.
边栏推荐
猜你喜欢
随机推荐
Quectel EC20 4G module dial related
【模板】树链剖分 P3384
高项 01 信息化与信息系统
类和结构体
2019南昌网络赛 C题,Hello 2019
Common Oracle Commands
数据一致性架构
MVN 中配置flyway mysq
(本章节完结)排序第五节——非比较排序(计数排序+基数排序+桶排序)(附有自己的视频讲解)
洛谷P1110 报表统计 multiset stl好题
无重复的字符的最长子串
浅识微服务架构
MUI无法滚动?完美解决
虚拟机网卡报错:Bringing up interface eth0: Error: No suitable device found: no device found for connection
Built-in macros in C language (define log macros)
【ROS2原理8】节点到参与者的重映射
Lottie系列三 :原理分析
Zero shift of leetcode
Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
移远EC20 4G模块拨号相关