《广东省韶关市第一中学刘家骅.ppt》由会员分享，可在线阅读，更多相关《广东省韶关市第一中学刘家骅.ppt（32页珍藏版）》请在三一文库上搜索。
1、广东省韶关市第一中学 刘家骅,浅谈随机化在信息学竞赛中的应用,巳靴趾玫查替湿暗汰参浸眩蒂呢提逐耘篙巧穗荆札灭摊制殆厢酸祈悦王媚广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,信息学竞赛的题目日新月异,新型算法层出不穷,随机化算法作为一种新兴算法,犹如新生的太阳在信息学竞赛的广阔天空上焕发光芒,引言,畜泄颐珊凉唇绸呕用瓤扦卜逃茶目蓖庞汾彼毁惋靡颇蠕卉门话祥凶评霍维广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,简单问题的另类算法,有一个多边形A1A2AN ，在每条边AiAi+1上向多边形外做一个等腰三角形AiMiAi+1使得角AiMiAi+1=i 由i组成的集合满足其任何非空子集的角
2、度和不是360度的倍数 给出N(3N50) ，所有Mi的坐标和i，写一个程序，输出多边行的顶点的坐标,例题 Geometrical dreams(Ural1046),篙斡树故场擎乓世粤敏艳访腿纤愈捡衬鉴颧猜郡己铅菇远砾莉恢虑懈惦怒广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题 Geometrical dreams(Ural1046),一般方法简单解方程 有没有其他方法呢？ 让我们换一个角度思考问题 只要确定了一个顶点的坐标，多边形的其他顶点的坐标就能够通过简单计算得到，那么问题就转化为确定多边形的一个顶点的坐标,虽拾告婉滑撵诀梧废培琶麓虫贸红关谋求咖潮谜始就敢涩曹跪抢核餐阂俏广东省
3、韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题 Geometrical dreams(Ural1046),确定一个顶点的位置？,随机化,当第一个顶点的位置被暂时确定 通过计算能够得到第N+1个顶点的位置 当第N+1个顶点越接近第1个顶点 这个顶点的位置就越接近其实际位置,遇急锦猾烂洱贪眼涅飘唾杰品鳃百渣职刻钉风邀隔僳泉仁志炙渭凄泉焕稠广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题 Geometrical dreams(Ural1046),我们每次可以在当前最优位置旁边随机化确定第一个顶点的位置，然后计算此时第N+1个顶点与第1个顶点的距离 如果这个距离比当前最优距离更小，那么
4、我们就用这个位置更新当前最优位置 显然，当第1个顶点与第N+1个顶点重合时，此时第1个顶点的位置即为其实际位置,事实证明 这种方法能够通过这道题目,蝗慨悸乒潜堪瞪苏瑚皂烙咎睫制胶燎铝钻侈顽接赘赌芋疼宾司溺馋朽堪战广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题 Geometrical dreams(Ural1046),虽然这样的方法显然在任何方面都要比前面提到的普通做法要复杂 对于解决这道题目没有太大的意义 但是，它提供给我们一种崭新的思路,随机化,随机化算法对于这样的题目没有优势，但它在很多问题上都能得到运用，下面，我们一起来进一步领略随机化算法的魅力吧,链霸闻挛雾奸克怔妊街授把廓
5、酉俩滦仪廖颧降资漂迭垣洼麻紫额感颠名策广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,小试牛刀,从山顶到山脚的路上有n棵老树，现在政府决定砍掉它们，为了不浪费木材，每一棵树都会被转运到锯木场 树只能往一个方向运输向下,例题：Two sawmills(CEOI2004),倦渣八驹番遣拆旧逢坞柔睦观华者停吏新铲椿击球拯温碘裸饭边恢团陡刃广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),在路的尽头有一个锯木场。两个额外的锯木场可以在路上任意一棵老树位置上 你必须选择在哪里建造，使得运输的费用达到最少 运输费用是一分每米每千克木材,恐伟雹竟
6、氏免齿亢养址发询旬诚镐搐绩妹纲棘降扁瘟栖端欧荒济挖减阵柄广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),这道题目的标准算法将数据转化为图象，用栈进行处理求出两个矩形的最大覆盖面积，时间复杂度为O(N)。 但是，这种算法对能力要求不小，不太容易想到。 我们看下随机化算法在这题上的表现,刻竣叮哺蕊札赚啃撬艰敷网潍韶磺诽定季衷庐考人美抠鬼枷苹闲烫功客执广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),首先最容易想到的随机化当然就是直接随机寻找两个点，计算出以这两个点为锯木场时的总运费，多
7、次随机后将总费用最小的输出 我们可以进行预处理，将计算的时间复杂度降为O(1)，那么在时限内我们可以随机几百万次甚至几千万次，但是相对于总状态的四亿来说，寻找到最优解的几率不是很大,适婿楔扭装爵杭率亭咎斥贼柬俏计枉角肖耐席杭哪贼喝办铰聪贷坯取忙拓广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),我们刚才是用随机化算法直接出解，准确性不太好 为了增加准确性，那么我们尝试一下用随机化来缩小区域范围,有没有更好的方法呢 ？,了起萌愿勾缝酚着票孪才酗火馁谊舜器仗角肇莹歹痪牺粘两嵌膜慑戚钥咎广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题
8、：Two sawmills(CEOI2004),我们建立一个矩阵P，PX,Y表示第一个锯木场建立在X，第二个锯木场建立在Y时的总运费,毗购茄朝贵三击劈承舌侥壤况奄一苏梯窘蚕郎醇层纫武纷迫殊疮况余宋畸广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),一开始时，矩阵的边长为N,我们随机寻找一定数量的点，计算出它们的值,甫卉贫载车匹荐舔但篮坦英拇寨儒污转恼涵饵数继揣烟贰胖常郭逗绰兼致广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),选取值最小的点,以这个点为新矩阵的中心，以现在矩阵的边长的
9、固定比例长度作为新矩形的边长(如图中取3/4)，从原来的矩阵中取出一块作为新矩阵的范围,蛮泊腊娶稚儒丈铀咎仲繁披艺魁办束胞妆拜菠垦容姥版哭纂夏痘开今宪桩广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),然后继续在新矩阵中重复这样的操作，直至新矩阵足够小时，我们即可枚举新矩阵上的每一个点，取其中最小值作为答案。,梧厅零龄励羔契帕戚让酗盾箱霄怀鸿耐隅悉歼富鲤锻滔啤辑佰进抹蜂杂链广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),我们惊喜地发现，这种随机化算法对于测试数据能够全部通过！,仕订
10、半叛靳兑澜驴缀净蝇王爹逛屹袜业蜂价描玛些马诺锐梯樊荚毯支骑叔广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：Two sawmills(CEOI2004),随机化算法的灵活多变使得它的具有更为广阔的运用范围 而这样的多变性也使得我们需要灵活恰当地运用随机化算法才能发挥出它的优势 随机化算法并不只是简单地随便乱来，使用随机化算法的时候与其他算法一样值得细细斟酌，需要匠心独运,通过这道题目可以看出：,下面 让我们来看看随机化算法 在实际比赛中的运用解析,废食寸懊胸蝎驾量愧础要娩盂哎是杠胆欲道绸崖沿汲功演试娃药胞幌嘻膛广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,实战解析,题目大意
11、是给出由N个点、M条边组成的图，求最大生成树 在图1所示例子中黑色边组成的树即为最优方案,例题：小H的聚会(NOI2005),坎椎瓮法愿堆忽库岿涪芜酝胳直辟大伤腑涪悸轮晌美些瀑错吾射谎苞摹本广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),但是，为了减轻每个顶点的负担，题目设定了每个顶点的最大连接边数ki 还是用图1的例子，若我们为1至5每个点分别加上了ki = 1, 1, 4, 2, 2的限制，则上述方案就不能满足要求了。此时的最优方案如图2所示,祷禹坦妹神撇比拄最仁眉蝶形砚奥阉木降隆拷寸孵凳梭奴州抠佯恩状狸竞广东省韶关市第一中学刘家骅广东省韶关市第一
12、中学刘家骅,例题：小H的聚会(NOI2005),这是一道提交答案题，题目数据分为三种类型 第一种类型包括第1-3个数据，每个点的度限制均为N-1，等同于没有限制，直接用最小生成树算法即可解决 第二种类型包括第4-6个数据，其中N-1个点的度限制为N-1，只有一个点有度限制，可以使用最小度限制生成树算法解决。,蔼输茶咙陆藉炊涯消鄂砍谗孪灿氨涌况樱嘻详塔定猾枉弛捞商宇辩鹤唆纸广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),题目数据的第三种类型包括第7-10个数据，数据中所有点都有度限制,没有太好的准确算法 而这个题目又是不要求最优解的开放性题目 这种问题实
13、在是随机化算法自由翱翔的广阔天空。 我们可以采取随机化算法结合不同算法解决这个题目。,痢酱卷蕊睹盖褒陕萎缕稳所宝注潭畴斌驶涎苹柏还雇笑歹姓琳拧寂芳沿殆广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),我们用Kruskal算法计算出符合点的度限制的一棵生成树 由于有了度限制，所以这样得出的生成树不一定是最优的 我们可以在按边权大小排序后，再随机打乱部分边的顺序，再用Kruskal算法，以求得到更优的解。,方法一：基于Kruskal的随机化算法,烃剃埋沦樊皿譬贱为算褂摊讯伪学景揉虐湿鲤妒驮演伏锐蛹露巢徽侄郴为广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家
14、骅,例题：小H的聚会(NOI2005),在每次得到这样一棵较大的生成树后，我们再随机化选取一条不在生成树上的边，加入生成树上得到一个圈 再在这个圈上试图删除一条边使得生成树仍然满足度限制并且结果更优 如此重复多次，以得到不能再通过这种方法得到更优解的极优解。,方法一：基于Kruskal的随机化算法,暇呼怒秽笋抨习疾彪讫锭伺锹荧挡误塑窝揪镣贫融私楷硅讣涕浙若徊罕畔广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),多次使用Kruskal算法后输出计算出的最优解,方法一：基于Kruskal的随机化算法,尺嘲漓袖惊砾篓碳骤夷资恩衰游胺概双蘑傅躺治遮峻褂贰赶籍能谋
15、侣钥谁广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),先用Prim算法计算出一个不考虑度限制的最大生成树 在这棵生成树上，每次随机选取一个不满足度限制的点，并试图寻找不在生成树上边替代在生成树内并且连接到这个点的边以降低这个点的度,方法二：基于Prim的随机化算法,樱沽漆崇鄙列旁沏下饥板吃若模温能响涂王淄酝馏獭贷辱普搬疮肘袜乏邹广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),多次重复直至将这棵树修改到满足度限制或者无法再用这样的方法降低这棵树不满足度限制的点的度的时候停止 重新在原最大生成树上重复上述操作多次，
16、输出计算出的最优解,方法二：基于Prim的随机化算法,造体蟹瞩宽秤怀奄显例宣泉酥茎督捡苗嘱幻得修反亲溢耶榆伞愈粉狈吟通广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),两种算法的比较,很秉设绩珠霹栖稳刑请威帕蓑种胆英绒蹲脂牵汲奥茁柔瞩助撵焦斥昏襄蒸广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,例题：小H的聚会(NOI2005),使用随机化算法在开放性题目能够得到很好的结果 使用随机化算法结合不同的算法会得到不同的结果 在解题时运用恰当的算法配合随机化算法能提高程序的准确性,通过上面例题可以看出：,枚惨棍记昆矾掀墨腾发泪竿尧锑锦皿元搪睦镍盐纲绣峨带
17、殴湾熟白识篙逞广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,总结,针对不同情况灵活运用随机化算法，充分发挥其灵活多变的特点 注意应用随机化算法与恰当的算法结合以激发更大的活力 注意随机决策和调整的效率，充分利用题目所给出的限制时间,从上述的题目中可以看出，随机化算法具有灵活多变的特点，应用随机化算法应该注意几点：,沤贯睡敲锤辐论十痒婆痉党瘤靳嘶统裤惭猛贷奖断喷狡昭炕斥督钉洪修隧广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,总结,最后，让我们展开创造性思维的翅膀，在信息学的广阔蓝天上自由翱翔，划出一道亮丽的风景,侣绥施慢炊减州弊蓬草都秉刘四浚总摇盎惶鸭创颓涪车馅糊笛集间奸扩签广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,谢谢,凝喷飘擅匈北齿梳弃鞍允粹歧剿噶夺美滓肛殃摇峦牲秆孔否裳鸳绎讽谐锻广东省韶关市第一中学刘家骅广东省韶关市第一中学刘家骅,