Presentation is loading. Please wait.

Presentation is loading. Please wait.

差分约束系统 F0403026 李博.

Similar presentations


Presentation on theme: "差分约束系统 F0403026 李博."— Presentation transcript:

1 差分约束系统 F 李博

2 引例 国王 很久以前,在某个国家,王子出生了 但是,王子有一点弱智…… 老国王去世后,王子登基了 但是,大臣们不买王子的账,要弹劾他……
引例 国王 很久以前,在某个国家,王子出生了 但是,王子有一点弱智…… 老国王去世后,王子登基了 但是,大臣们不买王子的账,要弹劾他…… 皇后向ACM班的你求助——只有你才能救他! 救救孩子啊~~~

3 引例 国王

4 引例 国王 ,i=1,2,…,n 我们令

5 引例 国王 原问题转化为一个关于 的不等式组有没有整数解的问题 如何求解呢? 差分约束系统

6 差分约束系统 差分约束系统: 若一个系统由n个变量和m个约束条件组成,且每个约束条件有如下形式,则称为一个有n个变量和m个约束条件的差分约束系统。

7 差分约束系统

8 矩阵形式

9 约束图

10 约束图

11 约束图 若存在约束条件 则从 向 引一条边 向每个点引一条边

12 约束图

13 结论 若图中有负权回路,即 ,则系统无可行解 否则,有可行解,解为

14 引理 三角形不等式 G = (V, E)是加权有向图,任取一点s,则对于所有(u,v)∈E,有如下不等式成立: 证明:反证法

15 对结论的证明(1) 1。不存在负权回路 考虑约束条件 有

16 对结论的证明(2) 2。存在负权回路,不妨设为c

17 差分约束系统 如何求最短路呢? Dijkstra Bellman-Ford …

18 Bellman-Ford for each v V do d[v]  ; d[s]  0 Relaxation
for i =1,...,|V|-1 do for each edge (u,v)  E do d[v]  min{d[v], d[u]+w(u,v)} Negative cycle checking for each v V do if d[v]> d[u] + w(u,v) then no solution

19 Bellman-Ford 引理: d[v]  (s,v) 时间复杂度: O(VE) 正确性证明: 数学归纳法 迭代前显然正确
若迭代时有 d[v] = d[u] +w(u,v)成立,则称一次成功松弛,按照成功松弛的次数进行归纳 (s,v)  (s,u)+w(u,v)  d[u]+w(u,v) =d[v]

20 Bellman-Ford 如果没有从s可以到达的负权回路,那么在 |V|-1迭代后对于所有的d[v]有: d[v]=(s,v)
s  v[1]  v[2]  ...  v 第i次迭代后d[v[i]]= (s,v[i])且不变(引理) 如果存在从s可达的负权回路,则一定会有某个(u,v), d[v]>d[u]+ω(u,v)

21 国王 稍微修改一下 的定义: 对映 ,并添加点

22 国王 构约束图,利用Bellman-Ford求解 若存在可行解,则数列元素由下式给出: i=1,2,…,n

23 区间(SWERC2002) 给你n个边界是整数的闭区间 和n个整数 所有数在[1,m]内 请你找到一个整数集合Z,使得 1。|Z|最小 2。

24 区间(SWERC2002) 定义:

25 区间(SWERC2002)

26 差分约束系统在实际中的应用 x1 x x3 x4 x5 x6 x7 x8

27 练习(NOI99 01串) 给定7个整数N,A0,B0,L0,A1,B1,L1,要求设计一个01串S=s1s2…si…sN,满足:
si=0或si=1,1<=i<=N; 对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1),0的个数大于等于A0且小于等于B0; 对于S的任何连续的长度为L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1),1的个数大于等于A1且小于等于B1; 例如,N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2,则存在一个满足上述所有条件的01串S=010101。

28 总结 1。寻找部分和 2。构造约束图

29 总结 3。利用Bellman-Ford求解,若有解则 若将 换为 ,则利用Bellman-Ford求最长路即可

30 参考资料 算法导论(第二版) NOI1999 SWERC2002 Central Europe 1997


Download ppt "差分约束系统 F0403026 李博."

Similar presentations


Ads by Google