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

最近更新

必备护士述职报告六篇 8页

七年级语文上册第27课《皇帝的新装》 27页

血液透析膜材料抗凝性能研究-全面剖析 35页

运动能源消耗分析-全面剖析 35页

假冒伪劣商品违法活动的特点及整治对策 2页

保温易割冒口在铸钢件上的应用 2页

供热机组利用循环水余热供热技术研究 2页

住房公积金流动性不均衡问题分析及对策 2页

低温快速固化聚酰亚胺环氧F级浸渍漆的研究 2页

《高中生物必修一》4.3物质跨膜运输的方式 21页

优选法在Fp—16龙门铣床上的应用 2页

伊朗雅达油田完井测试作业中沥青质析出分析 2页

企业申请科技成果鉴定的意义及要点研究 2页

火车站扩建项目劳务合同 6页

仪征市国营商业、供销合作社深化改革的思考 2页

以成组技术为基础的CAD数据库的设计 2页

从邯邢铁矿开发谈矿山地质研究 2页

深圳房地产交易合同范本 6页

从我国核电工业发展看技术经济研究 2页

从加拿大造纸技术谈与我国造纸工业有关的几个.. 2页

消防防排烟工程承建合同书版docx 7页

消防器材采购与安装项目施工合同 7页

人类工程学在企业管理中的应用(下) 2页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

高清地图中国31省市区最全河流水系分布地图建.. 25页

2023年北京市事业单位统考真题及答案 11页

煤矿春季预防性电气试验试措施样板 18页

2025届高考模拟作文“时间管理”升格导写 5页

剑桥雅思原版真题4 114页

《于宏杰-到底神要的是什么呢》 5页