算法学习之路|差分约束系统

  1. 云栖社区>
  2. 博客列表>
  3. 正文

算法学习之路|差分约束系统

kissjz 2018-02-23 23:57:51 浏览103 评论0

摘要: 差分约束系统实际上是一种转化,把某些问题转化成最短路问题来进行求解

差分约束系统实际上是一种转化,把某些问题转化成最短路问题来进行求解
差分约束系统解决的问题是不等式的求解:
例如:
x2-x0<=3;
x4-x2<=2;
x3-x0<=5;
x1-x0<=4;
x3-x1<=1;
x4-x3<=1;
x3-x2<=3;
如果要求x4-x0的不等式解,显然可用不等式俩俩相加的方法求,求出是:
x4-x0<=5,x4-x0<=6;x4-x0<=7这三个式子显然最后求交集(ˇˍˇ) x4-x0<=5
我们可以这么看,x0~x4为图上五个点,xj-xi为i到j的距离这样就建立了一个有向图

显然x0到x4的路径有5,6,6,7四条最短的路为5
如若一个系统由n个变量和m个不等式组成,并且这m个不等式对应的系数矩阵中每一行有且仅有一个1和-1,其它的都为0,这样的系统称为差分约束( difference constraints )系统。
例如

如果还不清楚的话看看三角不等式:
给出三个不等式:
B - A <= c (1)
C - B <= a (2)
C - A <= b (3)
可以得到图
我们发现min{b, a+c}正好对应了A到C的最短路,而这三个不等式就是著名的三角不等式。将三个不等式推广到m个,变量推广到n个,就变成了n个点m条边的最短路问题了。
解的存在性
如果转化的的图中存在负权的回路先让就不会有解,因为负的回路会一直循环下去直到无穷小,这样就不可能有解
还有一种是两点之间不可达,这样最短路径为无穷大,此时有无限个解

用云栖社区APP,舒服~

【云栖快讯】云栖社区技术交流群汇总,阿里巴巴技术专家及云栖社区专家等你加入互动,老铁,了解一下?  详情请点击

网友评论

kissjz
文章244篇 | 关注76
关注
阿里云机器学习是基于阿里云分布式计算引擎的一款机器学习算法平台。用户通过拖拉拽的方式可视化的... 查看详情
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
建站4折

建站4折