2006年国家集训队论文_从一类单调性问题看算法的优化（PPT报告).pptx

从一类单调性问题看算法的优化,,充分挖掘数据关系,灵活运用数据结构,往 往是构造出优秀算法的关键因素 一般队列 一端插入,另一端删除 特殊队列 尾端插入,两端删除 单调性 帮助优化一类单调性问题,问题1 锯木厂选址,2N20000,1Wi10000,1Di10000,,问题1 锯木厂选址,,,,最优方案中,锯木厂必定建在有树的位置,问题1 锯木厂选址,问题1 锯木厂选址,分析 C[I] 在第I棵树处建立一个锯木厂,并且将第1到第I棵树全部运到这个锯木厂所需的费用 W[J,I] 在第I棵树处建立一个锯木厂,并且将第J1到第I棵树全部运往这个锯木厂的费用,,,,,问题1 锯木厂选址,分析 F[I]表示在第I棵树处建立第二个锯木厂 的最小费用,则,,,这个算法的时间复杂度为ON2,问题1 锯木厂选址,问题1 锯木厂选址,证明 令S[K,I]表示决策变量取K时F[I]的值 设K1K2I, S[K1,I]-S[K2,I]0,,,,,问题1 锯木厂选址,证明 设K1K2I, S[K1,I]-S[K2,I]0 令g[K1,K2]上面不等式的左边 因为D[K] ≥ 0,因此Sd序列不下降,因此决策是单调的,,,,问题1 锯木厂选址,分析 维护一个特殊队列K,K1K2Kn, g[K1,K2]g[K2,K3]g[Kn-1,Kn] 计算状态F[I]前,若g[K1,K2]Sd[I],表示决策K1不比K2优,删除K1,重复该步骤,问题1 锯木厂选址,分析 计算F[I], F[I]C[K1]W[K1,I]W[I,n1] 若g[Kn-1,Kn]g[Kn,I], Sd[I’]g[Kn-1,Kn]g[Kn,I] Kn比Kn-1优之前I就将比Kn优, 删除Kn,重复该步骤, 最后将I插入队列 算法总复杂度ON,问题2 旅行问题,问题描述 一个环形跑道上有n个加油站，按顺时针编号 为1到n3n106 第i号加油站有Pi0Pi109升汽油, 每升汽油可供行驶一千米 第i号车站到其下一站的距离为Di 0di109,问题2 旅行问题,一个例子 N5 P[1]3; D[1]1 P[2]1; D[2]2 P[3]5; D[3]2 P[4]0; D[4]1 P[5]5; D[5]4,,3,1,5,0,5,1,2,2,1,4,问题2 旅行问题,一个例子 N5 P[1]3; D[1]1 P[2]1; D[2]2 P[3]5; D[3]2 P[4]0; D[4]1 P[5]5; D[5]4,,S3,S3,S6,S4,S8,S2,S1,S4,S3,S4,以1号加油站为起点,问题2 旅行问题,一个例子 N5 P[1]3; D[1]1 P[2]1; D[2]2 P[3]5; D[3]2 P[4]0; D[4]1 P[5]5; D[5]4,,S1,以2号加油站为起点,S-1,问题2 旅行问题,一个例子 N5 P[1]3; D[1]1 P[2]1; D[2]2 P[3]5; D[3]2 P[4]0; D[4]1 P[5]5; D[5]4,,S1,S0,S-1,以2号加油站为起点,S3,问题2 旅行问题,一个例子 N5 P[1]3; D[1]1 P[2]1; D[2]2 P[3]5; D[3]2 P[4]0; D[4]1 P[5]5; D[5]4,以1、3、5号加油站为起点有办法周游一圈,算法 一,分析 直接模拟刚刚的演算过程 总的时间复杂度为ON2 但是N最大可以达到106,太慢了,算法 二,分析 假定只能按顺时针方向行驶. 令A[I]P[I]-D[I] A[IN]A[I] A[0]0 设SA[I]表示A序列中前I项的和,算法 二,,,算法 二,分析 SA[I]到SA[IN-1]都不小于SA[I-1] SA[I]到SA[IN-1]中的最小数不小于SA[I-1] 求N个数中的最小数,很自然地想到了堆,算法 二,堆中不超过N个元素 2N次插入操作 2N次删除操作 N次取堆顶元素 总复杂度ONLog2N,,,算法 三,分析 给定一个序列SA和N个区间 求出每个区间中的最小值,对其作相应判定 这是一个标准的RMQ问题 时间复杂度降为ON,SA 0 2 1 4 3 4 2 1 4 3,算法 四,分析 给定的N个区间不存在包含关系,满足单调性,0 1 2 3 4 5 6 7 8 9 Sa 0 2 1 4 3 4 2 1 4 3,,K,2,,2,,7,,7,,7,同样满足单调性,算法 四,预处理 维护一个特殊队列K, K1K2Kn Sa[k1]Sa[k2]Sa[Kn] 将1,2n-1依次插入队列K.插入前,如果Sa[i]Sa[kn],将Kn删除.反复该步骤,最后将i插入队列,算法 四,求解并更新K 若K1i-1,将K1删除出队列 插入新位置号in-1, 若Sa[Kn]Sa[in-1], 删除Kn,重 复这个步骤,最后将in-1作为Kn插入队列 若Sa[k1]Sa[i-1],表示从i号加油站出发可以周游一周 总复杂度ON,四个算法比较,总 结,通过充分挖掘数据关系,发现隐含的单调性, 以较低的编程复杂度成功地实现了算法的优 化 注意问题的特殊性 学会灵活变通,总 结,善于发现,勇于创新,谢谢大家,