§1概率算法的分类 ② Monte carlo算法(MC算法) 蒙特卡洛算法1945年由J. Von neumann进行核武模拟提出 的。它是以概率和统计的理论与方法为基础的一种数值计算 方法,它是双重近似:一是用概率模型模拟近似的数值计算 二是用伪随机数模拟真正的随机变量的样本。 这里我们指的Mc算法是:若问题只有1个正确的解,而无近 似解的可能时使用MC算法 例如,判定问题只有真或假两种可能性,没有近似解 因式分解,我们不能说某数几乎是一个因子 ■特点:MC算法总是给出一个答案,但该答案未必正确,成 功即答案是正确的的概率正比于算法执行的时间 ■缺点:一般不能有效地确定算法的答案是否正确 16
16 ② Monte Carlo算法 (MC算法) 蒙特卡洛算法1945年由J. Von Neumann进行核武模拟提出 的。它是以概率和统计的理论与方法为基础的一种数值计算 方法，它是双重近似：一是用概率模型模拟近似的数值计算， 二是用伪随机数模拟真正的随机变量的样本。 这里我们指的MC算法是： 若问题只有1个正确的解，而无近 似解的可能时使用MC算法 例如，判定问题只有真或假两种可能性，没有近似解 因式分解，我们不能说某数几乎是一个因子 ◼ 特点：MC算法总是给出一个答案，但该答案未必正确，成 功(即答案是正确的)的概率正比于算法执行的时间 ◼ 缺点：一般不能有效地确定算法的答案是否正确 §1.2 概率算法的分类
§1概率算法的分类 ③ Las vegas算法(LV算法) LV算法绝不返回错误的答案。 ■特点:获得的答案必定正确,但有时它仍根本就找不 到答案。 和MC算法一样,成功的概率亦随算法执行时间增加而增 加。无论输入何种实例,只要算法在该实例上运行足够 的次数,则算法失败的概率就任意小。 ④ Sherwood算法 Sherwood算法总是给出正确的答案。 当某些确定算法解决一个特殊问题平均的时间比最坏时 间快得多时,我们可以使用 Sherwood算法来减少,甚 至是消除好的和坏的实例之间的差别
17 ③ Las Vegas算法 (LV算法) LV算法绝不返回错误的答案。 ◼ 特点：获得的答案必定正确，但有时它仍根本就找不 到答案。 和MC算法一样，成功的概率亦随算法执行时间增加而增 加。无论输入何种实例，只要算法在该实例上运行足够 的次数，则算法失败的概率就任意小。 ④ Sherwood算法 Sherwood算法总是给出正确的答案。 当某些确定算法解决一个特殊问题平均的时间比最坏时 间快得多时，我们可以使用Sherwood算法来减少，甚 至是消除好的和坏的实例之间的差别。 §1.2 概率算法的分类
Ch2数字概率算法 这类算法主要用于找到一个数字问题的近似解 §21T值计算 实验:将n根飞镖随机投向一正方形的靶子,计算落入此正方 形的内切圆中的飞镖数目k。 假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任 飞镖高手更能保证此假设成立) 设圆的半径为r,面积s=Tr2;方靶面积s2=4r2 由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比 为 n4r24 由此知: r≈4k/nk=n 18
18 这类算法主要用于找到一个数字问题的近似解 §2.1 π值计算 ◼ 实验：将n根飞镖随机投向一正方形的靶子，计算落入此正方 形的内切圆中的飞镖数目k。 假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任 一飞镖高手更能保证此假设成立) 设圆的半径为r，面积s1= πr2； 方靶面积s2=4r2 由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比 为： 由此知： Ch.2 数字概率算法 2 2 4 4 k r n r = = 4 / 4 n k n k =
§21值计算 ■求丌近似值的算法 为简单起见,只以上图的右上14象限为样本 Darts (nt k←0: fori←1 to n do{ x← uniform(0,1 y← uniform(0,1);∥随机产生点(xy) if(x2y2≤1) then k++;∥l内 return 4k/n 实验结果:m=3141592654 n=1000万:3140740,3142568(2位精确) n=1亿:3141691,3141363(3位精确) n=10亿:3141527,3141507(4位精确)
19 ◼ 求π近似值的算法 为简单起见，只以上图的右上1/4象限为样本 Darts (n) { k ← 0; for i ← 1 to n do { x ← uniform(0, 1); y ← uniform(0, 1); // 随机产生点(x,y) if (x2 + y2 ≤ 1) then k++; //圆内 } return 4k/n; } 实验结果： π=3.141592654 n = 1000万: 3.140740, 3.142568 (2位精确) n = 1亿: 3.141691, 3.141363 (3位精确) n = 10亿: 3.141527, 3.141507 (4位精确) §2.1 π值计算
§21mπ值计算 求m近似值的算法 EX1若将y← uniform(0,1)改为y←x,则上 述的算法估计的值是什么?
20 求π近似值的算法 Ex.1 若将y ← uniform(0, 1) 改为 y ← x, 则上 述的算法估计的值是什么？ §2.1 π值计算