国家集训队2008论文集非完美算法初探——任.ppt
《国家集训队2008论文集非完美算法初探——任.ppt》由会员分享,可在线阅读,更多相关《国家集训队2008论文集非完美算法初探——任.ppt(19页珍藏版)》请在三一文库上搜索。
1、唐山一中 任一恒 完美算法 节省空间 更快速方便 压缩 比赛题目标准算法可采用算法 NOI追捕盗贼树搜索分治贪心 CTSC 激光坦克/智能贪心 矩阵网络流构造贪心随机 IOI船帆/贪心调整 冬令营剪刀石头 布 网络流贪心调整 2007年部分应用非完美算法效果不错的题目 一、随机算法 二、贪心算法 四、模拟退火算法 五、等等算法_ 三、抽样测试法 三、抽样测试法 抽样,即从统计总体中,任意抽出一部分单位作 为样本,并以其结果推算总体的相应指标。在某些问 题中,需要让我们检查一系列测试元s,如果s中的某 个测试元满足了某个条件,那么则说s满足了某个性质 。在大度数情况下,我们需要将s中的测试元一个
2、一个 的进行验证,才能确定s是否满足该性质。但是如果s 满足如下性质,要不s中不含满足条件的测试元,要不 满足某条件的测试元很多,则可以直接选取几个具有 代表性的测试元进行测试,通过这几个测试元来确定s 是否满足该性质。 质数检验 质数n,基底1n-1,必为强伪质数 对于一个整数n,设n-1=d*2s(d是奇数),对于给 定的基底a,如果存在ad=1(mod n)或者对于00,然后转第2步。 模拟退火注意点 (1)温度T的初始值设置问题 (2) 退火速度问题 (3)温度管理问题 关联损失 L=20 Div 2 小技巧 优化初始解 生成新解:翻转两边/翻转中间 B(I)/P(I)Q (w1, w
3、2 ,,wq , wq+1 ,,wp ,,wn) (wq, wq-1 ,,w1 , wq+1 ,,wn ,,wp) PQ (w1, w2 ,,wp , wp+1 ,,wq ,,wn) (w1, w2 ,,wq , wq-1 ,,wp ,,wn) 效果 最佳本程序最佳本程序最佳本程序 6060606031366322684891443753810290 2680268559367608817233679581953952 153015424305950668679197817180708 2920300017849621301153405829174311659 67674392150509280637800620868800 85119042608636935692477600129294400 998811034149851875390282993104940360 65417176515235955629043754303806 1248413761661437277260229186781423 110261097738180038980021522002174600 总结 应用广泛。 时空消耗低。 编程复杂度低。 思维容易理解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 国家 集训队 2008 论文集 完美 算法 初探
链接地址:https://www.31doc.com/p-2232421.html