拉斯维加斯算法与N皇后问题 | 码农家园

关注
拉斯维加斯算法与N皇后问题 | 码农家园www.shan-machinery.com拉斯维加斯算法与N皇后问题

拉斯维加斯算法拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解,这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似,拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足够多次,可使求解失败的概率任意小。N皇后的求解方法:消极:LV算法过于消极,一旦失败,从头再来。乐观:回溯算法过于乐观,一旦放置某个皇后失败,就进行系统回退一步的策略,而这一步往往不一定有效折中:一般情况下更好,先用LV方法随机的放置前若干个结点,然后使用回溯法放置后若干个结点随机放置位置策略和回溯法相结合求解n皇后问题

RandomNumber.h头文件

1234567891011121314151617181920212223242526#include//利用线性同余法产生的伪随机数 const unsigned long maxshort=65536;const unsigned long multipliter=1194211693L;const unsigned adder=12345L;class RandomNumber{    private:        unsigned long randSeed;    public:        RandomNumber(unsigned long s=0);        unsigned short Random(unsigned long n);        double fRandom(void);};RandomNumber::RandomNumber(unsigned long s){    if(s==0)        randSeed=time(0);    else        randSeed=s; }unsigned short RandomNumber::Random(unsigned long n){    randSeed=multipliter*randSeed+adder;    return (unsigned short)((randSeed>>16)%n);}  double RandomNumber::fRandom(void){    return Random(maxshort)/double(maxshort);}

主文件:

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include#include #include#include"RandomNumber.h" using namespace std;class Queen{    friend bool nQueen(int);private:    bool Place(int k);    bool Backtrack(int t);    bool QueensLV(int stop);    int n,*x,*y;    }; bool Queen::Place(int k){   //测试皇后k置于第x[k]列的合法性     for (int j=1;jn){        for(int i=1;i0表示放置成功   }bool nQueen(int n){    Queen X;    X.n=n;    int *p=new int [n+1];    int *q=new int [n+1];    for(int i=0;i15)        stop=n-15;    bool found=false;    while(!X.QueensLV(stop));    // 算法的回溯搜索部分    if(X.Backtrack(stop+1)){        for(int i=1;ihttps://www.shan-machinery.com