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

广东中山一中 顾研,感受随机的美,浅谈随机化思想在几何问题中的应用,引入,随着信息学的发展，近几年，各种各样灵活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。,随机算法的特点是：简单、快速、灵活和易于并行化，这些特点都会在论文中得到体现。,概览,数值概率算法拉斯维加斯算法蒙特卡罗算法舍伍德算法,第一部分 随机算法简介,第二部分 随机增量算法,第三部分 模拟退火算法,随机增量算法的一个例子,Expensive Drink ( Beijing Site, 2007 )（经过抽象）,maximize,s.t.,单纯形法、内点法？,(n100),Expensive Drink,随机增量算法的一般步骤,发现问题的本质,提出算法,改造成增量算法,加入随机,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定义为调整向量的模长。估价函数定义为到最近点的距离。如果函数值变大，则更新原解。,求区域中一点，到某个点集中的点的最小距离最大。,通过类比的思想， 引入模拟退火算法：,最小距离问题,模拟退火算法有并行性。,求区域中一点，到某个点集中的点的最小距离最大。,不断重复这一过程，直到步长足够小。取当前最优解作为答案。,通过类比的思想， 引入模拟退火算法：,模拟退火算法的应用,模拟退火算法有很强的可移植性。,模拟退火算法的例子,激光坦克（CTSC2007）,在平面上有N个坦克，M个镜子。要求在平面内放置一个激光发射器，使得它在发出的每束激光经过不超过k次反射后击中所有目标的前提下，距离的最大值最小。,N=4 M=4 k=2,模拟退火算法的例子,激光坦克（CTSC2007）,N=4 M=4 k=2,本题是一个最大距离最小的问题，如果不考虑镜子的因素，可以使用最远点Voronoi图或前面的随机增量算法来解决，但是镜子的存在使得问题非常棘手。,模拟退火算法的例子,激光坦克（CTSC2007）,N=4 M=4 k=2,此时，模拟退火算法的可移植性的优势就体现了出来，我们可以在主算法的框架上，分别独立编写与镜子不同次数相交的评价函数。,激光坦克的得分与代价,总结,本文通过几道例题，以及体现出的一种思想，希望能为大家打开一扇窗，在遇到几何问题的时候多一种思路。当然，随机化思想的灵活运用，是在对于经典问题熟练掌握的前提下的，因为创新永远建立在扎实的基础之上。,谢谢！,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的近似值时，我们可以在单位圆的外接矩形内随机撒n个点，设有k个点落在单位圆内，可以得到p近似等于4k/n。,舍伍德算法,舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况的发生，而是设法消除这种最坏行为与特定实例之间的关联性。舍伍德算法的一个最广泛的应用就是快速排序的随机化实现。,随机洗牌算法,这个问题不复杂，以下代码就可以以线性的时间复杂度得到一个1n的随机排列。（记录在数组O中。）,Algorithm Random_shuffle for 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=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 back 5 激光坦克 6 A star not a tree? 7 Mammoth Hunt TopCoder Marathon中数道几何题目,随机增量算法,模拟退火算法,调整法,