文档介绍:该【算法合集之《浅谈随机化思想在几何问题中的应用》 】是由【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