算法合集之《浅谈随机化思想在几何问题中的应用》
50页1、广东中山一中 顾研,感受随机的美,浅谈随机化思想在几何问题中的应用,引入,随着信息学的发展,近几年,各种各样灵活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。,随机算法的特点是:简单、快速、灵活和易于并行化,这些特点都会在论文中得到体现。,概览,数值概率算法拉斯维加斯算法蒙特卡罗算法舍伍德算法,第一部分 随机算法简介,第二部分 随机增量算法,第三部分 模拟退火算法,随机增量算法的一个例子,Expensive Drink ( Beijing Site, 2007 )(经过抽象),maximize,s.t.,单纯形法、内点法?,(n100),Expensive Drink,随机增量算法的一般步骤,发现问题的本质,提出算法,改造成增量算法,加入随机,Expensive Drink,解,解,解,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,想法:枚举两个平面,得到一条直线。,枚举其余约束,切割该直线。,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,想法:枚举两个平面,得到一条直线。,枚举其余约束,切割该直线
2、。,直到最后剩下一条线段。,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,直线数量O(n2)切割复杂度O(n)总复杂度O(n3),仍需要提高,结论2:只有线段的两个端点可能成为解。,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,症结:没有利用到之前已经计算的结果,对症:引入增量算法。依次加入半空间的时候,若原先的最优解为v,且满足当前的约束,就没有必要枚举平面上的直线了。,Expensive Drink,复杂度仍旧为O(n3),对策:随机插入半空间的顺序,Expensive Drink,复杂度仍旧为O(n3),对策:随机插入半空间的顺序,复杂度分析,取随机变量Xi,若满足前i-1条约束的最优解满足第i条约束,则Xi=0,否则Xi=1。,时间复杂度为,根据期望的线性率有,是多少呢?最优解由3个约束构成,恰好包括第i条约束的概率就是 。,在本题中,增量算法架筑起了线性规划问题与经典几何知识的桥梁,随机化思想则消除了输入数据的顺序对于复杂度的影响。本题也体现出随机算法简单、快速(相对于单纯形法)的特点。,Expensiv
3、e Drink,下面将介绍论文中的第二个算法:模拟退火算法。,模拟退火算法简介,模拟退火(Simulated Annealing)算法是模仿自然界中固体退火的原理的一种元启发式(Meta-Heuristics)算法。, 初始化:初始充分大的温度T,初始解状态S,迭代数L for k=1 to L 做至 产生新解S并计算评价函数C(S) 若C(S)C(S)则接受S作为新的当前解,否则以概率接受S作为新的当前解 如果满足终止条件则输出当前解作为最优解,结束程序 T逐渐减少,然后转,最小距离问题,经典方法:构造Voronoi图解,并对顶点集合进行判断。,求区域中一点,到某个点集中的点的最小距离最大。,最小距离问题,求区域中一点,到某个点集中的点的最小距离最大。,通过类比的思想, 引入模拟退火算法:,随机初始解,温度T定义为调整向量的模长。估价函数定义为到最近点的距离。如果函数值变大,则更新原解。,最小距离问题,随机初始解,温度T定义为调整向量的模长。估价函数定义为到最近点的距离。如果函数值变大,则更新原解。,求区域中一点,到某个点集中的点的最小距离最大。,通过类比的思想, 引入模拟退火算法:
4、,最小距离问题,模拟退火算法有并行性。,求区域中一点,到某个点集中的点的最小距离最大。,不断重复这一过程,直到步长足够小。取当前最优解作为答案。,通过类比的思想, 引入模拟退火算法:,模拟退火算法的应用,模拟退火算法有很强的可移植性。,模拟退火算法的例子,激光坦克(CTSC2007),在平面上有N个坦克,M个镜子。要求在平面内放置一个激光发射器,使得它在发出的每束激光经过不超过k次反射后击中所有目标的前提下,距离的最大值最小。,N=4 M=4 k=2,模拟退火算法的例子,激光坦克(CTSC2007),N=4 M=4 k=2,本题是一个最大距离最小的问题,如果不考虑镜子的因素,可以使用最远点Voronoi图或前面的随机增量算法来解决,但是镜子的存在使得问题非常棘手。,模拟退火算法的例子,激光坦克(CTSC2007),N=4 M=4 k=2,此时,模拟退火算法的可移植性的优势就体现了出来,我们可以在主算法的框架上,分别独立编写与镜子不同次数相交的评价函数。,激光坦克的得分与代价,总结,本文通过几道例题,以及体现出的一种思想,希望能为大家打开一扇窗,在遇到几何问题的时候多一种思路。当然,随机
《算法合集之《浅谈随机化思想在几何问题中的应用》》由会员xzh****18分享,可在线阅读,更多相关《算法合集之《浅谈随机化思想在几何问题中的应用》》请在金锄头文库上搜索。
爱心树活动教案
世界文化之旅0
七年级学年知识归纳
七年级历史下册第二单元第12课《蒙古的兴起和元朝的建立》课件人教新课标版
一片美丽的叶子
非谓语动词 (6)
[中学联盟]江苏省太仓市第二中学七年级英语上册教学课件:Unit3READING1 (2)
“数与代数”教材修订说明
2014年7月师院培训
字理教学快捷入门之一20140521s
议论文写作指导之新材料作文审题立意 (2)
压缩语段 (2)
琵琶行课件 (2)
2014年各年级的教学计划和建议
(苏教版)五年级数学下册找规律第二课时
秋姑娘的信 (5)
苏教版数学五年级上册《复式条形统计图》课件 (2)
【名校课时通】2014届九年级化学全册第二单元探秘水世界第三节原子的构成名师教学课件鲁教版
《逻辑与语文》课件2
《检阅》[1]
2021-04-07 29页
2018-10-15 35页
2018-10-15 40页
2018-10-15 87页
2018-10-15 12页
2018-10-15 12页
2018-10-15 33页
2018-10-15 21页
2018-10-15 29页
2018-10-15 89页