1 / 50
文档名称:

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

格式:ppt   大小:6,684KB   页数:50页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

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

上传人:165456465 2025/3/15 文件大小:6.53 MB

下载得到文件列表

算法合集之《浅谈随机化思想在几何问题中的应用》.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