浅谈随机化思想在几何问题中的的应用.ppt

结论1：如果存在解，必然存在于三个平面的交点上。 Expensive Drink 想法：枚举两个平面， 得到一条直线。 枚举其余约束，切割该直线。 直到最后剩下一条线段。 引理1 只有线段的两个端点可能是的目标函数的 最大值。 Expensive Drink 引理2 不会有某三个平面的交点被遗漏。 结论2：只有线段的两个端点可能成为解。 Expensive Drink 引理1 只有线段的两个端点可能是的目标函数的最大值。 Expensive Drink 引理2 不会有某三个平面的交点在计算中被遗漏。 具体的实现 因为空间中的直线情况比较多、比较复杂，因此我们可以使用参数方程进行统一表示。 这样，我们对直线的切割就转化成为对于参数值求交的过程。 最后是求解参数方程的过程。首先我们假设枚举的两个平面不平行，我们任意消去x、y、z中的一个，得到一个二元（一元）一次方程。取任意一个自由元的方程的系数，经过两次回代即可求出直线的参数方程。 广东中山一中 顾研 感受随机的美 ——浅谈随机化思想在几何问题中的应用 引入 随着信息学的发展，近几年，各种各样灵活的几何题目层出不穷。因此随机算法和随机化思想便有了表演的舞台。 随机算法的特点是：简单、快速、灵活和易于并行化，这些特点都会在论文中得到体现。 概览 数值概率算法 拉斯维加斯算法 蒙特卡罗算法 舍伍德算法 第一部分 随机算法简介 第二部分 随机增量算法 第三部分 模拟退火算法 随机增量算法的一个例子 Expensive Drink ( Beijing Site, 2007 )（经过抽象） maximize s.t. …… 单纯形法、内点法？ (n≤100) Expensive Drink 随机增量算法的一般步骤 发现问题的本质 提出算法 改造成增量算法 加入随机 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定义为调整向量的模长。估价函数定义为到最近点的距离。 如果函数值变大，则更新原解。 求区域中一点，到某个点集中的点的最小距离最大。 通过类比的思想， 引入模拟退火算法： 最小距离问题 模拟退火算法有并行性。 求区域中一点，到某个点集中的点的最小距离最大。 不断重复这一过