《算法合集之问题中的变与不变.ppt》由会员分享，可在线阅读，更多相关《算法合集之问题中的变与不变.ppt（25页珍藏版）》请在三一办公上搜索。
1、问题中的变与不变,长沙市雅礼中学 陈雪,引言,对变量进行操作是信息学中的常见问题。如果能找到变量之间的关系，把变量转化成不变量，那么算法的效率就将得到质的提升。,例一蚂蚁,一条树枝上有N只蚂蚁。给出他们的位置，如何安排蚂蚁初始的方向使得全部蚂蚁掉落的时间最早或最晚。最多1,000,000只蚂蚁。,感性认识,左边的蚂蚁向左端走，右边的蚂蚁向右端走。如何使全部掉落的时间最晚？猜想：让左边的蚂蚁向右端走，同时右边的蚂蚁向左端走。,理性分析,直接证明猜想难度比较大。看一般的情况:纪录2只蚂蚁的有用信息:速度 和位置。设。,在蚂蚁相遇前一刻,在蚂蚁相遇后一颗,一个集合内蚂蚁相遇,集合不变,继续分析,另任
2、何两只属于集合U内的蚂蚁相遇之后，集合U不变。集合U只随着时间的变化而变化。Ansi=蚂蚁I按起始方向走到端点,继续分析,回到原问题 最早时间=最迟时间=猜想得证！最终时间复杂度O(n)。,即左边蚂蚁向左走，右边蚂蚁向右走,Max蚂蚁I向近端出发,Max蚂蚁I向远端出发,即左边蚂蚁向右走，右边蚂蚁向左走,小结,分析题目的特殊特点:1.原路返回2.速度相同将速度变量固定，成为常量。问题得到了简化。,例二circular way,安排一种方案使得总代价最小n50000最小权匹配！无法满足题目要求！设A类点顺时针排序的坐标为A1,A2.An设B类点顺时针排序的坐标为B1,B2.Bn,优化算法,最小权
3、匹配必然满足下面的性质:通过调整可以得到更优解,两条匹配边不会交叉,算法二,1.枚举和A1匹配的点Bk。2.然后按顺序一一求出和Ai匹配的点。3.最后统计当前的代价和，更新答案。,时间复杂度,继续分析,另Ci表示当前Ai与它匹配的Bj的距离。当前的代价sum=CiCi随着我们枚举k而变化。,找出Ci中蕴含的不变？,观察Ci,由于Ai到Bj有顺时针，逆时针2种走法。Ci=Min|Ai-Bj|,L-|Ai-Bj|Ci只同Ai和Bj有关。不妨把Ci看成Ai和Bj的函数。设Ci=f(Ai)+g(Bj),讨论Ci,0,从 顺时针走到,讨论Ci,0,从 逆时针走到,讨论Ci,0,从 顺时针走到,讨论Ci,
4、0,从 逆时针走到,继续分析,根据Ai,Bi的有序性，得到f(Ai)的每种情况对应的Bj都是连续的一段。f(Ai)在枚举和A1匹配的点Bk的过程中 只会发生4次变化。从Ci的N次变化 f(Ai),g(Bi)的4次变化,回到原问题,当前的代价sum=Ci=f(Ai)+g(Bi)A1匹配Bk，sum已经求出。当A1匹配Bk+1，更新f(Ai),g(Bi),sum。sum=sum-f(Ai)+f(Ai)-g(Bi)+g(Bi)把一个-f(Ai)+f(Ai)和-g(Bi)+g(Bi)看成一次事件,f(Ai)表示上一时刻f(Ai)f(Ai)表示当前f(Ai),举例,A1匹配B4，有A1匹配B1，有,看成
5、一次事件,看成一次事件,分析,事件总数8n根据Ai,Bi的有序性，预处理用指针即可,知道下一时刻k+1会发生的事件,更新sum,得到f(Ai)4种情况对应的Bj范围,每件事件发生时间,小结,算法流程如下1将Ai,Bi排序2预处理求出每个事件发生时间3枚举和A1匹配的点Bk,更新sum。4输出时间复杂度O(排序+事件总数)=O(nlgn),小结,将变化的Ci转化成“不变”的f(Ai)和g(Bi)减少了操作规模问题迎刃而解,总结,例一蚂蚁 以不变应万变 例二circular way 将变量的操作规模缩小,仔细分析，大胆猜想,把握问题的本质,问题迎刃而解,变 不变,谢谢大家,参考文献:1 刘汝佳,黄亮.算法艺术与信息学竞赛.清华大学出版社.20032 zju online judge 2376 ants.http:/sgu online judge 313 circular railway.http:/acm.sgu.ru/problem.php?contest=0&problem=313,
