算法分析與复杂性理论小论文.docxVIP

算法分析与复杂性理论用拉斯维加斯算法解决n皇后问题姓名：王晓星流水号： 一、随机化算法确定性算法的每一个计算步骤都是确定的，而随机算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此随机算法可在很大程度上降低算法度。随机化算法的基本特征是对所求解问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。二、拉斯维加斯(Las Vegas)算法拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。通常采用bool型方法来表示拉斯维加斯算法。当算法找到一个解时返回true，否则false.当返回false时，说明未得到解，那么可再次独立调用该算法，在时间允许的情况一直运算到出解为止。void obstinate(Object x, Object y) {// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y bool success= false; while (!success) success=lv(x,y); } void obstinate(Object x, Object y){// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解ybool success= false;while (!success) success=lv(x,y);}设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有。解此方程得：三、n皇后问题问题描述：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1）纯拉斯维加斯随机算法求解思路对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的拉斯维加斯算法。在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后已相容地放置好，或已没有下一个皇后的可放置位置时为止。注意这里解决的是找到其中一个方法，并不是求出N皇后的全部解。具体代码如下：#include stdafx.h #include RandomNumber.h #include cmath #include iostream using namespace std; class Queen { friend void nQueen(int); private: bool Place(int k); //测试皇后k置于第x[k]列的合法性boolQueensLv(void); //随机放置n个皇后拉斯维加斯算法int n; //皇后个数int *x,*y; //解向量}; //测试皇后k置于第x[k]列的合法性bool Queen::Place(int k) { for(int j=1; jk; j++) { if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) { return false; } } return true; } //随机放置n个皇后的拉斯维加斯算法bool Queen::QueensLv(void) { RandomNumberrnd; //随机数产生器int k = 1; //下一个皇后的编号int count = 1; //在一列中，可以放置皇后的个数while((k=n)(count0)) { count = 0; for(inti=1; i=n; i++) { x[k] = i;//位置if(Place(k))