Las Vegas

拉斯维加斯算法是一种随机化算法。总之可以用来骗分。

以下类型的问题可以使用拉斯维加斯算法：

1. 寻找任意一个可行解。

2. 最优解占可行解集的比例较大。

3. 类似质因数分解的单一解问题，可以用此算法一步步得出解。

一般形式

while(!LasVegas());

N 皇后问题

目前公认的最优 N 皇后问题的解法是回溯（搜索）。复杂度约为 O(N^N), 虽然当 N 大于 15 时搜索便开始罢工，但这样当然可以找到所有可行解。但是如果只要求找到任意一个解，回溯法就显得有些多余。

注意到 N 皇后问题的解并没有什么规律，皇后类似于随机摆放在棋盘上。所以可以利用 LasVegas 算法在前 k 行随机摆放皇后，后 (N-k) 行利用回溯完成。实践证明 1s 内可以在 N<=200 的范围内较为稳定地得出至少一个可行解。这比普通回溯法的效率高出了至少 2000 个数量级。%%%

/*
代码来源：《计算机算法设计与分析》
*/
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
class Queen
{
    friend bool nQueen(int);
private:
    bool Place(int k);              //测试皇后 K 置于 x[k] 列的合法性
    bool Backtrack(int t);          //解 n 后问题的回溯法
    bool QueenLV(int stopVegas);    //随机放置 n 个皇后的拉斯维加斯算法
    int n,*x,*y;
};
bool Queen::Place(int k)
{
    for(int j=1; j<k; j++)          //第 k 个皇后是否跟前面的皇后冲突
        if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
            return false;
    return true;
}
bool Queen::Backtrack(int t)
{
    if(t>n)                         //存放皇后放置的位置
    {
        for(int i=1; i<=n; i++)
            y[i]=x[i];
        return true;
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            x[t]=i;                 //t 皇后放在第 i 列
            if(Place(t)&&Backtrack(t+1))
                return true;
        }
    }
    return false;
}
bool Queen::QueenLV(int stopVegas)
{
                                    //随机放置 n 个皇后的拉斯维加斯算法

    int k=1;                        //随机数产生器
    int count=1;
                                    //1<=stopVagas=<n 表示允许随机放置的皇后数
    while((k<=stopVegas)&&(count>0))
    {
        count=0;
        for(int i=1; i<=n; i++)
        {
            x[k]=i;
            if(Place(k))
                y[count++]=i;
        }
        if(count>0)                 //如果能放置，则在这么多个能放置第 k 个皇后的位置中选择一个位置
            x[k++]=y[rand()%count];
    }
    return(count>0);                //count>0 表示放置成功
}
bool nQueen(int n)
{
                                    //与回溯法相结合的接 n 后问题的拉斯维加斯算法
    Queen X;
    X.n=n;
    int *p=new int[n+1];
    int *q=new int[n+1];
    for(int i=0; i<=n; i++)
    {
        p[i]=0;
        q[i]=0;
    }
    X.y=p;
    X.x=q;
    int stop=5;
    if(n>15)
        stop=n-15;
    bool found=false;
    while(!X.QueenLV(stop));        //直到能放置
                                    //Backtreck 为算法的回溯搜索部分
    if(X.Backtrack(stop+1))
    {
        for(int i=1; i<=n; i++)
            cout<<p[i]<<"  ";
        found=true;
    }
    cout<<endl;
    delete []p;
    delete []q;
    return found;
}
int main()
{
    int n;
    cout<<"n:";
    cin>>n;
    if(!nQueen(n))
        cout<<"无解"<<endl;
    return 0;
}