文档介绍：概率算法和近似算法
*
随机数
随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。
线性同余法是产生伪随机数的最常用的方法。由(x)返回的解未必是y0。
称上述算法MC(x)是偏y0的算法。
重复调用一个一致的，p正确偏y0蒙特卡罗算法k次，可得到一个O(1-(1-p)k)正确的蒙特卡罗算法，且所得算法仍是一个一致的偏y0蒙特卡罗算法。
*
素数测试
Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)! -1(mod n)。
费尔马小定理：如果p是一个素数，且0<a<p，则ap-1(mod p)。
二次探测定理：如果p是一个素数，且0<x<p，则方程x21(mod p)的解为x=1，p-1。
private static int power(int a, int p, int n)
{// 计算 ap mod n，并实施对n的二次探测
int x, result;
if (p==0) result=1;
else {
x=power(a,p/2,n); // 递归计算
result=(x*x)%n; // 二次探测
if ((result==1)&&(x!=1)&&(x!=n-1))
composite=true;
if ((p%2)==1) // p是奇数
result=(result*a)%n;
}
return result;}
public static boolean prime(int n)
{// 素数测试的蒙特卡罗算法
rnd = new Random();
int a, result;
composite=false;
a=(n-3)+2;
result=power(a,n-1,n);
if (composite||(result!=1)) return false;
else return true;
}
算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。
*
主元素问题
设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。
public static boolean majority(int[]t, int n)
{// 判定主元素的蒙特卡罗算法
rnd = new Random();
int i=(n)+1;
int x=t[i]; // 随机选择数组元素
int k=0;
for (int j=1;j<=n;j++)
if (t[j]==x) k++;
return (k>n/2); // k>n/2 时t含有主元素
}
public static boolean majorityMC(int[]t, int n, double e)
{// 重复é ù次调用算法majority
int k= (int) ((1/e)/(2));
for (int i=1;i<=k;i++)
if (majority(t,n)) return true;
return false;
}
对于任何给定的>0，算法majorityMC重复调用log(1/) 次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法majorityMC所需的计算时间显然是O(nlog(1/ ))。
*
近似算法
*
近似算法
迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。
(1)只对问题的特殊实例求解
(2)用动态规划法或分支限界法求解
(3)用概率算法求解
(4)只求近似解
(5)用启发式方法求解
本章主要讨论解NP完全问题的近似算法。
*
近似算法的性能
若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最