n后问题2.0(拉斯维加斯随机算法)

蔚落 2022-08-18 02:19 116阅读 0赞

前言:

昨天总结了个传统穷举的回溯法,考虑到由于递归回溯法时间复杂度高,超过12的皇后计算代价太大.如果基数过大,回溯法的优势就不明显了.

所以关于该算法的改进还有另一种拉斯维加斯(Las Vegas)算法,结合了随机函数,提高了效率.

一.源程序:

#include<iostream>
    #include<cmath>
    #include<cstdlib>
    #include<stdio.h>
    using namespace std;
    class Queen
    {
    	friend void nQueen(int i);
    private:
    	bool Place(int k);
    	bool QueensLV(void);
    	int n;
    	int *x,*y;
    };
    
    bool Queen::Place(int k)
    {
    	for(int j=1;j<k;j++)
    		if(  ( abs(k-j)==abs(x[j]-x[k]) ) ||(x[j]==x[k])  )
    			return false;
    	return true;	//注意这里不是else执行返回true,当每一行都测试过没有冲突之后才返回true
    }
    bool Queen::QueensLV(void)	//定义私有成员函数,实现逐行随机摆放
    {
    	int k = 1,count = 1;
    	while((k<=n)&&(count>0))
    	{
    		count=0;
    		for (int i = 1; i <=n; i++)
    			{//从第一列到第n列 对第k行的皇后逐个试探,若合法则记录与y数组,并且累加解决方案count
    				x[k] = i;
    				if(Place(k))
    				{y[count]=i; count++;	}
    			}
    		if(count>0)			
    		{
    			int z = rand()%count; //产生从0 ~ (count-1)的随机数,即在解决方案数组y中随机找一个作为该行放置位置
    				x[k]=y[z]; k++; //在记录的方案中随机放置,并且k++进入下一行
    		}			 
    	}
    	return (count>0); //若执行到该行,则表示while循环结束,表明所有行皆走过,此时若解决方案存在,则有解.		
    }
    
    void nQueen(int n) //求解
    {
    	Queen X;
    	X.n=n;
    	int *p = new int[n+1];
    	for(int i=0;i<=n;i++)
    		p[i]=0;
    	X.x=p;
    	X.y = new int [n+1];		//注意要给x和y数组初始化
    	while (!X.QueensLV());		//注意QueensLV函数一旦发现无法再放置下一个皇后,需要重新开始不断重复调用QueensLv,                                                                         //直到找到解决方案<pre name="code" class="cpp">					//不足之处若该n后无解,仍然继续死循环.
    	for (int i = 1; i <=n; i++)
    	{cout<<p[i]<<" ";}
    	cout<<endl;
    	delete[]p;
    }
    
    int main()
    {
    	int N;//皇后个数,解决方案;
    	int t=4;
    	while(t--)
    	{
    		cout<<"请输入皇后个数:"<<endl;
    		cin>>N;
    		nQueen(N);
    	}
    }

二.结果示例:

![20151205213536751][]

三.小结

由于该随机算法只是找出解决方案的一个即返回,若方案有多个,则随机选取.所以执行同样个数的n后问题可能有不同的解.

然而该算法还是有缺陷,比如每次放置皇后到一定行数,如果发现没有再可以放置的话就从又要重新再来.

明天接着折腾另一个改进的版本 随机算法结合回溯法的n后问题.

参考资料:《计算机算法设计与分析》 p222

Ps:注意书上例子有个问题 ,数组y忘记初始化,以致于运行代码迟迟发现问题却无从下手,小坑呵.

[20151205213536751]: /images/20220731/c0f7ac1465554185b5038471b2d404d5.png