`

差分约束系统

阅读更多
(本文假设读者已经有以下知识:最短路径的基本性质、Bellman-Ford算法。)
    比如有这样一组不等式:
  
X1 - X2 <= 0
X1 - X5 <= -1
X2 - X5 <= 1
X3 - X1 <= 5
X4 - X1 <= 4
X4 - X3 <= -1
X5 - X3 <= -3
X5 - X4 <= -3
不等式组(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,于是这个差分约束系统中就多出了下列不等式:
   
X1 - X0 <= 0
X2 - X0 <= 0
X3 - X0 <= 0
X4 - X0 <= 0
X5 - X0 <= 0
不等式组(2)

    对于这5个不等式,也在图中建出相应的边。最后形成的图如下:


图1

    图中的每一条边都代表差分约束系统中的一个不等式。现在以V0为源点,求单源最短路径。最终得到的V0到Vn的最短路径长度就是Xn的一个解啦。从图1中可以看到,这组解是{-5, -3, 0, -1, -4}。当然把每个数都加上10也是一组解:{5, 7, 10, 9, 6}。但是这组解只满足不等式组(1),也就是原先的差分约束系统;而不满足不等式组(2),也就是我们后来加上去的那些不等式。当然这是无关紧要的,因为X0本来就是个局外人,是我们后来加上去的,满不满足与X0有关的不等式我们并不在乎。
    也有可能出现无解的情况,也就是从源点到某一个顶点不存在最短路径。也说是图中存在负权的圈。这一点我就不展开了,请自已参看最短路径问题的一些基本定理。

    其实,对于图1来说,它代表的一组解其实是{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)

    所以建图的时候要先把所有不等式化成大于等于号的。其它各种过程,包括证明为什么解出的是最小值的证法,都完全类似。
   
    用到差分约束系统的题目有ZJU 2770,祝好运。
分享到:
评论

相关推荐

    差分约束系统详解.doc

    差分约束系统是一种用于建模和解决一系列线性不等式问题的方法,这些不等式通常涉及一组变量的差的约束。系统的核心在于其线性规划矩阵 A,它定义了变量之间的关系。在这个系统中,矩阵 A 的每一行包含一个 1、一个 ...

    Bellman-Ford算法与差分约束系统.ppt

    Bellman-Ford算法与差分约束系统

    差分约束系统例题详解[总结].pdf

    差分约束系统(Differential Constraint System, 简称DCS)是一种在算法和数学规划中常见的模型,用于处理一系列变量间的关系。在这个例题中,我们面对的是一个序列的子序列约束问题,需要找到满足所有约束条件的序列...

    详细差分约束系统详解

    详细差分约束系统详解 差分约束系统是线性规划的一种特殊形式,通过约束图和 Bellman-Ford 算法来解决。下面将详细介绍差分约束系统的定义、约束图、解法和应用。 定义 差分约束系统是一种特殊的线性规划问题,...

    冯威《数与图的完美结合——浅析差分约束系统》

    冯威《数与图的完美结合——浅析差分约束系统》

    数与图的完美结合 -------浅析差分约束系统

    差分约束系统是一种在计算机科学和数学中用于解决优化问题的模型,特别是在运筹学、图论和信息学竞赛等领域有着广泛应用。它将一组线性不等式与图论的概念相结合,通过构建网络来简化复杂问题,使得我们可以利用图...

    差分约束系统例题详解

    差分约束系统是一种在计算机科学和数学中用于解决优化问题的方法,特别是在图论和最优化领域。它通过定义变量之间的差异关系来建模问题,通常用于处理线性不等式系统。在这个例题中,差分约束系统被用来解决一个序列...

    图论- 差分约束系统.rar

    在图论中,差分约束系统(Differential Constraint System,DCS)是一种特殊的模型,广泛应用于路径规划、网络流问题、机器人运动规划等领域。本文将深入探讨差分约束系统的概念、性质以及它们在实际问题中的应用。 ...

    差分约束系统详解

    差分约束系统是一种用于建模和解决线性不等式约束问题的方法,它涉及到一系列变量之间的差异关系。在这样的系统中,线性规划矩阵 \( A \) 的结构特殊,每行包含一个 1 和一个 -1,其余元素为 0。这种结构确保了约束...

    差分约束系统题解1

    【差分约束系统】是一种用于解决一系列线性不等式约束问题的模型,常用于最优化问题,如求解最短路径、最长路径或者判断是否存在满足条件的解。在这个模型中,我们通常需要将问题转化为寻找图中的最短路径或最长路径...

    差分约束系统 2024年1月6日

    差分约束系统是一种用于处理线性不等式约束的数学模型,主要应用于寻找变量之间的最大或最小差值。在这个系统中,我们有n个变量x[0], x[1], ..., x[n-1]和m个不等式,每个不等式的形式为x[i] - x[j] [k],其中a[k]是...

    ACM 程序设计:图论2 最短路径 差分约束系统-1.pdf

    【ACM程序设计:图论2 最短路径 差分约束系统-1.pdf】这篇文档主要探讨了在图论中的最短路径问题,并且引入了差分约束系统这一概念,这是在解决某些优化问题时非常重要的工具。在这个特定的问题中,最短路径问题被...

    MIT算法导论公开课之课程笔记 18.最短路径算法、Bellman和差分约束系统.rar

    最短路径算法、Bellman和差分约束系统》 在计算机科学中,寻找最短路径问题是一个常见的优化问题,广泛应用于网络路由、交通规划、社交网络分析等领域。本篇笔记主要探讨了两种解决这类问题的经典算法:Dijkstra...

    冯威-浅析差分约束系统.ppt

    冯威-浅析差分约束系统.ppt

    ACM 程序设计:图论2 最短路径 差分约束系统-p6.pdf

    在ACM程序设计中,图论是一门重要的理论基础,特别是在解决实际问题时,如本题所述的"最短路径"和"差分约束系统"。在这个特定的问题中,我们面临的是一个寻找最安全路径的问题,而非通常意义上的最短路径。问题背景...

    POJ2983-Is the Information Reliable【差分约束+优化Bellman】

    北京大学在线编程平台上的POJ2983题目——"Is the Information Reliable",是一道涉及差分约束系统(Differential Constraint System)与优化版Bellman算法的典型问题。在本文中,我们将深入探讨这两个概念,并结合...

    1751【差分约束】Intervals(区间)[借鉴].pdf

    解题的关键在于将问题转化为差分约束系统,这是一个由一系列不等式组成的系统,每个不等式描述了变量之间的关系。对于这个问题,我们可以定义一个数组s[x],表示从0到x的点集中元素的个数。那么,区间[ai, bi]需要的...

    ACM 程序设计:图论2 最短路径 差分约束系统-p1.pdf

    图论与最短路径算法在 ACM 程序设计中的应用 在 ACM 程序设计中,图论和最短路径算法是两大重要的知识点。本文将通过一个具体的例子来介绍这两个概念,并对其在程序设计中的应用进行详细的解释。...

Global site tag (gtag.js) - Google Analytics