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

最近更新

基于测录井资料的J油田储层分类研究 2页

幼儿园2019-2020年保育员五级职业水平考试试题.. 11页

2020-2025年中国游泳镜行业市场前景预测及投资.. 20页

基于模糊控制的自动供水教学系统的设计 2页

2025年交换过后才知道续写作文 6页

基于标签和关联规则挖掘的图书组合推荐系统模.. 2页

2020-2025年中国植物防脱洗发液市场前景预测及.. 23页

2025年五彩池教学设计优秀 20页

能源基础设施建设项目合同工程方案 7页

基于有补T-范的F-命题演算和一类F-控制模型 2页

2025年护士毕业实习总结 9页

2025年护士心得体会600字范文 17页

2025年护士年终简短工作总结 9页

2025年五年级苹果的作文 6页

2025年护士年终个人总结简短2025 13页

2025年护士工作述职报告范文 19页

2025年护士工作总结5篇 12页

2025年五年级数学教案异分母分数的加、减法 7页

基于改进同伦迭代法对病态潮流的研究 2页

基于控制流模型的Web系统测试方法研究 2页

人工智能与行业应用-全面剖析 43页

2025年护士学习的心得 4页

股权转让合同变更登记协议 5页

2019-2025年中国自动铅笔行业发展潜力分析及投.. 23页

校园网络工程设计-网络工程课程设计报告 32页

煤矿综采工作面三机选型 10页

物业续聘管理方案 4页

六年级下册平面图形的认识练习题 4页

第10课桥梁模型-设计与制作 2页

液相色谱-质谱联用仪期间核查操作规程 3页