文档介绍:第九章概率算法
第1页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
1
计算机算法设计与分析
概率计算
概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。
它的基本特征是计算具有022年,5月20日,14点43分,星期日
2022/8/22
9
计算机算法设计与分析
Fermat素数测试法
Fermat定理: 若p是素数,则对任意整数a,gcd(a, p) = 1,则有ap–1≡1 (mod p)。
显然,对素数p有pp–1 ≡1 (mod p)。
对于一般的整数n,满足nn–1≡1 (mod n)的数目很少。满足的称为伪素数。
就用是否满足nn–1≡1 (mod n)来判断n是否为素数。
第10页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
10
计算机算法设计与分析
Fermat素数测试法
Bool Fermat_Prime(int n) {
a = 2; power = n – 1; other = 1;
while(power > 1) {
if (power % 2 = = 1) {other *= a; other %= n;}
power /= 2; a = a * a % n;}
if (a * other % n == 1) return True;
return False;
}
第11页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
11
计算机算法设计与分析
合数的见证者
设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必定为合数。
第12页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
12
计算机算法设计与分析
合数的见证者多于一半
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。
第13页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
13
计算机算法设计与分析
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。
第14页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
14
计算机算法设计与分析
Las Vegas算法
Las Vegas算法的特点是随机性地进行决策。
例如对n后问题,Las Vegas算法是随机地产生一组王后放置的位置。若成功了,便找到了一个解;若失败了,就整个重来,再随机产生另外一组王后的位置。这样作,直至找到解。
此算法能显著地改进算法的有效性,甚至对迄今为止找不到有效算法的问题,也能得到满意的结果。
第15页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
15
计算机算法设计与分析
瞎子爬山法与局部最优
更一般的求解问题的方法是瞎子爬山法。
一个瞎子从山脚开始,试探着一步一步向上爬,就可以一直爬到山顶。
可是,他爬上的可能只是个小山头,更高的山还在后面。而他无法从小山头下来,也就无法爬到更高的山头了。
这种情形就被称为陷入了局部最优。
如何避免陷入局部最优是求解问题中要注意的一个重要问题。
第16页,共38页,2022年,5月20日,14点43分,星期日
2022/8/22
16
计算机算法设计与分析
进化算法(Evolutionary