当前位置:网站首页>差分约束-图论
差分约束-图论
2022-08-09 07:01:00 【swust_fang】
差分约束系统
一、何为差分约束系统:
差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如:
二、差分约束系统的求解:
差分约束系统可以转化为图论来解决,对应于上面的不等式组,如果要求出x3-x0的最大值的话,叠加不等式可以推导出x3-x0<=7,最大值即为7,我们可以通过建立一个图,包含6个顶点,对每个xj-xi<=bk,建立一条i到j的有向边,权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7,这是巧合吗?并不是。
之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式:(在此引用大牛的博客)
B - A <= c (1)
C - B <= a (2)
C - A <= b (3)
如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。
因此,对三角不等式加以推广,变量n个,不等式m个,要求xn-x1的最大值,便就是求取建图后的最短路。
同样地,如果要求取差分约束系统中xn-x1的最小值,便是求取建图后的最长路。最长路可以通过spfa求出来,只需要改下松弛的方向即可,即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负,求取最短路,两者是等价的。
最长路求解算法证明如下:
http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html
最后一点,建图后不一定存在最短路/最长路,因为可能存在无限减小/增大的负环/正环,题目一般会对应于不同的输出。判断差分约束系统是否存在解一般判环即可。
3、差分约束系统的应用
差分约束系统的应用很广,都会有一定的背景,我们只需要根据题意构造出差分约束系统,然后再根据题目的要求求解就行了。
一般题目会有三种情况:(1)、求取最短路 (2)、求取最长路 (3)、判断差分约束系统的解是否存在
当然这三种也可能会相互结合。
差分约束系统的解法如下:
1、 根据条件把题意通过变量组表达出来得到不等式组,注意要发掘出隐含的不等式,比如说前后两个变量之间隐含的不等式关系。
2、 进行建图:
首先根据题目的要求进行不等式组的标准化。
(1)、如果要求取最小值,那么求出最长路,那么将不等式全部化成xi – xj >= k的形式,这样建立j->i的边,权值为k的边,如果不等式组中有xi – xj > k,因为一般题目都是对整形变量的约束,化为xi – xj >= k+1即可,如果xi – xj = k呢,那么可以变为如下两个:xi – xj >= k, xi – xj <= k,进一步变为xj – xi >= -k,建立两条边即可。
(2)、如果求取的是最大值,那么求取最短路,将不等式全部化成xi – xj <= k的形式, 这样建立j->i的边,权值为k的边,如果像上面的两种情况,那么同样地标准化就行了。
(3)、如果要判断差分约束系统是否存在解,一般都是判断环,选择求最短路或者最长路求解都行,只是不等式标准化时候不同,判环地话,用spfa即可,n个点中如果同一个点入队超过n次,那么即存在环。
值得注意的一点是:建立的图可能不联通,我们只需要加入一个超级源点,比如说求取最长路时图不联通的话,我们只需要加入一个点S,对其他的每个点建立一条权值为0的边图就联通了,然后从S点开始进行spfa判环。最短路类似。
3、 建好图之后直接spfa或bellman-ford求解,不能用dijstra算法,因为一般存在负边,注意初始化的问题。
边栏推荐
- 2022 年全球十大最佳自动化测试工具
- Simple to use Lambda expressions
- shardingsphere data sharding configuration item description and example
- 买口罩(0-1背包)
- 入门cv必读的10篇baseline论文
- 【MySQL】update mysql.user set authentication_string=password(“123456“) where User=‘root‘; 报错
- XILINX K7 FPGA+RK3399 PCIE驱动调试
- list与string转换
- rsync:recv_generator: mkdir (in backup) failed:Permission denied (13) |failed to set times on '.'
- 多米诺骨牌
猜你喜欢
Search 1688 product interface by image (item_search_img-search 1688 product by image (Politao interface) code docking tutorial
6 states of a thread
The solution that does not work and does not take effect after VScode installs ESlint
【Oracle 11g】Redhat 6.5 安装 Oracle11g
Error jinja2.exceptions.UndefinedError: 'form' is undefined
网络学习总结
排序第四节——归并排序(附有自己的视频讲解)
Inception V3 闭眼检测
Flask failed to create database without error
Fragments
随机推荐
imageio读取.exr报错 ValueError: Could not find a backend to open `xxx.exr‘ with iomode `r`
2022-08-08: Given an array arr, it represents the height of the missiles that will appear in order from morning to night.When the cannon shoots missiles, once the cannon is set to shoot at a certain h
顺序表删除所有值为e的元素
Use baidu EasyDL intelligent bin
Introduction and use of BeautifulSoup4
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
sklearn数据预处理
网络学习总结
子路由及路由出口配置
单例 DCL(double check lock) 饱汉模式和饿汉模式
高项 03 项目立项管理
APP product source data interface (taobao, jingdong/spelling/suning/trill platform details a lot data analysis interface) code and docking tutorial
failed (13: Permission denied) while connecting to upstream
C language implements sequential stack and chain queue
找出数组中不重复的值php
cut命令的使用实例
longest substring without repeating characters
排序第一节——插入排序(直接插入排序+希尔排序)(视频讲解26分钟)
高项 04 项目变更管理
【ROS2原理8】节点到参与者的重映射