专栏首页owent关于差分约束(转载)

关于差分约束(转载)

关于差分约束(转载)

(本文假设读者已经有以下知识:最短路径的基本性质、Bellman-Ford算法。) 比如有这样一组不等式:

$$ \begin{cases} X1 - X2 <= 0 \\ X1 - X5 <= (-1) \\ X2 - X5 <= 1 \\ X3 - X1 <= 5 \\ X4 - X1 <= 4 \\ X4 - X3 <= (-1) \\ X5 - X3 <= (-3) \\ X5 - X4 <= (-3) \end{cases} $$(1)

全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘以-1就可以化成小于等于)。这样的不等式组就称作差分约束系统。 这个不等式组要么无解,要么就有无数组解。因为如果有一组解{X1, X2, …, Xn}的话,那么对于任何一个常数k,{X1 + k, X2 + k, …, Xn + k}肯定也是一组解,因为任何两个数同时加一个数之后,它们的差是不变的,那么这个差分约束系统中的所有不等式都不会被破坏。

差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。即对于任何一条边u -> v,都有:

d(v) <= d(u) + w(u, v)

其中d(u)和d(v)是从源点分别到点u和点v的最短路径的权值,w(u, v)是边u -> v的权值。 显然以上不等式就是d(v) – d(u) <= w(u, v)。这个形式正好和差分约束系统中的不等式形式相同。于是我们就可以把一个差分约束系统转化成一张图,每个未知数Xi对应图中的一个顶点Vi,把所有不等式都化成图中的一条边。对于不等式Xi – Xj <= c,把它化成三角形不等式:Xi <= Xj + c,就可以化成边Vj -> Vi,权值为c。最后,我们在这张图上求一次单源最短路径,这些三角形不等式就会全部都满足了,因为它是最短路径问题的基本性质嘛。 话说回来,所谓单源最短路径,当然要有一个源点,然后再求这个源点到其他所有点的最短路径。那么源点在哪呢?我们不妨自已造一个。以上面的不等式组为例,我们就再新加一个未知数X0。然后对原来的每个未知数都对X0随便加一个不等式(这个不等式当然也要和其它不等式形式相同,即两个未知数的差小于等于某个常数)。我们索性就全都写成Xn – X0 <= 0,于是这个差分约束系统中就多出了下列不等式:

$$ \begin{cases} X1 - X0 <= 0 \\ X2 - X0 <= 0 \\ X3 - X0 <= 0 \\ X4 - X0 <= 0 \\ X5 - X0 <= 0 \end{cases} $$(2)

对于这5个不等式,也在图中建出相应的边。每一条边都代表差分约束系统中的一个不等式。现在以V0为源点,求单源最短路径。最终得到的V0到Vn的最短路径长度就是Xn的一个解啦。从图1中可以看到,这组解是{-5, -3, 0, -1, -4}。当然把每个数都加上10也是一组解:{5, 7, 10, 9, 6}。但是这组解只满足不等式组(1),也就是原先的差分约束系统;而不满足不等式组(2),也就是我们后来加上去的那些不等式。当然这是无关紧要的,因为X0本来就是个局外人,是我们后来加上去的,满不满足与X0有关的不等式我们并不在乎。

也有可能出现无解的情况,也就是从源点到某一个顶点不存在最短路径。也说是图中存在负权的圈。这一点我就不展开了,请自已参看最短路径问题的一些基本定理。

其实,它代表的一组解其实是{0, -5, -3, 0, -1, -4},也就是说X0的值也在这组解当中。但是X0的值是无可争议的,既然是以它作为源点求的最短路径,那么源点到它的最短路径长度当然是0了。因此,实际上我们解的这个差分约束系统无形中又存在一个条件:

