《算法合集之《浅谈随机化思想在几何问题中的应用》》由会员分享，可在线阅读，更多相关《算法合集之《浅谈随机化思想在几何问题中的应用》（31页珍藏版）》请在金锄头文库上搜索。
1、IOI2008 冬令营论文 顾研1感受随机的美浅谈随机化思想在几何问题中的应用广东省中山一中 顾研摘要近几年来，可以使用随机化来解决的几何题目越来越多。本文将着重介绍两种在信息学竞赛中常见的随机几何算法：随机增量法与模拟退火法，以及和传统方法的比较，说明了随机化思想的优势。关键字随机化 随机增量算法 模拟退火算法 调整目录摘要.1 关键字.1 目录.1 正文.3 1 随机算法简介.3 1.1 数值概率算法.3 1.2 拉斯维加斯（Las Vegas）算法.3 1.3 蒙特卡罗（Monte Carlo）算法.3 1.4 舍伍德（Sherwood）算法.4 2 随机增量算法.5 2.1 增量算法.
2、5 2.2 随机增量算法的一个例子.5 2.2.1 张角法.6 2.2.2 改进算法.6 2.3 随机增量算法的应用.8 2.3.1 蛮力算法.9 2.3.2 切割线段算法.10 2.3.3 随机增量算法.12 3 模拟退火（Simulated Annealing）算法.14IOI2008 冬令营论文 顾研23.1 模拟退火算法介绍.14 3.1.1 模拟退火算法的原理.14 3.1.2 模拟退火算法的模型.14 3.2 例一：Run Away .14 3.3 例二：Empire strikes back.17 3.4 例三：激光坦克.19 3.5 小结.24 4 总结.24 感谢.25 参考
3、文献.25 附录.25 附录 1 蒙特卡罗抽样的步骤.25 附录 2 2.2.2 定理的证明.26 附录 3 论文原题.28 附录 3 参考程序.31 联系方式.31IOI2008 冬令营论文 顾研3正文1 随机算法简介随机算法是这样的一类算法：它在接受输入的同时，在算法中引入随机因素，即通过随机数选择算法的下一步。也就是说，一个随机算法在不同的运行中对于相同的输入可能有不同的结果，或执行时间有可能不同。随机算法的特点：简单、快速、灵活和易于并行化，这些特点都会在本文中得到体现。随机算法可以理解为在时间、空间和精度上的一种的平衡。常见的随机算法有四种：数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。1.1 数值概率算法数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到满意的解。举个例子：计算的近似值时，我们可以在单位圆的外接正方形内随机撒n个点，设有k个点落在单位圆内，可以得到。nk4数值概率算法不是本文的重点，这里仅作简单介绍。有兴趣的同学可自行研究。
