如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如:xj-xi<=bk,其中,1<=i,j<=n, 1<=k<=m。则称其为差分约束系统(System of difference constraints)。差分约束系统就是求解关于一组变量的不等式组的方法。
求解差分约束系统,可以转化为图论中的单源最短路径问题。
观察约束条件xj-xi<=bk,会发现它类似于最短路中的三角不等式d[u]<=d[v]+w[u,v](即d[u]-d[v]<=w[u,v])。因此,以每个变量xi为结点,对于约束条件xj-xi<=bk,连接一条边(i,j),边权为bk。再增加一个源点s,s与所有的点相连,边权为0。对这个图,运行以s为起点的bellman-ford(或者spfa),最终{d[i]}即为一组可行解。
引理:设x=(x1,x2,…,xn)是差分约束系统Ax≤b的一个解,d为任意常数。则x+d=(x1+d,x2+d,…,xn+d)也是该系统Ax≤b的一个解。
poj3159:发苹果问题。flymouse是班长,他需要给每个同学发一定数量的苹果,但是学生之间会有比较,有的学生(编号为a)认为某个学生b的苹果数不能超过他v个(Sb-Sa<=v)。flymouse的编号为1,现在要求满足学生要求,并且使S1 - Sn最大。
解:从a到b连接一条有向边,权值为v。以1为起始点,求到每个点的最短路径,最终dis[n]即为所求。
poj1364:有一个国王,它只会算连续的数的加法,假设一串数{a1,a2,...an},给出条件si,ni,operator,ki,意思是从si到si+ni这段数的和>或者<ki。现在又n组这样的条件,判断这些条件是否存在矛盾。
解:设S[i]表示从串开头1到i的和,S[0]=0,则条件可转化为:S[ni+si] - S[si-1] > ki(or <)。由于S[i]均为整数,可以转化为:S[ni+si] - S[si-1] >= ki + 1(or <= ki-1)。先将条件全部转化为<=形式,再添加超级源点n+1,到其余各点连接一条边,权值为0。利用spfa判断负环的存在。
poj2983:有两个敌对势力,a方想弄清楚b方的n个防御站的位置,通过一些地下组织。地下组织提供多条情报,你要判断这些情报是否可靠。情报分为两种:P A B X:A站在B站北边X公里;V A B:A站在B站北边至少1公里,但具体多远不清楚。现在给出n个站和m条情报,判断这m条情报是否可靠。
解:设S[i]表示i站距离最南边的距离,S[0]=0,则情报可以转化为S[A]-S[B]<=X&&S[A]-S[B]>=X;S[A] - S[B]>=1。首先将这些不等式全部转化为<=,求最短路用bellmanford判断负环。
poj1201:给出n(n=50000)段连续的整数(整数均小于50000),要求出一个最小的集合Z,至少包含第i段里面ci个数。
解:S[i]表示Z集合从0到i-1中取的整数的个数。对于段[a,b]取不小于c个数,则有:S[b+1]-S[a]>=c。显然,这是求最长路。(用spfa注意添加源点)
有关差分约束系统建模问题,可参考:http://blog.csdn.net/mindmb/archive/2010/12/08/6062203.aspx
分享到:
相关推荐
代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码...
北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮——计算机——数学建模——专业选修 北邮...
数学建模讲座之四——利用Matlab求解线性规划问题PPT学习教案.pptx
数学建模讲座之三——利用Matlab求解线性规划问题linprog函数PPT学习教案.pptx
基于Excel的建模与求解,用excel 轻松建模,轻松求解
同时采用矩阵实数编码遗传算法(MRCGA)和穷举搜索算法,利用MATLAB 7.0.1和C++编程,分别对模型进行求解,并对所得结果进行分析比较,以此来帮助电力部门制定机组启停计划。 首先,建立发电成本最小目标函数和各项...
B2C电子商务系统UML建模——淘宝网系统.docx
遗传算法的优化计算——建模自变量降维
论文研究-时空约束下连铸车间天车调度的多目标建模与求解.pdf, 针对钢厂炼钢-连铸车间天车调度的时空约束下NP难问题特点,考虑重钢包和空钢包吊运任务,以所有吊运任务...
案例27 遗传算法的优化计算——建模自变量降维.7z
数学建模——插值数学建模——插值数学建模——插值数学建模——插值数学建模——插值
MATLAB程序遗传算法的优化计算——建模自变量降维
基于遗传算法的优化计算——建模自变量降维代码
MATLAB源码集锦-基于遗传算法的优化计算——建模自变量降维代码
案例27 遗传算法的优化计算——建模自变量降维
《Matlab/Simulink动力学系统建模与仿真(第2版)》编排了较多的例题来说明各类动力学模型的仿真模型的建立方法,以及差分模型、相似模型、时域和频域等仿真模型,最后将控制动力学基础知识作为后继研究的扩展内容...
MATLAB基于遗传算法的优化计算——建模自变量降维.rar
遗传算法的优化计算——建模自变量降维 matlab程序