算法合集之《浅谈随机化思想在几何问题中的应用》.ppt

文档介绍：该【算法合集之《浅谈随机化思想在几何问题中的应用》 】是由【165456465】上传分享，文档一共【50】页，该文档可以免费在线阅读，需要了解更多关于【算法合集之《浅谈随机化思想在几何问题中的应用》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。感受随机的美
——浅谈随机化思想在几何问题中的应用
广东中山一中 顾研
随着信息学的发展，近几年，各种各样灵活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。
随机算法的特点是：简单、快速、灵活和易于并行化，这些特点都会在论文中得到体现。
引入
概览
数值概率算法
01
拉斯维加斯算法
02
蒙特卡罗算法
03
舍伍德算法
04
第一部分 随机算法简介
05
第二部分
06
Expensive Drink ( Beijing Site, 2007 )（经过抽象）
1
maximize
2
.
3
……
4
单纯形法、内点法？
5
(n≤100)
6
随机增量算法的一个例子
发现问题的本质
01
提出算法
02
改造成增量算法
03
加入随机
04
随机增量算法的一般步骤
Expensive Drink
解
解
解
结论1：如果存在解，必然存在于三个平面的交点上。
Expensive Drink
想法：枚举两个平面，
得到一条直线。
枚举其余约束，切割该直线。
结论1：如果存在解，必然存在于三个平面的交点上。
Expensive Drink
结论1：如果存在解，必然存在于三个平面的交点上。
枚举其余约束，切割该直线。
想法：枚举两个平面，
得到一条直线。
直到最后剩下一条线段。
直线数量O(n2)
切割复杂度O(n)
总复杂度O(n3)
01
结论1：如果存在解，必然存在于三个平面的交点上。
04
仍需要提高
02
结论2：只有线段的两个端点可能成为解。
03
Expensive Drink
01
症结：没有利用到之前已经计算的结果
02
对症：引入增量算法。依次加入半空间的时候，若原先的最优解为v，且满足当前的约束，就没有必要枚举平面上的直线了。
Expensive Drink