X0 = 0 > 也就是说在不等式组(1)、(2)组成的差分约束系统的前提下,再把其中的一个未知数的值定死。这样的情况在实际问题中是很常见的。比如一个问题表面上给出了一些不等式,但还隐藏着一些不等式,比如所有未知数都大于等于0或者都不能超过某个上限之类的。比如上面的不等式组(2)就规定了所有未知数都小于等于0。 > > 对于这种有一个未知数定死的差分约束系统,还有一个有趣的性质,那就是通过最短路径算法求出来的一组解当中,所有未知数都达到最大值。下面我来粗略地证明一下,这个证明过程要结合Bellman-Ford算法的过程来说明。 > > 假设X0是定死的;X1到Xn在满足所有约束的情况下可以取到的最大值分别为M1、M2、……、Mn(当然我们不知道它们的值是多少);解出的源点到每个点的最短路径长度为D1、D2、……、Dn。 > > 基本的Bellman-Ford算法是一开始初始化D1到Dn都是无穷大。然后检查所有的边对应的三角形不等式,一但发现有不满足三角形不等式的情况,则更新对应的D值。最后求出来的D1到Dn就是源点到每个点的最短路径长度。 > > 如果我们一开始初始化D1、D2、……、Dn的值分别为M1、M2、……、Mn,则由于它们全都满足三角形不等式(我们刚才已经假设M1到Mn是一组合法的解),则Bellman-Ford算法不会再更新任合D值,则最后得出的解就是M1、M2、……、Mn。 > > 好了,现在知道了,初始值无穷大时,算出来的是D1、D2、……、Dn;初始值比较小的时候算出来的则是M1、M2、……、Mn。大家用的是同样的算法,同样的计算过程,总不可能初始值大的算出来的结果反而小吧。所以D1、D2、……、Dn就是M1、M2、……、Mn。 > > 那么如果在一个未知数定死的情况下,要求其它所有未知数的最小值怎么办?只要反过来求最长路径就可以了。最长路径中的三角不等式与最短路径中相反:

$$ d(v) >= d(u) + w(u, v) $$

也就是 $$ d(v) - d(u) >= w(u, v) $$

所以建图的时候要先把所有不等式化成大于等于号的。其它各种过程,包括证明为什么解出的是最小值的证法,都完全类似。 摘自:http://hi.baidu.com/phecy/blog/item/6583cf81d25e0edebc3e1ef3.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 简单C++单元测试框架(支持一键切到GTest或Boost.Test)

    众所周知,单元测试对于持续集成和变更的检测是十分重要的。 这个单元测试框架本是用于之前规划的C++协程框架使用的。 虽然已经有比较成熟的单元测试框架GTes...

    owent
  • ECUST 09年 校赛个人赛第六,七场总结

    owent
  • [libiniloader] Project

    Github地址: https://github.com/owt5008137/libiniloader

    owent
  • SDN应用路由算法实现工具之Networkx

    SDN(Software Defined Networking)是一种新型的网络架构,通过集中式的控制平面管理数据层面的转发等操作。网络的连通性是最基础的需求,...

    SDNLAB
  • 解读 | NVIDIA Turing 架构解析:追光逐影,成败未定

    AI 科技评论消息,自NVIDIA的Turing架构问世已经过去了一个多月时间,GeForce RTX 20系列的发布以及实时光线跟踪技术的推出,让NVIDIA...

    AI科技评论
  • 深度学习在医疗诊断领域优势明显,数据质量将成AI未来发展瓶颈

    人工智能正在改变医疗诊断行业 今年年初,谷歌成功研发出一套用于乳腺癌诊断的人工智能系统。这套系统分析了大量的病理组织显微图像,速度比人类快得多,且肿瘤检出率高达...

    企鹅号小编
  • Java基础-25(05)图形用户界面编程GUI

    package cn.itcast.view;(6) import cn.itcast.dao.UserDao; import cn.itcast.dao.i...

    Java帮帮
  • 前端开发路线图——从小白到前端工程师

    编者按:很多人都想学编程。但是苦于没有具体的步骤和指导。比如想找份前端开发的工作,却不知道应该先学习什么再学习什么,也不知道该选择什么样的工具。因为经常被人问到...

    笔阁
  • 数据结构与算法——稀疏数组

    当一个数组(包括多维数组)中的大部分元素为0或者为同一个数值的数组时,为了节约空间起到压缩的效果,将数据用另一种结构来表示,即稀疏数组。

    C you again 的博客
  • MySQL timestamp NOT NULL插入NULL的问题

    如果该参数不开启,则对timestamp NOT NULL插入NULL值,不报错,无warning,插入后的值为当前时间

    爱撸猫的杰

扫码关注云+社区

领取腾讯云代金券