概率算法的介绍与分析
- 格式：doc
- 大小：28.50 KB
- 文档页数：4
算法分析与设计课程课外学习论文
概率算法的介绍与分析
摘要：介绍概率算法，以主元素问题与n皇后问题为例重点介绍并分析蒙特卡洛算法以及拉斯维加斯算法，以及算法应用方法。
关键词：概率算法；蒙特卡洛算法；拉斯维加斯算法
一、引言
很多算法的每一个计算步骤都是固定的，而概率算法允许算法在执行的过程中随机选择下一个计算步骤。
许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。
因此概率算法可在很大程度上降低算法的复杂度。
概率算法大致分为:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
本文将重点介绍蒙特卡洛算法以及拉斯维加斯算法。
二、蒙特卡洛算法
1、产生随机数的机制
随机数在概率算法设计中扮演着十分重要的角色。
在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。
产生随机数最常用的方法是线性同余法。
由线性同余法产生的随机序列a1,a2,...,an满足
其中,b>=0, c>=0, d>=m。
d称为该随机序列的种子。
当a，c，m确定后，随着d的不同产生不同的随机数列，为了使随机数数列的随机性能好，我们通常取m充分大的素数，而且取gcd(m，a)=1。
2、蒙特卡洛算法
如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。
对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，并选择出现频次最高的解即可。
例：主元素问题
设T[1:n]是一个含有n个元素的数组。
当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。
判断所给数组是否含有主元素。
对于任何给定的ε>0，算法majorityMC重复调用 log(1/ε) 次算法majority。
它是一个偏真蒙特卡罗算法，且其错误概率小于ε。
算法majorityMC所需的计算时间显然是O(nlog(1/ ε))。
源码见附录一。
三、拉斯维加斯算法
拉斯维加斯算法思想：
void obstinate(Object x, Object y)
{// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y
bool success= false;
while (!success) success=lv(x,y);
}
例：n皇后问题
n 皇后问题：在n×n 格的棋盘上放置彼此不受攻击的n 个皇后．按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子．n 皇后问题等价于在n×n 格的棋盘上放置n个皇后，任何2 个皇后不放在同一行或同一列或同一斜线上．
对于n 皇后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更像是随机放置
的．由此想到可采用拉斯维加斯算法，在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n 个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止．
方法queensLV ( ) 实现在棋盘上随机放置n个皇后的拉斯维加斯算法．
通过反复调用随机放置n 个皇后的拉斯维加斯算法queensLV ( )，直至找到n 皇后问题的一个解．
源码见附录二
四、算法比较
蒙特卡罗算法用于求问题的准确解。
对于许多问题来说，近似解毫无意义。
例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。
又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。
用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。
求得正确解的概率依赖于算法所用的时间。
算法所用的时间越多，得到正确解的概率就越高。
蒙特卡罗算法的主要缺点就在于此。
一般情况下，无法有效判断得到的解是否肯定正确。
拉斯维加斯算法求得的解肯定是正确的，不会得到不正确的解，但是有时候用拉斯维加斯算法可能找不到解。
使用拉斯维加斯算法求解同一问题的同一实例，能够得到相同的结果，但算法的执行时间会不一样。
拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。
五、学习心得和体会（黑体小四号两端对齐）
概率算法在求解诸如定积分，非线性方程以及诸多实际问题中应用广泛，很多情况下可以减小算法时间空间复杂度。
把随机性注入到算法中，使得算法设计与分析的灵活性及解决问题的能力大为改观，但准确性较低，正所谓鱼和熊掌不可兼得。
参考文献：（黑体小四号两端对齐）
1. 概率算法. /view/1082614.htm
2. 王晓东. 计算机算法设计与分析.（第二版）. 电子工业出版社. 2006
3. 朱珣. 分班问题的拉斯维加斯算法实现. 江汉大学学报(自然科学版)第35卷第4期. 2007年12月
4. 邓宏涛，朱珣. N皇后问题LasVegas优化算法的实现. 江汉大学学报(自然科学版)第34卷第4期. 2006年12月
附录一：主元素问题源码
template<class Type>
bool Majority(Type *T, int n)
{// 判定主元素的蒙特卡罗算法
int i=rnd.Random(n)+1;
Type 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含有主元素
}
template<class Type>
bool MajorityMC(Type *T, int n, double e)
{// 重复调用算法Majority
int k=ceil(log(1/e)/log(2));
for (int i=1;i<=k;i++)
if (Majority(T,n)) return true;
return false;
}
附录二：n皇后问题源码：
private static Boolean queensLV ( )
{ //随机放置n 个皇后的Las V egas 算法
rnd=new Random ( );
int k=1;
int count=1;
while ((k<=n) && (count>0)) {
count=0;
int j=0;
for ( int i=1; i<=n; i++ ) {
x k =i;
if (place (k))
if (rnd.random ++count) ==0) j=i; //随机位置
}
if (count>0) x k++ =j;
}
return (count>0); // count>0 表示放置成功
}
public static void nQueen
{ //解n 皇后问题的Las V egas 算法
//初始化x
x=new int n+1 ;
for int i=0; i<=n; i++ ) x i =0;
// 反复调用随机放置n 个皇后的Las V egas 算法，直至放置成功
while ! queensLV ( ));
}。
