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