算法合集之《浅谈随机化思想在几何问题中的应用》.ppt
《算法合集之《浅谈随机化思想在几何问题中的应用》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《浅谈随机化思想在几何问题中的应用》.ppt(50页珍藏版)》请在三一文库上搜索。
1、广东中山一中 顾研,感受随机的美,浅谈随机化思想在几何问题中的应用,引入,随着信息学的发展,近几年,各种各样灵活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。,随机算法的特点是:简单、快速、灵活和易于并行化,这些特点都会在论文中得到体现。,概览,数值概率算法 拉斯维加斯算法 蒙特卡罗算法 舍伍德算法,第一部分 随机算法简介,第二部分 随机增量算法,第三部分 模拟退火算法,随机增量算法的一个例子,Expensive Drink ( Beijing Site, 2007 )(经过抽象),maximize,s.t.,单纯形法、内点法?,(n100),Expensive Drink,随
2、机增量算法的一般步骤,发现问题的本质,提出算法,改造成增量算法,加入随机,Expensive Drink,解,解,解,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,想法:枚举两个平面, 得到一条直线。,枚举其余约束,切割该直线。,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,想法:枚举两个平面, 得到一条直线。,枚举其余约束,切割该直线。,直到最后剩下一条线段。,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,直线数量O(n2) 切割复杂度O(n) 总复杂度O(n3),仍需要提高,结论2:
3、只有线段的两个端点可能成为解。,结论1:如果存在解,必然存在于三个平面的交点上。,Expensive Drink,症结:没有利用到之前已经计算的结果,对症:引入增量算法。依次加入半空间的时候,若原先的最优解为v,且满足当前的约束,就没有必要枚举平面上的直线了。,Expensive Drink,复杂度仍旧为O(n3),对策:随机插入半空间的顺序,Expensive Drink,复杂度仍旧为O(n3),对策:随机插入半空间的顺序,复杂度分析,取随机变量Xi,若满足前i-1条约束的最优解满足第i条约束,则Xi=0,否则Xi=1。,时间复杂度为,根据期望的线性率有,是多少呢?最优解由3个约束构成,恰好
4、包括第i条约束的概率就是 。,在本题中,增量算法架筑起了线性规划问题与经典几何知识的桥梁,随机化思想则消除了输入数据的顺序对于复杂度的影响。本题也体现出随机算法简单、快速(相对于单纯形法)的特点。,Expensive Drink,下面将介绍论文中的第二个算法:模拟退火算法。,模拟退火算法简介,模拟退火(Simulated Annealing)算法是模仿自然界中固体退火的原理的一种元启发式(Meta-Heuristics)算法。, 初始化:初始充分大的温度T,初始解状态S,迭代数L for k=1 to L 做至 产生新解S并计算评价函数C(S) 若C(S)C(S)则接受S作为新的当前解,否则以
5、概率 接受S作为新的当前解 如果满足终止条件则输出当前解作为最优解,结束程序 T逐渐减少,然后转,最小距离问题,经典方法:构造Voronoi图解,并对顶点集合进行判断。,求区域中一点,到某个点集中的点的最小距离最大。,最小距离问题,求区域中一点,到某个点集中的点的最小距离最大。,通过类比的思想, 引入模拟退火算法:,随机初始解,温度T定义为调整向量的模长。估价函数定义为到最近点的距离。 如果函数值变大,则更新原解。,最小距离问题,随机初始解,温度T定义为调整向量的模长。估价函数定义为到最近点的距离。 如果函数值变大,则更新原解。,求区域中一点,到某个点集中的点的最小距离最大。,通过类比的思想,
6、 引入模拟退火算法:,最小距离问题,模拟退火算法有并行性。,求区域中一点,到某个点集中的点的最小距离最大。,不断重复这一过程,直到步长足够小。取当前最优解作为答案。,通过类比的思想, 引入模拟退火算法:,模拟退火算法的应用,模拟退火算法有很强的可移植性。,模拟退火算法的例子,激光坦克(CTSC2007),在平面上有N个坦克,M个镜子。要求在平面内放置一个激光发射器,使得它在发出的每束激光经过不超过k次反射后击中所有目标的前提下,距离的最大值最小。,N=4 M=4 k=2,模拟退火算法的例子,激光坦克(CTSC2007),N=4 M=4 k=2,本题是一个最大距离最小的问题,如果不考虑镜子的因素
7、,可以使用最远点Voronoi图或前面的随机增量算法来解决,但是镜子的存在使得问题非常棘手。,模拟退火算法的例子,激光坦克(CTSC2007),N=4 M=4 k=2,此时,模拟退火算法的可移植性的优势就体现了出来,我们可以在主算法的框架上,分别独立编写与镜子不同次数相交的评价函数。,激光坦克的得分与代价,总结,本文通过几道例题,以及体现出的一种思想,希望能为大家打开一扇窗,在遇到几何问题的时候多一种思路。当然,随机化思想的灵活运用,是在对于经典问题熟练掌握的前提下的,因为创新永远建立在扎实的基础之上。,谢谢!,Expensive Drink题目描述,有3种物品的价格(设为x, y, z)要满
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅谈随机化思想在几何问题中的应用 算法 浅谈 随机化 思想 几何 问题 中的 应用
链接地址:https://www.31doc.com/p-2158944.html