chapter—8随机算法.ppt

南京理工大学 反复调用Las Vegas型8皇后问题的随机算法，直到得到问题的一个解。 将随机性算法与回溯法相结合，会获得更好的效果。可在棋盘上若干行随机放置相容的皇后，然后在其他行用回溯法继续放置，直到找到一个解或宣布算法失败。 特点：随机放置的皇后越多，回溯法有哪些信誉好的足球投注网站所需时间越少，但失败的概率越大。 南京理工大学 将串匹配问题的Monte Carlo算法转换为Las Vegas算法 Las Vegas算法特点：要么找到正确解，要么算法失败。 策略：只要产生匹配，就测试模式串Y与子串Xj是否相等，以确保找到正确解。 南京理工大学 Las Vegas算法时间复杂度 O(n+m) × (1-1/n) + O(mn)×(1/n) = O(n+m) 其中： 1-1/n为Monte Carlo算法成功的概率， 1/n为调用Las Vegas算法的概率， O(mn)为发生假匹配时，用于“比较Y与Xj是否相等”操作的最坏时间复杂度。(最坏情况：每次都发生假匹配,则有：1≤j≤n-m+1,每次耗时O(m)，共O(mn)) 至此，找到了一个总是有效的模式匹配算法，复杂度为O(n+m). 南京理工大学 舍伍德(Sherwood)型随机算法 很多算法对不同的输入实例，运行时间差别很大。例如快速排序算法。此时，可通过舍伍德型随机算法来消除算法的时间复杂性与输入实例之间的关系。 例： 快速排序问题： 6, 13, 19, 23, 31, 35, 58 一次划分结果： 6, {13, 19, 23, 31, 35, 58} 随机选择主元： 23, 13, 19, 6, 31, 35, 58 一次划分结果： {6,13,19}, 23, {31, 35, 58} 南京理工大学 随机化快速排序算法 输入：n个元素的数组A[1,…,n] 输出：A中元素的非降序排列 random_quicksort(low, high) 1. if low high then 2. v ← random(low, high) 3. 互换 A[low]和A[v] 4. split(A[low…high], w) //w是主元的新位置 5. random_quicksort(low, w-1) 6. random_quicksort(w+1, high) 7.end if 舍伍德型随机算法总能求得问题的一个正确解，但其平均复杂性与最坏复杂性并没有改进。换言之，该型随机算法不能避免最坏情况，但能尽量消除输入实例对算法性能的影响。 南京理工大学 作业 14.10, 14.16 南京理工大学 随机算法Random Algorithm 南京理工大学 随机算法的设计思想 允许结果以较小的概率出现错误，以此为代价，获得算法运行时间的大幅度减少。如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解答，但是该算法能接受小概率的错误，那么采用随机算法就可以快速地找到这个问题的解。 例如：判断表达式f(x1, x2,…, xn)是否恒等于0，若用解析的方式来判断非常费时。随机算法首先随机生成一个n元向量(r1, r2,…, rn)，若f(r1, r2,…, rn) ≠0，则表达式f≡0显然不成立； 若f(r1, r2,…, rn) =0，或者是f≡0，或者是选择的(r1, r2,…, rn)比较凑巧，那么多试验几次，若继续得到f(r1, r2,…, rn) =0的结论，就可以得出f(r1, r2,…, rn)≡ 0的结论，并且试验的次数越多，出错的概率越小。 南京理工大学 随机数发生器 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足 其中b=0，c=0，d=m。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。 南京理工大学 圆周率计算 r public static double darts(int n) { // 用随机投点法计算pi值 int k=0; for (int i=1;i =n;i++) { double x=dart.fRandom(); double y=dart.fRandom();