广东省韶关市一中学刘家骅.ppt
《广东省韶关市一中学刘家骅.ppt》由会员分享,可在线阅读,更多相关《广东省韶关市一中学刘家骅.ppt(32页珍藏版)》请在三一文库上搜索。
1、广东省韶关市第一中学 刘家骅,浅谈随机化在信息学竞赛中的应用,信息学竞赛的题目日新月异,新型算法层出不穷,随机化算法作为一种新兴算法,犹如新生的太阳在信息学竞赛的广阔天空上焕发光芒,引言,简单问题的另类算法,有一个多边形A1A2AN ,在每条边AiAi+1上向多边形外做一个等腰三角形AiMiAi+1使得角AiMiAi+1=i 由i组成的集合满足其任何非空子集的角度和不是360度的倍数 给出N(3N50) ,所有Mi的坐标和i,写一个程序,输出多边行的顶点的坐标,例题 Geometrical dreams(Ural1046),例题 Geometrical dreams(Ural1046),一般方
2、法简单解方程 有没有其他方法呢? 让我们换一个角度思考问题 只要确定了一个顶点的坐标,多边形的其他顶点的坐标就能够通过简单计算得到,那么问题就转化为确定多边形的一个顶点的坐标,例题 Geometrical dreams(Ural1046),确定一个顶点的位置?,随机化,当第一个顶点的位置被暂时确定 通过计算能够得到第N+1个顶点的位置 当第N+1个顶点越接近第1个顶点 这个顶点的位置就越接近其实际位置,例题 Geometrical dreams(Ural1046),我们每次可以在当前最优位置旁边随机化确定第一个顶点的位置,然后计算此时第N+1个顶点与第1个顶点的距离 如果这个距离比当前最优距离
3、更小,那么我们就用这个位置更新当前最优位置 显然,当第1个顶点与第N+1个顶点重合时,此时第1个顶点的位置即为其实际位置,事实证明 这种方法能够通过这道题目,例题 Geometrical dreams(Ural1046),虽然这样的方法显然在任何方面都要比前面提到的普通做法要复杂 对于解决这道题目没有太大的意义 但是,它提供给我们一种崭新的思路,随机化,随机化算法对于这样的题目没有优势,但它在很多问题上都能得到运用,下面,我们一起来进一步领略随机化算法的魅力吧,小试牛刀,从山顶到山脚的路上有n棵老树,现在政府决定砍掉它们,为了不浪费木材,每一棵树都会被转运到锯木场 树只能往一个方向运输向下,例
4、题:Two sawmills(CEOI2004),例题:Two sawmills(CEOI2004),在路的尽头有一个锯木场。两个额外的锯木场可以在路上任意一棵老树位置上 你必须选择在哪里建造,使得运输的费用达到最少 运输费用是一分每米每千克木材,例题:Two sawmills(CEOI2004),这道题目的标准算法将数据转化为图象,用栈进行处理求出两个矩形的最大覆盖面积,时间复杂度为O(N)。 但是,这种算法对能力要求不小,不太容易想到。 我们看下随机化算法在这题上的表现,例题:Two sawmills(CEOI2004),首先最容易想到的随机化当然就是直接随机寻找两个点,计算出以这两个点为
5、锯木场时的总运费,多次随机后将总费用最小的输出 我们可以进行预处理,将计算的时间复杂度降为O(1),那么在时限内我们可以随机几百万次甚至几千万次,但是相对于总状态的四亿来说,寻找到最优解的几率不是很大,例题:Two sawmills(CEOI2004),我们刚才是用随机化算法直接出解,准确性不太好 为了增加准确性,那么我们尝试一下用随机化来缩小区域范围,有没有更好的方法呢 ?,例题:Two sawmills(CEOI2004),我们建立一个矩阵P,PX,Y表示第一个锯木场建立在X,第二个锯木场建立在Y时的总运费,例题:Two sawmills(CEOI2004),一开始时,矩阵的边长为N,我们
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广东省 韶关市 中学 刘家骅
链接地址:https://www.31doc.com/p-2461823.html