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

感受随机的美 引入 概览 随机增量算法的一个例子 复杂度分析 在本题中，增量算法架筑起了线性规划问题与经典几何知识的桥梁，随机化思想则消除了输入数据的顺序对于复杂度的影响。本题也体现出随机算法简单、快速（相对于单纯形法）的特点。 模拟退火算法简介 最小距离问题 最小距离问题 最小距离问题 模拟退火算法的应用 模拟退火算法的例子 总结 本文通过几道例题，以及体现出的一种思想，希望能为大家打开一扇窗，在遇到几何问题的时候多一种思路。当然，随机化思想的灵活运用，是在对于经典问题熟练掌握的前提下的，因为创新永远建立在扎实的基础之上。 Expensive Drink题目描述 Expensive Drink Expensive Drink 具体的实现 三维线性规划O(n)的算法 这题理论上存在O(n)复杂度的方法。但是该算法有两点弊病： 1) 时间复杂度中隐藏的常数巨大。本题中在时间上的优势微小。（n仅100。） 2) 编程复杂度过大。其实O(n)的算法并不难想：每次加入一个半空间后，如果先前的解不成立需要更新，此时就是要将目标向量在平面上的投影作为新的目标向量，将其他半空间转换成半平面做一次二维线性规划。几次空间和平面间的转换与旋转，将该算法仅仅保留在理论上。 我们使用随机思想是希望事半功倍、化繁为简，因此本算法有悖于我们的初衷。而且无论在信息学还是ACM赛场上比赛的时间都是有限的，因此本算法虽然存在，但并不值得推广。 数值概率算法 数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到满意的解。 举个例子：计算p的近似值时，我们可以在单位圆的外接矩形内随机撒n个点，设有k个点落在单位圆内，可以得到p近似等于4k/n。 舍伍德算法 舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况的发生，而是设法消除这种最坏行为与特定实例之间的关联性。舍伍德算法的一个最广泛的应用就是快速排序的随机化实现。 随机洗牌算法 这个问题不复杂，以下代码就可以以线性的时间复杂度得到一个1~n的随机排列。（记录在数组O中。） 蒙特卡罗抽样 它的基本思想是，对于所求的问题，通过试验的方法和大样本来模拟，得到这个随机变量的期望值，并用它作为问题的解。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解的过程。 模拟退火算法的原理 模拟退火算法是一种元启发式（Meta-Heuristics）算法，来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为 ，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。 元启发式算法 元启发式算法（Meta-Heuristics）是一种启发式策略，意思就是指导启发式算法进行工作的方法。常见的元启发式算法有： 模拟退火算法 遗传算法 蚁群算法 PSO(粒子群优化) 精确度分析的一个例子 最优解附近（如点A，B）的点非常稀少且距离很远，因此有候选解在它周围（所在的Delaunay三角剖分区域内）的概率是很大的。而且此时的距离比较大，我们对方向进行多次尝试，因此调整出去的概率也很小。 精确度分析的一个例子 如图，假设一次随机调整成功的概率为P，则 精确度分析的一个例子 若我们的L取30 ?…………(d=0,g=0) ?D取到最小值0.085r。 1）因为此时两者垂直，因此对于答案的影响很小。 2）我们使用了放缩过程，把g、d都当成0计算，因此实际的调整概率还要更高。 精确度分析的一个例子 但是如果题目的精度要求非常高，怎么办呢？既然很难随机到向量和Voronoi边平行，我们可以直接枚举平行于Voronoi边的向量，虽然在时间上付出一点代价，但是在调整成功的概率和解的精度无疑将大大提高。当然对于普通的题目（本节三道例题Run Away、Empire Strikes Back、激光坦克），普通的随机调整就可以了。 URAL1520：Empire Strikes Back 激光坦克 激光坦克 可以使用随机化思想的几何题目 1 Expensive Drink 2 最小外接圆/球 3 Run Away 4 Empire strikes bac