nqueenlvb.cpp

这个是八皇后问题的回溯加las vegas算法

/*
*  文件名称：nqueenlvb.cpp
*  算法说明：随机算法和回溯算法相结合
*  完成日期：2006年11月4日
*/
#include <iostream>
#include <time.h>
#define N  8
#define TOTAL  10000
using namespace std;
int x[N+1];//数组x用来存放第1行到N行的皇后所在的列
int flag;//用以判断回溯是否成功
double s,f,temp;//s：解决一个皇后问题成功时所访问的结点总数
				//f: 解决一个皇后问题失败时所访问的结点总数
				//temp:调用一次nqueenlvb函数时访问的结点数

int random(int x) //产生1~x之间的一个随机数
{
		return(1+rand()%x);
}

int place(int row)//判断执行到第row行时，x[row]即对应于row的皇后所在的列是否合法
{
	for (int i=1;i<row;i++)
		if ( (x[row]==x[i]) || ( abs(row-i)==abs(x[row]-x[i]) ) )//当皇后所在的列……
			return 0;
	return 1;
}

void backtrack(int t)   //从第t行开始用回溯法解决皇后问题
{
	int i;

	if (t>N) //回溯成功，标记 flag 并退出
	{
		flag=1;  
		return;
	}
	else
		for (i=1;i<=N&&!flag;i++)
		{
			x[t]=i;
			if (place(t))
			{++temp;backtrack(t+1);}
		}
	return;
}

int nqueenlvb(int x[],int stoplv)
{
	int row,col;
	int count,ok[N+1];//count对应每行所能放皇后的列的个数，ok[count]用来存放每行能相对应的列
	
	temp=1;//调用一次nqueenlvb退出时访问的结点数；搜索树的根表示棋盘空状态，是访问的第一个结点
	flag=0;//每次调用，flag都从0开始；
	
	for (row=1;row<=stoplv;row++)
	{
		count=0;//对应每一行都要重新赋值
		for(col=1;col<=N;col++)
		{
			x[row]=col;
			if (place(row))
			{
				count++;//从1开始计数，为了取随机数的统一
				ok[count]=col;
			}
		}
		
		if (count==0) {f=f+temp;return 0;}//失败时，将访问的结点记入f
		else {++temp;x[row]=ok[random(count)];}		
	}
	backtrack(stoplv+1);
	if (flag) {s=s+temp;return 1;}
	else {f=f+temp;return 0;}
}

void main()
{
	int stoplv;//随机放置的皇后个数
	double num,p;
	int i=0;

	srand((unsigned)time(NULL));
	cout<<"stoplv	"<<"p	"<<"s	"<<"	f	"<<"	t	"<<endl;
	
	for (stoplv=0;stoplv<=N;stoplv++)
	{
		num=0;s=0;f=0;
		for (i=0;i<TOTAL;i++)
			if (nqueenlvb(x,stoplv))  
				num++;
		if (stoplv==0||stoplv==1)//成功的概率为1
			f=0;
		else 
			f=f/(TOTAL-num);//失败时平均访问的结点数

		p=num/TOTAL;//成功的概率
		s=s/num;    //成功时平均访问的结点数
		cout<<stoplv
			<<"	"<<p
			<<"	"<<s			
			<<"		"<<f
			<<"		"<<(s+f*(1-p)/p)<<endl;	
	}
}