汤泽.ppt
《汤泽.ppt》由会员分享,可在线阅读,更多相关《汤泽.ppt(31页珍藏版)》请在三一文库上搜索。
1、从一类单调性问题看算法的优化,长沙市一中 汤泽,充分挖掘数据关系,灵活运用数据结构,往 往是构造出优秀算法的关键因素 一般队列: 一端插入,另一端删除 特殊队列: 尾端插入,两端删除 单调性: 帮助优化一类单调性问题,问题1 锯木厂选址,2=N=20000,1=Wi=10000,1=Di=10000,问题1 锯木厂选址,最优方案中,锯木厂必定建在有树的位置,问题1 锯木厂选址,问题1 锯木厂选址,分析: CI: 在第I棵树处建立一个锯木厂,并且将第1到第I棵树全部运到这个锯木厂所需的费用 WJ,I: 在第I棵树处建立一个锯木厂,并且将第J+1到第I棵树全部运往这个锯木厂的费用,问题1 锯木厂选
2、址,分析: FI表示在第I棵树处建立第二个锯木厂 的最小费用,则:,这个算法的时间复杂度为O(N2),问题1 锯木厂选址,问题1 锯木厂选址,证明: 令SK,I表示决策变量取K时FI的值 设K1K2I, SK1,I-SK2,I0,问题1 锯木厂选址,证明: 设K1K2I, SK1,I-SK2,I0 令gK1,K2=上面不等式的左边 因为DK 0,因此Sd序列不下降,因此决策是单调的!,问题1 锯木厂选址,分析: 维护一个特殊队列K,K1K2Kn, gK1,K2gK2,K3gKn-1,Kn: 计算状态FI前,若gK1,K2=SdI,表示决策K1不比K2优,删除K1,重复该步骤,问题1 锯木厂选址
3、,分析: 计算FI, FI=CK1+WK1,I+WI,n+1 若gKn-1,KngKn,I, SdIgKn-1,KngKn,I Kn比Kn-1优之前I就将比Kn优, 删除Kn,重复该步骤, 最后将I插入队列 算法总复杂度O(N),问题2 旅行问题,问题描述: 一个环形跑道上有n个加油站,按顺时针编号 为1到n(3n106) 第i号加油站有Pi(0=Pi109)升汽油, 每升汽油可供行驶一千米 第i号车站到其下一站的距离为Di (0di109),问题2 旅行问题,一个例子: N=5 P1=3; D1=1 P2=1; D2=2 P3=5; D3=2 P4=0; D4=1 P5=5; D5=4,3,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 汤泽
链接地址:https://www.31doc.com/p-3209827.html