第九章 概率算法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第九章 概率算法
概率计算 ■概率计算就是在算法中可采用随机选择计算的 步骤、元素或参数等 ■它的基本特征是计算具有不确定性 ■它的解也不一定是最优解。 ■它在很大程度上能降低算法的复杂度。 在非标准算法中普遍了应用概率方法,主要有: ■(1)直接用概率进行数值计算 ■(2)用概率/随机进行选择; ■(3)利用概率加速搜索或避免陷于局部最优 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 概率计算 ◼ 概率计算就是在算法中可采用随机选择计算的 步骤、元素或参数等。 ◼ 它的基本特征是计算具有不确定性。 ◼ 它的解也不一定是最优解。 ◼ 它在很大程度上能降低算法的复杂度。 ◼ 在非标准算法中普遍了应用概率方法，主要有： ◼ (1)直接用概率进行数值计算； ◼ (2)用概率/随机进行选择； ◼ (3)利用概率加速搜索或避免陷于局部最优
直接用概率进行数值计算 ■设fx)是[0,1上的连续函数, 求I可代xdx。 y=f(x) ■假设向单位正方形内随机 投入n个点(x2y,若有m个 G 点落入G中,则I≈m/n double Darts (int n) double x, y; int k=0 static Random number dart for(int F1; K<=n; i++)ix-dart. randome y-dart. fRandomO; if (<=f(x)k++, return k/double(n);) 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 直接用概率进行数值计算 ◼ 设f(x)是[0, 1]上的连续函数， 求I =∫ f(x)dx 0 1 。 y = f(x) G ◼ 假设向单位正方形内随机 投入n个点(xi , yi )，若有m个 点落入G中，则I≈m/n。 ◼ double Darts (int n) {double x, y; int k = 0; ◼ static RandomNumber dart; ◼ for (int i=1; i<=n; i++) {x=dart.fRandom(); ◼ y=dart.fRandom(); if (y<=f(x)) k++;} ◼ return k/double(n); }
划分基准的随机选择 ■在快速排序算法中,若用拟中位数作为划分标 准,可保证在线性时间内完成。但是确定拟中 位数要付出额外开销。若选用第一个元素为划 分基准,最坏时的时间复杂性为O(n2 ■若在算法中采用随机选择一个元素作为划分标 准,便可既保证算法的线性时间平均性能,又 避免了计算拟中位数的麻烦 也可先对数组进行“洗牌”,然后再进行确定 的排序算法。这样依然可取得同样的效果。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 划分基准的随机选择 ◼ 在快速排序算法中，若用拟中位数作为划分标 准，可保证在线性时间内完成。但是确定拟中 位数要付出额外开销。若选用第一个元素为划 分基准，最坏时的时间复杂性为O(n2 )。 ◼ 若在算法中采用随机选择一个元素作为划分标 准，便可既保证算法的线性时间平均性能，又 避免了计算拟中位数的麻烦。 ◼ 也可先对数组进行“洗牌”，然后再进行确定 的排序算法。这样依然可取得同样的效果
“洗牌”后的快速排序 void shuffle( Type a[,intn){/随机洗牌算法 static Random number md for(int 1=1; 1<n; i++)i int j=md Random(n-i+1)+i Swap(all, alD;i) Void Quiksort By Shuffle(Type all, int n)i Shuffle(a,n);∥.数组a洗牌 Quiksort(a, n ;) 2021/22 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 “洗牌”后的快速排序 ◼ void Shuffle(Type a[], int n) { //随机洗牌算法 ◼ static RandomNumber md; ◼ for (int i = 1; i < n; i++) { ◼ int j = md.Random(n – i + 1) + i; ◼ Swap(a[i], a[j]); }} ◼ Void QuiksortByShuffle(Type a[], int n) { ◼ Shuffle(a, n); //将数组a洗牌 ◼ Quiksort(a, n); }