文档介绍：第九章概率算法
*
计算机算法设计与分析
*
本讲稿第一页，共三十八页
概率计算
概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。
它的基本特征是计算具有不确定性。
它的解也不一定是最优解。
它在很大程度上能er /= 2; a = a * a % n;}
if (a * other % n == 1) return True;
return False;
}
本讲稿第十一页，共三十八页
合数的见证者
设n为测试的自然数，不妨设n是大于2的奇数，则有n – 1 = 2im，其中i是非负整数，m是正奇数。取一自然数b，1 < b < n，记W(b)为条件：
① bn–1 ≠ 1 (mod n) 或
②i，使得m = (n–1)/2i 且 1 < gcd(bm–1, n) < b。
若①或②中有一个为真，就认为W(b)满足，则n必定是合数，我们称b是n为合数的见证者。
若n有见证者，则n必定为合数。
本讲稿第十二页，共三十八页
合数的见证者多于一半
Miller已经证明，存在常数c，使得当n为合数时，在[1, c(log n)2]范围内有见证者。
Rabin证明了：如果n是合数，则
|{b|1<b<n，W(b)满足}|≥(n–1)/2
即，在小于n的自然数中有多半是n的见证者。
任取一个自然数b < n，若b不是n的见证者，则n是合数的概率小于1/2。若随机取m个数都不是见证者，则n是合数的概率小于1/2m。
本讲稿第十三页，共三十八页
Miller-Rabin素数判定概率算法
Bool Miller_Rabin_Prime(int n){
b[1 .. m] = RandomSampling(n, m);
/*随机选取m个大于1小于n的无重复的自然数
for (j = 1; j <= m; j++)
if (W(b[j]) 满足) return False;
return True;
}
若m = 100，则n不是素数的概率小于1/2100。
本讲稿第十四页，共三十八页
Las Vegas算法
Las Vegas算法的特点是随机性地进行决策。
例如对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。若成功了，便找到了一个解；若失败了，就整个重来，再随机产生另外一组王后的位置。这样作，直至找到解。
此算法能显著地改进算法的有效性，甚至对迄今为止找不到有效算法的问题，也能得到满意的结果。
本讲稿第十五页，共三十八页
瞎子爬山法与局部最优
更一般的求解问题的方法是瞎子爬山法。
一个瞎子从山脚开始，试探着一步一步向上爬，就可以一直爬到山顶。
可是，他爬上的可能只是个小山头，更高的山还在后面。而他无法从小山头下来，也就无法爬到更高的山头了。
这种情形就被称为陷入了局部最优。
如何避免陷入局部最优是求解问题中要注意的一个重要问题。
本讲稿第十六页，共三十八页
进化算法(Evolutionary Algorithm)
达尔文的进化论：适者生存，优胜劣汰。
1975年霍兰(Holland)提出了遗传算法，通过模拟生物进化的过程概率搜索最优解。
遗传算法首先产生所谓的个体种群，每个个体是编码的二进制串(又称为染色体)。
然后对个体进行随机的选择，再经过复制、交叉和变异产生下一代的种群。
就这样经过一代一代的进化，最终获得满意的个体(即问题的解)。
本讲稿第十七页，共三十八页
进化计算中的基本算子
适应值f(xi)：给出个体xi优劣；
选择算子：对个体进行概率选择。
个体的概率为p(xi) = f(xi) / ∑f(xj)，优秀的个体具有较高的概率。
最常用的选择算子为轮盘赌的方法。这样优秀个体具有较高的被选中的概率。同时差的个体也有被选中的可能。
复制算子copy：对选中的个体进行复制。
交叉算子：将两个个体染色体中的某个位彼此交换，从而形成两个新的个体。
变异算子m：改变一个个体的染色体的某些位，得到一个新的个体。
停止准则：决定算法停止的准则
本讲稿第十八页，共三十八页
进化算法的基本框架
t = 0 // t为代数；
初始化：P(0)={a1(0), …, an(0)}//初始种群P(0)
度量：P(0): {f(a1(0)), …, f(an(0))};
while (P(t)不满足停止准则) {
交叉：P’(t) = (P(t));
变异：P’’(t) = m(P’(t));
度量：P’’(t)：{f(a1’’(t)), …, f(an’’(t)));
选择：P(t+1) = P’’(t) ∪Q;
t = t +1; }