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

广东中山一中广东中山一中广东中山一中广东中山一中 顾研顾研顾研顾研感受随机的美浅谈随机化思想在几何问题中的应用引入 随着信息学的发展，近几年，各种各样灵随着信息学的发展，近几年，各种各样灵活的几何题目层出不穷。因此随机算法和随机活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。化思想便有了表演的舞台。随机算法的特点是：随机算法的特点是：简单简单、快速快速、灵活灵活和和易于并行化易于并行化，这些特点都会在论文中得到体现。，这些特点都会在论文中得到体现。概览数值概率算法数值概率算法拉斯维加斯算法拉斯维加斯算法蒙特卡罗算法蒙特卡罗算法舍伍德算法舍伍德算法第一部分第一部分 随机算法简介随机算法简介第二部分第二部分随机增量算法随机增量算法第三部分第三部分模拟退火算法模拟退火算法随机增量算法的一个例子Expensive Drink(Beijing Site,2007)（经过抽象）（经过抽象）maximizes.t.单纯形法、内点法？单纯形法、内点法？(n100)随机增量算法的一般步骤发现问题的本质发现问题的本质提出算法提出算法改造成增量算法改造成增量算法加入随机加入随机Expensive Drink解解解结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。Expensive Drink想法：枚举两个平面，想法：枚举两个平面，得到一条直线。得到一条直线。枚举其余约束，枚举其余约束，切割该直线。切割该直线。结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。Expensive Drink想法：枚举两个平面，想法：枚举两个平面，得到一条直线。得到一条直线。枚举其余约束，枚举其余约束，切割该直线。切割该直线。直到最后剩下一直到最后剩下一条线段。条线段。结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。Expensive Drink直线数量直线数量O(n2)切割复杂度切割复杂度O(n)总复杂度总复杂度O(n3)仍需要提高结论结论2：只有线段的两个端点可能成为解。：只有线段的两个端点可能成为解。结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。Expensive Drink症结：没有利用到之前已经计算的结果症结：没有利用到之前已经计算的结果 对症：引入增量算对症：引入增量算法。依次加入半空法。依次加入半空间的时候，若原先间的时候，若原先的最优解为的最优解为v，且满，且满足当前的约束，就足当前的约束，就没有必要枚举平面没有必要枚举平面上的直线了。上的直线了。Expensive Drink复杂度仍旧为复杂度仍旧为O(n3)对策：随机插入对策：随机插入半空间的顺序半空间的顺序Expensive Drink复杂度仍旧为复杂度仍旧为O(n3)对策：随机插入对策：随机插入半空间的顺序半空间的顺序复杂度分析 取随机变量取随机变量Xi，若满足前，若满足前i-1条约束的最条约束的最优解满足第优解满足第i条约束，则条约束，则Xi=0，否则，否则Xi=1。时间复杂度为时间复杂度为根据期望的线性率有根据期望的线性率有 是多少呢？最优解由是多少呢？最优解由3个约束构成，恰个约束构成，恰好包括第好包括第i条约束的概率就是条约束的概率就是 。在本题中，增量算法架筑起了线性规划问在本题中，增量算法架筑起了线性规划问题与经典几何知识的桥梁，随机化思想则题与经典几何知识的桥梁，随机化思想则消除了输入数据的顺序对于复杂度的影响。消除了输入数据的顺序对于复杂度的影响。本题也体现出随机算法简单、快速（相对本题也体现出随机算法简单、快速（相对于单纯形法）的特点。于单纯形法）的特点。Expensive Drink下面将介绍论文中的第二个算法：模拟退下面将介绍论文中的第二个算法：模拟退火算法。火算法。模拟退火算法简介 模拟退火（模拟退火（Simulated Annealing）算法是）算法是模仿自然界中固体退火的原理的一种元启发式模仿自然界中固体退火的原理的一种元启发式（Meta-Heuristics）算法。）算法。初始化：初始充分大的温度初始化：初始充分大的温度T，初始解状态，初始解状态S，迭代数迭代数L for k=1 to L 做做至至 产生新解产生新解S并计算评价函数并计算评价函数C(S)若若C(S)C(S)则接受则接受S作为新的当前解，否则以概率作为新的当前解，否则以概率 接受接受S作为新的当前解作为新的当前解 如果满足终止条件则输出当前解作为最优解，结束程序如果满足终止条件则输出当前解作为最优解，结束程序 T逐渐减少，然后转逐渐减少，然后转最小距离问题经典方法：构造经典方法：构造Voronoi图解，并图解，并对顶点集合进行对顶点集合进行判断。判断。求区域中一点，到某个点集中的点的最小距离最大。求区域中一点，到某个点集中的点的最小距离最大。最小距离问题求区域中一点，到某个点集中的点的最小距离最大。求区域中一点，到某个点集中的点的最小距离最大。通过类比的思想，通过类比的思想，引入模拟退火算法：引入模拟退火算法：随机初始解，随机初始解，温度温度T定义为调整定义为调整向量的模长。估价向量的模长。估价函数定义为到最近函数定义为到最近点的距离。点的距离。如果函数值变如果函数值变大，则更新原解。大，则更新原解。最小距离问题 随机初始解，随机初始解，温度温度T定义为调整定义为调整向量的模长。估价向量的模长。估价函数定义为到最近函数定义为到最近点的距离。点的距离。如果函数值变如果函数值变大，则更新原解。大，则更新原解。求区域中一点，到某个点集中的点的最小距离最大。求区域中一点，到某个点集中的点的最小距离最大。通过类比的思想，通过类比的思想，引入模拟退火算法：引入模拟退火算法：最小距离问题模拟退火算法有模拟退火算法有并行性并行性。求区域中一点，到某个点集中的点的最小距离最大。求区域中一点，到某个点集中的点的最小距离最大。不断重复这一过不断重复这一过程，直到步长足程，直到步长足够小。取当前最够小。取当前最优解作为答案。优解作为答案。通过类比的思想，通过类比的思想，引入模拟退火算法：引入模拟退火算法：模拟退火算法的应用模拟退火算法有很强的模拟退火算法有很强的可移植性可移植性。最小距离最大最小距离最大对应于对应于最近点最近点Voronoi图解图解最大距离最小最大距离最小最远点最远点Voronoi图解图解第第k大距离最小大距离最小k阶阶Voronoi图解图解经过反射后距离最小经过反射后距离最小和距离最小和距离最小倒数和距离最小倒数和距离最小模拟退火算法的例子激光坦克（激光坦克（CTSC2007）在平面上有在平面上有N个坦克，个坦克，M个镜子。要求在平面内个镜子。要求在平面内放置一个激光发射器，使放置一个激光发射器，使得它在发出的每束激光经得它在发出的每束激光经过不超过过不超过k次反射后击中所次反射后击中所有目标的前提下，距离的有目标的前提下，距离的最大值最小。最大值最小。N=4M=4k=2模拟退火算法的例子激光坦克（激光坦克（CTSC2007）N=4M=4k=2 本题是一个最大距离本题是一个最大距离最小的问题，如果不考虑最小的问题，如果不考虑镜子的因素，可以使用最镜子的因素，可以使用最远点远点Voronoi图或前面的随图或前面的随机增量算法来解决，但是机增量算法来解决，但是镜子的存在使得问题非常镜子的存在使得问题非常棘手。棘手。模拟退火算法的例子激光坦克（激光坦克（CTSC2007）N=4M=4k=2 此时，模拟退火算法此时，模拟退火算法的可移植性的优势就体现的可移植性的优势就体现了出来，我们可以在主算了出来，我们可以在主算法的框架上，分别独立编法的框架上，分别独立编写与镜子不同次数相交的写与镜子不同次数相交的评价函数。评价函数。激光坦克的得分与代价Testcasek不处理反射不处理反射处理一次反射处理一次反射处理两次反射处理两次反射601010102110101031010107111010521010108261010139101043101010930010105000总得分总得分568090代码长度代码长度90160240300总结本文通过几道例题，以及体现出的一种思本文通过几道例题，以及体现出的一种思想，希望能为大家打开一扇窗，在遇到几想，希望能为大家打开一扇窗，在遇到几何问题的时候多一种思路。当然，随机化何问题的时候多一种思路。当然，随机化思想的灵活运用，是在对于经典问题熟练思想的灵活运用，是在对于经典问题熟练掌握的前提下的，因为创新永远建立在扎掌握的前提下的，因为创新永远建立在扎实的基础之上。实的基础之上。Expensive Drink题目描述题目描述有有3种物品的价格（设为种物品的价格（设为x,y,z）要满足）要满足n组约束组约束且且求求 的最大值的最大值Expensive Drink解解解结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。Expensive Drink想法：枚举两个平面，想法：枚举两个平面，得到一条直线。得到一条直线。枚举其余约束，枚举其余约束，切割该直线。切割该直线。结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。结论结论1：如果存在解，必然存在于三个平面的交点上。：如果存在解，必然存在于三个平面的交点上。Expensive Drink想法：枚举两个平面，想法：枚举两个平面，得到一条直线。得到一条直线。枚举其余约束，枚举其余约束，切割该直线。切割该直线。直到最后剩下一直到最后剩下一条线段。条线段。引理引理1 只有线段的两个端点可能是的目标函数的只有线段的两个端点可能是的目标函数的 最大值。最大值。Expensive Drink引理引理2 不会有某三个平面的交点被遗漏。不会有某三个平面的交点被遗漏。结论结论2：只有线段的两个端点可能成为解。：只有线段的两个端点可能成为解。Expensive Drink引理引理1 只有线段的两个端点可能是的目标函数的最大值。只有线段的两个端点可能是的目标函数的最大值。Expensive Drink引理引理2 不会有某三个平面的交点在计算中被遗漏。不会有某三个平面的交点在计算中被遗漏。具体的实现 因为空间中的直线情况比较多、比较复杂，因此我们可以因为空间中的直线情况比较多、比较复杂，因此我们可以使用参数方程进行统一表示。使用参数方程进行统一表示。这样，我们对直线的切割就转化成为对于参数值求交的过这样，我们对直线的切割就转化成为对于参数值求交的过程。程。最后是求解参数方程的过程。首先我们假设枚举的两个平最后是求解参数方程的过程。首先我们假设枚举的两个平面不平行，我们任意消去面不平行，我们任意消去x、y、z中的一个，得到一个二元中的一个，得到一个二元（一元）一次方程。取任意一个自由元的方程的系数，经过两（一元）一次方程。取任意一个自由元的方程的系数，经过两次回代即可求出直线的参数方程。次回代即可求出直线的参数方程。三维线性规划O(n)的算法这题理论上存在这题理论上存在O(n)复杂度的方法。但是该算法有两点复杂度的方法。但是该算法有两点弊病：弊病：1)时间复杂度中隐藏的常数巨大。本题中在时间上的优时间复杂度中隐藏的常数巨大。本题中在时间上的优势微小。（势微小。（n仅仅100。）。）2)编程复杂度过大。其实编程复杂度过大。其实O(n)的算法并不难想：每次加的算法并不难想：每次加入一个半空间后，如果先前的解不成立需要更新，此时就入一个半空间后，如果先前的解不成立需要更新，此时就是要将目标向量在平面上的投影作为新的目标向量，将其是要将目标向量在平面上的投影作为新的目标向量，将其他半空间转换成半平面做一次二维线性规划。几次空间和他半空间转换成半平面做一次二维线性规划。几次空间和平面间的转换与旋转，将该算法仅仅保留在理论上。平面间的转换与旋转，将该算法仅仅保留在理论上。我们使用随机思想是希望事半功倍、化繁为简，因此本算我们使用随机思想是希望事半功倍、化繁为简，因此本算法有悖于我们的初衷。而且无论在信息学还是法有悖于我们的初衷。而且无论在信息学还是ACM赛场赛场上比赛的时间都是有限的，因此本算法虽然存在，但并不上比赛的时间都是有限的，因此本算法虽然存在，但并不值得推广。值得推广。数值概率算法数值概率算法常用于数值问题的求解。这类算法数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，算时间的增加不断提高。在许多情况下，要计算要计算出问题的精确解是不可能或没有必要的，因此用出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到满意的解。数值概率算法可得到满意的解。举个例子：计算举个例子：计算p p的近似值时，我们可以在单位圆的近似值时，我们可以在单位圆的外接矩形内随机撒的外接矩形内随机撒n个点，设有个点，设有k个点落在单位个点落在单位圆内，可以得到圆内，可以得到p p近似等于近似等于4 4k/n。舍伍德算法 舍伍德算法总能求得问题的一个解，且所求得的舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。解总是正确的。当一个确定性算法在最坏情况下当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有的计算复杂性与其在平均情况下的计算复杂性有较大差别时，较大差别时，可以在这个确定算法中引入随机性可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。好坏实例间的这种差别。舍伍德算法精髓不是避舍伍德算法精髓不是避免算法的最坏情况的发生，而是设法消除这种最免算法的最坏情况的发生，而是设法消除这种最坏行为与特定实例之间的关联性。坏行为与特定实例之间的关联性。舍伍德算法的舍伍德算法的一个最广泛的应用就是快速排序的随机化实现。一个最广泛的应用就是快速排序的随机化实现。随机洗牌算法这个问题不复杂，以下代码就可以以线性这个问题不复杂，以下代码就可以以线性的时间复杂度得到一个的时间复杂度得到一个1n的随机排列。的随机排列。（记录在数组（记录在数组O中。）中。）Algorithm Random_shufflefor i 2 to n 交换交换Oi，Orandom(i)（其中（其中random(n)返回一个返回一个1n的随机数。）的随机数。）蒙特卡罗抽样它的基本思想是，对于所求的问题，通过它的基本思想是，对于所求的问题，通过试验的方法和大样本来模拟，得到这个随试验的方法和大样本来模拟，得到这个随机变量的期望值，并用它作为问题的解。机变量的期望值，并用它作为问题的解。它是以一个概率模型为基础，按照这个模它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，型所描绘的过程，通过模拟实验的结果，作为问题的近似解的过程。作为问题的近似解的过程。模拟退火算法的原理模拟退火算法是一种元启发式（模拟退火算法是一种元启发式（Meta-Heuristics）算）算法，来源于固体退火原理，将固体加温至充分高，再让其法，来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度准则，粒子在温度T时趋于平衡的概率为时趋于平衡的概率为 ，其中，其中E为温度为温度T时的内能，时的内能，E为其改变量，为其改变量，k为为Boltzmann常数。常数。元启发式算法元启发式算法（元启发式算法（Meta-Heuristics）是一）是一种启发式策略，意思就是指导启发式算法种启发式策略，意思就是指导启发式算法进行工作的方法。常见的元启发式算法有：进行工作的方法。常见的元启发式算法有：模拟退火算法模拟退火算法遗传算法遗传算法蚁群算法蚁群算法PSO(粒子群优化粒子群优化)精确度分析的一个例子最优解附近（如点最优解附近（如点A，B）的点非常稀少且）的点非常稀少且距离很远，因此有候选解在它周围（所在距离很远，因此有候选解在它周围（所在的的Delaunay三角剖分区域内）的概率是三角剖分区域内）的概率是很大的。而且此时的距离比较大，我们对很大的。而且此时的距离比较大，我们对方向进行多次尝试，因此调整出去的概率方向进行多次尝试，因此调整出去的概率也很小。也很小。精确度分析的一个例子如图，假设一次随机调整成功的如图，假设一次随机调整成功的概率为概率为P，则，则 精确度分析的一个例子若我们的若我们的L取取30(d=0,g g=0)D D取到取到最小值最小值0.085r。1）因为此时两者垂直，因因为此时两者垂直，因此对于答案的影响很小。此对于答案的影响很小。2）我们使用了放缩过程，我们使用了放缩过程，把把g g、d都当成都当成0计算，因计算，因此实际的调整概率还要更此实际的调整概率还要更高。高。精确度分析的一个例子但是如果题目的精度要求非常高，怎么办但是如果题目的精度要求非常高，怎么办呢？既然很难随机到向量和呢？既然很难随机到向量和Voronoi边平行，边平行，我们可以直接枚举平行于我们可以直接枚举平行于Voronoi边的向量，边的向量，虽然在时间上付出一点代价，但是在调整虽然在时间上付出一点代价，但是在调整成功的概率和解的精度无疑将大大提高。成功的概率和解的精度无疑将大大提高。当然对于普通的题目（本节三道例题当然对于普通的题目（本节三道例题Run Away、Empire Strikes Back、激光坦克），、激光坦克），普通的随机调整就可以了。普通的随机调整就可以了。URAL1520：Empire Strikes Back激光坦克激光坦克TestcasekNM60200000021250312100071100003523308237013444323593183010525100多次迭代多次迭代逐步求精逐步求精可以使用随机化思想的几何题目1 Expensive Drink2 最小外接圆最小外接圆/球球3 Run Away4 Empire strikes back 5 激光坦克激光坦克6 A star not a tree?7 Mammoth HuntTopCoder Marathon中数道几何题目中数道几何题目随机增量算法随机增量算法模拟退火算法模拟退火算法调整法调整法