广东中山一中广东中山一中广东中山一中广东中山一中 顾研顾研顾研顾研感受随机的美浅谈随机化思想在几何问题中的应用算法合集之浅谈随机化思想在几何问题中的应用引入 随着信息学的发展，近几年，各种各样灵随着信息学的发展，近几年，各种各样灵活的几何题目层出不穷。因此随机算法和随机活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。化思想便有了表演的舞台。随机算法的特点是：随机算法的特点是：简单简单、快速快速、灵活灵活和和易于并行化易于并行化，这些特点都会在论文中得到体现。，这些特点都会在论文中得到体现。算法合集之浅谈随机化思想在几何问题中的应用概览数值概率算法数值概率算法拉斯维加斯算法拉斯维加斯算法蒙特卡罗算法蒙特卡罗算法舍伍德算法舍伍德算法第一部分第一部分 随机算法简介随机算法简介第二部分第二部分随机增量算法随机增量算法第三部分第三部分模拟退火算法模拟退火算法算法合集之浅谈随机化思想在几何问题中的应用随机增量算法的一个例子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 不会有某三个平面的交点在计算中被遗漏。不会有某三个平面的交点在计算中被遗漏。算法合集之浅谈随机化思想在几何问题中的应用具体的实现 因为空