0047算法笔记——【随机化算法】拉斯维加斯(Las Vegas)算法和n后问题

《0047算法笔记——【随机化算法】拉斯维加斯(Las Vegas)算法和n后问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、拉斯维加斯(LasVegas)算法   拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。[cpp] viewplain copy1.void obstinate(Ob

2、ject x, Object y)  2.{// 反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解y  3.    bool success= false;  4.    while (!success) success=lv(x,y);  5.}      设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间,s(x)和e(x)分别是算法对于具体实例

3、x求解成功或求解失败所需的平均时间，则有。解此方程得：   2、n后问题   问题描速：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。   1)纯拉斯维加斯随机算法求解思路    对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后

4、与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。    具体实现代码如下：   1、RandomNumber.h[cpp] viewplain copy1.#include"time.h"  2.//随机数类  3.const unsigned long maxshort = 65536L;  4.const unsigned long multiplier = 1194211693L;  5.const unsigned long adder = 12

5、345L;  1.  2.class RandomNumber  3.{  4.    private:  5.        //当前种子  6.        unsigned long randSeed;  7.    public:  8.        RandomNumber(unsigned long s = 0);//构造函数，默认值0表示由系统自动产生种子  9.        unsigned short Random(unsigned long n);//产生0：n-1之间的

6、随机整数  10.        double fRandom(void);//产生[0,1)之间的随机实数  11.};  12.  13.RandomNumber::RandomNumber(unsigned long s)//产生种子  14.{  15.    if(s == 0)  16.    {  17.        randSeed = time(0);//用系统时间产生种子  18.    }  19.    else  20.    {  21.        randSee

7、d = s;//由用户提供种子  22.    }  23.}  24.  25.unsigned short RandomNumber::Random(unsigned long n)//产生0：n-1之间的随机整数  26.{  27.    randSeed = multiplier * randSeed + adder;//线性同余式  28.    return (unsigned short)((randSeed>>16)%n);  29.}  30.  31.double Rando

8、mNumber::fRandom(void)//产生[0,1)之间的随机实数  32.{  33.    return Random(maxshort)/double(maxshort);  34.}     2、7d4d1.cpp[cpp] viewplain copy1.//随机化算法 拉斯维加斯算法 n后问题  2.#include "stdafx.h"  3.#include "RandomNumber.h"  4.#include   5.#include