陈雪问题中变与不变.ppt

问题中的变与不变 1引言•对变量进行操作是信息学中的常见问题•如果能找到变量之间的关系，把变量转化成不变量，那么算法的效率就将得到质的提升2[ [例一例一] ]蚂蚁蚂蚁•一条树枝上有N只蚂蚁给出他们的位置，如何安排蚂蚁初始的方向使得全部蚂蚁掉落的时间最早或最晚•最多1,000,000只蚂蚁3感性认识•左边的蚂蚁向左端走，右边的蚂蚁向右端走•如何使全部掉落的时间最晚？•猜想：让左边的蚂蚁向右端走，同时右边的蚂蚁向左端走4理性分析•直接证明猜想难度比较大•看一般的情况:•纪录2只蚂蚁的有用信息:速度 和位置 •设 •在蚂蚁相遇前一刻,•在蚂蚁相遇后一颗,一个集合内蚂蚁相遇集合不变5继续分析•另•任何两只属于集合U内的蚂蚁相遇之后，集合U不变•集合U只随着时间的变化而变化•{Ansi i}={蚂蚁I按起始方向走到端点}6继续分析•回到原问题• 最早时间=• 最迟时间=•猜想得证！！•最终时间复杂度O( n )即左边蚂蚁向左走，右边蚂蚁向右走Max{蚂蚁I向近端出发}Max{蚂蚁I向远端出发}即左边蚂蚁向右走，右边蚂蚁向左走7小结•分析题目的特殊特点:–1.原路返回–2.速度相同•将速度变量固定，成为常量。

•问题得到了简化8[ [例二例二] ]circular way•安排一种方案•使得总代价最小•n≤50000•最小权匹配！ •无法满足题目要求！！•设A类点顺时针排序的坐标为A1 1,A2 2.. An n•设B类点顺时针排序的坐标为B1 1,B2 2.. Bn n9优化算法•最小权匹配必然满足下面的性质:•通过调整可以得到更优解两条匹配边不会交叉两条匹配边不会交叉10算法二•1.枚举和A1 1匹配的点Bk k•2.然后按顺序一一求出和Ai i匹配的点•3.最后统计当前的代价和，更新答案时间复杂度11继续分析•另Ci i表示当前Ai i与它匹配的Bj j的距离•当前的代价sum=ΣCi i•Ci i随着我们枚举k而变化找出Ci中蕴含的不变？12观察Ci i•由于Ai i到Bj j有顺时针，逆时针2种走法•Ci i =Min{|Ai i-Bj j|,L-|Ai i-Bj j|}•Ci i只同Ai i和Bj j有关•不妨把Ci i看成Ai i和Bj j的函数•设Ci i=f(Ai i)+g(Bj j)13讨论Ci i0从 顺时针走到14讨论Ci i0从 逆时针走到15讨论Ci i0从 顺时针走到16讨论Ci i0从 逆时针走到17继续分析•根据Ai i,Bi i的有序性，得到f(Ai i)的每种情况对应的Bj j都是连续的一段。

•f(Ai i)在枚举和A1 1匹配的点Bk k的过程中 只会发生4次变化• 从Ci i的N次变化 • f(Ai i),g(Bi i)的4次变化18回到原问题•当前的代价sum=ΣCi i=Σf(Ai i)+Σg(Bi i)•A1 1匹配Bk k，sum已经求出•当A1 1匹配Bk+1k+1，，更新f(Ai i),g(Bi i),sum•sum=sum’-f’(Ai i)+f(Ai i)-g’(Bi i)+g(Bi i)•把一个-f’(Ai i)+f(Ai i)和-g’(Bi i)+g(Bi i) 看成一次事件f’(Ai)表示上一时刻f(Ai)f(Ai)表示当前f(Ai)19举例•A1 1匹配B4 4，有，有•A1 1匹配B1 1，有，有看成一次事件看成一次事件20分析•事件总数≤8n•根据Ai i,Bi i的有序性，预处理用指针即可知道下一时刻k+1会发生的事件更新sum得到f (Ai)4种情况对应的Bj范围每件事件发生时间21小结•算法流程如下•[1]将Ai i,Bi i排序•[2]预处理求出每个事件发生时间•[3]枚举和A1 1匹配的点Bk k,更新sum。

•[4]输出•时间复杂度•O(排序+事件总数)=O(nlgn)22 小结•将变化的Ci i转化成“不变”的f(Ai i)和g(Bi i)•减少了操作规模•问题迎刃而解23总结• [ [例一例一] ]蚂蚁蚂蚁• 以不变应万变以不变应万变• [ [例二例二] ]circular way• 将变量的操作规模缩小将变量的操作规模缩小 仔细分析，大胆猜想把握问题的本质问题迎刃而解变 不变24•参考文献:•[1] 刘汝佳,黄亮.算法艺术与信息学竞赛. 清华大学出版社.2003•[2] zju online judge 2376 ants. •[3] sgu online judge 313 circular railway. 25。