概率算法和近似算法ppt课件

1、随机数在概率算法设计中扮演着非常重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中运用的随机数都是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,an满足, 2 , 1mod)(10nmcbaadann其中b0，c0，dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性实际研讨的内容，已超出本书讨论的范围。从直观上看，m应获得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点

2、。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因此所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而 。4422rrnk4public static double darts(int n) / 用随机投点法计算值 int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)0。设t(x)是算法obstinate找到详细实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于详细实例x求解胜利或求解失败所需的平均时间，那么有

3、：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的拉斯维加斯算法。 在棋盘上相继的各行中随机地放置皇后，并留意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。假设将上述随机放置战略与回溯法相结合，能够会获得更好的效果。可以先在棋盘的假设干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就

4、越少，但失败的概率也就越大。 stopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.11在实践运用中常会遇到一些问题，不论采用确定性算法或概率算法都无法保证每次都能得到正确的解答。蒙特卡罗算法那么在普通情况下可以保证对问题的一切实例都以高概率给出正确解，但是通常无法断定一个详细解能否正确。设p是一个实数，且1/2pn/2时，称元素x是数组T的主元素。 public static boolean majority(intt, int n) / 断定主元素的蒙特卡罗算法 rnd = new Rand

5、om(); int i=rnd.random(n)+1; int x=ti; / 随机选择数组元素 int k=0; for (int j=1;jn/2); / kn/2 时t含有主元素 public static boolean majorityMC(intt, int n, double e) / 反复 次调用算法majority int k= (int) Math.ceil(Math.log(1/e)/Math.log(2); for (int i=1;i0，算法majorityMC反复调用log(1/) 次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法major

6、ityMC所需的计算时间显然是O(nlog(1/ )。近似算法近似算法近似算法近似算法 迄今为止，一切的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题战略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法。近似算法的性能近似算法的性能 假设一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目的函数值为c，那么将该近似算法的性能比定义为= 。在通常情况下，该性能比是问题输入规模n的一个函数(n)，即 (n)。cccc*,*maxcc

7、cc*,*max该近似算法的相对误差定义为= 。假设对问题的输入规模n，有一函数(n)使得 (n)，那么称(n)为该近似算法的相对误差界。近似算法的性能比(n)与相对误差界(n)之间显然有如下关系：(n)(n)-1。 *ccc *ccc 子集合问题的近似算法子集合问题的近似算法 问题描画：设子集和问题的一个实例为S,t。其中，S=x1，x2，xn是一个正整数的集合，t是一个正整数。子集和问题断定能否存在S的一个子集S1，使得 。txSx 1子集和问题的指数时间算法子集和问题的指数时间算法int exactSubsetSum (S,t) int n=|S|； L0=0； for (int i=1

8、；i=n；i+) Li=mergeLists(Li-1,Li-1+Si)； 删去Li中超越t的元素； return max(Ln)；算法以集合算法以集合S=x1S=x1，x2x2，xnxn和目的和目的值值t t作为输入。算法作为输入。算法中用到将中用到将2 2个有序表个有序表L1L1和和L2L2合并成为一合并成为一个新的有序表的算个新的有序表的算法法mergeLists(L1,L2)mergeLists(L1,L2)。 子集和问题的完全多项式子集和问题的完全多项式时间近似格式时间近似格式 基于算法exactSubsetSum，经过对表Li作适当的修整建立一个子集和问题的完全多项式时间近似格式。

9、 在对表Li进展修整时，用到一个修整参数，01。用参数修整一个表L是指从L中删去尽能够多的元素，使得每一个从L中删去的元素y，都有一个修整后的表L1中的元素z满足(1-)yzy。可以将z看作是被删去元素y在修整后的新表L1中的代表。 举例：假设=0.1，且L=10,11,12,15,20,21,22,23,24,29，那么用对L进展修整后得到L1=10，12，15，20，23，29。其中被删去的数11由10来代表，21和22由20来代表，24由23来代表。 子集和问题的完全多项式子集和问题的完全多项式时间近似格式时间近似格式对有序表L修整算法List trim(L,) int m=|L|； L1=L1； int last=L1； for (int i=2；i=m；i+) if (last(1-)*Li) 将Li参与表L1的尾部； last=Li； return L