- 浏览: 1637551 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (405)
- C/C++ (16)
- Linux (60)
- Algorithm (41)
- ACM (8)
- Ruby (39)
- Ruby on Rails (6)
- FP (2)
- Java SE (39)
- Java EE (6)
- Spring (11)
- Hibernate (1)
- Struts (1)
- Ajax (5)
- php (2)
- Data/Web Mining (20)
- Search Engine (19)
- NLP (2)
- Machine Learning (23)
- R (0)
- Database (10)
- Data Structure (6)
- Design Pattern (16)
- Hadoop (2)
- Browser (0)
- Firefox plugin/XPCOM (8)
- Eclise development (5)
- Architecture (1)
- Server (1)
- Cache (6)
- Code Generation (3)
- Open Source Tool (5)
- Develope Tools (5)
- 读书笔记 (7)
- 备忘 (4)
- 情感 (4)
- Others (20)
- python (0)
最新评论
-
532870393:
请问下,这本书是基于Hadoop1还是Hadoop2?
Hadoop in Action简单笔记(一) -
dongbiying:
不懂呀。。
十大常用数据结构 -
bing_it:
...
使用Spring MVC HandlerExceptionResolver处理异常 -
一别梦心:
按照上面的执行,文件确实是更新了,但是还是找不到kernel, ...
virtualbox 4.08安装虚机Ubuntu11.04增强功能失败解决方法 -
dsjt:
楼主spring 什么版本,我的3.1 ,xml中配置 < ...
使用Spring MVC HandlerExceptionResolver处理异常
(本文假设读者已经有以下知识:最短路径的基本性质、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,祝好运。
比如有这样一组不等式:
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,祝好运。
发表评论
-
二分查找之变型题目
2010-10-24 12:40 2115二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就 ... -
一道笔试题(创新工厂)解法
2010-10-21 17:44 1814一个帖子http://www.iteye.com/topic/ ... -
[zz]大数据量,海量数据 处理方法总结
2010-08-27 22:24 2241大数据量的问题是很多面试笔试中经常出现的问题,比如baidu ... -
Trie and suffix array
2010-04-13 20:54 1897字典数Trie和后缀数组suffix array是处理字符串操 ... -
金币问题
2009-11-09 08:41 1988今年某公司的笔试题: 一个矩阵地图,每一个元素值代表金币数, ... -
楼梯问题
2009-11-09 08:19 1543hl给我的几道某公司的算法题: 1、 有个 100 级的 ... -
一道考察模拟乘法的题目
2009-11-07 22:37 1395今天hl和我讨论一道题目: 写道 整形数组如a={1,4, ... -
链表归并
2009-11-07 21:40 1001以前gx同学问的某某公司的笔试题,写一下练练(纯手写,没编译过 ... -
找出出现次数超过一半的数字
2009-11-07 21:23 1863hl同学问我一道这个题,想了一种方法,感觉还是不错的,只扫描一 ... -
有道难题以超低分晋级
2009-06-10 11:36 1529有道难题比赛居然晋级了,可以领到一个t-shirt。 -
逆序数/逆序数对
2009-06-09 23:17 3733逆序数是个常遇到的问题,主要有两种解法: O(n^2)的方法: ... -
有道难题topcoder
2009-05-31 23:55 2426今天做了有道topcoder的题目,也是第一次在topcode ... -
百度之星第一场题目
2009-05-31 00:03 3589由于不符合参赛条件,未能参加百度之星,看了题目还挺有意思,把题 ... -
一个对字符串很好的Hash函数ELFHHash
2009-05-03 21:41 2239#include<stdio.h> #defin ... -
最大流Ford-Fulkerson算法
2009-04-22 17:33 9625算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford- ... -
大数/高精度加减乘除取模[收藏]
2009-04-16 19:38 5025#include <iostream> #i ... -
带重复数字的全排列
2009-04-16 18:58 3858上次gx同学问我一道又重复数字的全排列的问题,我当时用set保 ... -
二分图匹配
2009-04-15 15:40 3698二分图最大匹配的匈牙利算法 二分图是这样一个图,它的顶点可以分 ... -
线段树
2009-03-24 10:58 1654把问题简化一下: 在自然数,且所有的数不大于30000的 ... -
树状数组
2009-03-24 10:39 2305树状数组是一种非常优雅的数据结构. 当要频繁的对数 ...
相关推荐
Bellman-Ford算法与差分约束系统
差分约束系统详解(system of difference constraints)
差分约束系统例题详解[总结].pdf
冯威《数与图的完美结合——浅析差分约束系统》
差分约束系统详解!!详细介绍差分约束系统
这里我们介绍一种方法,它很好地将某些特殊的不等式组与图相联结,让复杂的问题简单化,将难处理的问题用我们所熟知的方法去解决,它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-...
差分约束系统例题详解,是很好的一种解题方法
差分约束系统(system of difference constraints)详解,解释了如何实现该算法及算法复杂度。
图论- 差分约束系统.rar
差分约束系统 2024年1月6日
冯威-浅析差分约束系统.ppt
ACM 程序设计:图论2 最短路径 差分约束系统-p1.pdf
ACM 程序设计:图论2 最短路径 差分约束系统-p6.pdf
ACM 程序设计:图论2 最短路径 差分约束系统-1.pdf
MIT算法导论公开课之课程笔记 18.最短路径算法、Bellman和差分约束系统.rar
第一行一个正整数 N 第一行一个整数 N 第一行是三个空格分隔的整数 N、ML 和 MD 第二种是手工入队,然后初始化 Dist 数组为 第一行一个整数,表示测
基于SDC特征和GMM-UBM模型的语种识别系统,徐婷婷,,本文提出了一种基于SDC特征和改进的GMM-UBM 模型的自动语种识别方法。SDC特征由许多语音帧的一阶差分谱连接扩展而成,与传统的MFCC特征
+ [差分约束系统](#差分约束系统) + [平面图](#平面图) + [2-SAT](#2-sat) + [最小生成树](#最小生成树) + [二分图](#二分图) + [Voronoi图](#voronoi图) + [偶图](#偶图) * [树](#树) + [树](#树-1) + ...