LasVegas算法 n皇後問題

/*
 * Abstract：
 *         EX7. 寫一LasVegas算法求n皇後問題，求n=12~20時，最優的StepVegas的值。
 *         
		
 * Author : Ace.Ma
 * Date   : 2012/9/18
 * Version: 0.1 
 */
#include<iostream>
#include<iomanip>
#include<ctime>
#include<set>
#include<cmath>
#include"Queen.h"

using namespace std;


void test()
{
	for( int n=12; n<=20; ++n)
	{
		cout<<"皇後個數 n="<<n<<endl;
		cout<<setw(10)<<"stopVegas"<<setw(10)<<"p"<<setw(10)<<"s"<<setw(10)<<"e"<<setw(10)<<"t"<<endl;
		for( int stopVegas=0; stopVegas<=n; ++stopVegas)
		{
			long failCount = 0;
			long sucessVistedNodes = 0;
			long failVistedNodes = 0;
			int vistedNodes =0;
			for (int j=0; j<10; ++j) //對于特定的n和stepVegas，求10次的平均性能
			{
				while(1)
				{
					if(nQueen(n,stopVegas,vistedNodes))
					{
						sucessVistedNodes += vistedNodes;
						break; //一次成功，跳出循環
					}else{
						failVistedNodes += vistedNodes;
						++failCount;
					}
				}
			}
			double p = 10.0/(10.0+failCount);
			cout<<setw(10)<<stopVegas<<setw(10)<<p<<setw(10)<<(sucessVistedNodes/10)<<setw(10)<< (failVistedNodes/10) <<setw(10)<< (sucessVistedNodes*p+(1-p)*failVistedNodes)/10 <<"  "<<failCount/10<<endl;
		}
		for(int i=0; i<50; ++i) 
			cout<<"*";
		cout<<endl;
	}
}

int main()
{
	srand((unsigned int)time(0));
	
	test();

	system("pause");
	return 0;
} 
/* 
參考資料：http://www.cnblogs.com/tanky_woo/archive/2010/12/13/1904146.html
備注：産看結果：注意書上說解決8皇後問題時，列出了一個不同stopVegas值時，所對應的算法成功率，
在stopVegas=8時，他寫着是0.1293，我個人認為是錯的。接下來我說下自己這麼了解的原因：
首先，這個程式為何會造成有失敗的情況，那就是因為在随機求出前stopVegas行成立時，
不代表後面N-stopVegas行用回溯就可以成立，因為這不是一個徹底的回溯。
它是從stopVegas+1行開始計算，回溯不成立最後傳回時，也隻停留在stopVegas。
而我們在完全随機時，那麼它就是反複調用随機位置放置n個皇後的Las Vegas算法，直至放置成功。
是以當stopVegas=8時，他的成功率也應該是100%。
另外在stopVegas=3時，成功率等于0.49，趨近于0.5，大家可以試試，基本上每運作兩次會有一次回來結果。
如果上面我的了解有錯，歡迎大家指出，我的部落格(www.WuTianQi.com)。

個人見解：
這個我感覺應該也把 随機放置stopVegas産生的失敗也算上，這對節點數的平均值有影響的。
*/
           

Queen.h
           

#ifndef QUEEN_H
#define QUEEN_H


class Queen
{
	friend bool nQueen(int, int);
	friend bool nQueen(int n, int stopVegas,int &VistedNodes);


	int getVistedNodes()
	{
		return vistedNodes;
	}
private:
	bool Place(int k);  //測試皇後k置于第x[k]列的合法性
	bool Backtrack(int t); //解n後問題的回溯法
	bool QueensLV(int stopVegas); //随機放置n個皇後Las Vegas算法
	int n;          //皇後個數
	int vistedNodes; //一次搜尋成功或失敗通路的節點數。
	int *x;         //解向量
	int *y;
};


bool Queen::Place(int k)
{//測試皇後k置于第x[k]列的合法性
	for( int j=1; j<k; ++j)
	{
		if ((abs(k-j) == abs(x[j]-x[k])) || (x[j]==x[k]))
			return false;
	}
	++vistedNodes; //随機放一個皇後，算是通路了一個節點吧
	return true;
}


bool Queen::Backtrack(int t)
{//解n後問題的回溯法，開始放第t個皇後，用回溯法。根據前面已經放置的皇後，可能有解或無解，但不會出現有解沒有求出的情況.
	if(t > n)
	{
		for(int i=1; i<=n; ++i) //這裡再把x數組元素拷貝到y數組，後面輸出用了y呵呵，其實感覺也沒必要，直接用x輸出挺好
		{
			y[i] = x[i];
		}
		return true; 
	}else{
		for(int i=1; i<=n; ++i)
		{
			x[t] = i;
			if( Place(t) && Backtrack(t+1) )
			{
				//++vistedNodes; //回溯法放一個皇後，也算通路了一個節點吧
				return true;
			}
		}
	}
	return false;
}
bool Queen::QueensLV(int stopVegas)
{//随機放置n個皇後的Las Vegas算法
	int k = 1; //随機數産生器
	int count = 1;
	//1<=stopVegas<<n 表示允許随機放置的皇後數
	while( (k <= stopVegas) && (count > 0) )
	{
		count = 0;
		for( int i = 1; i <= n; ++i)
		{
			x[k] = i;
			if( Place(k))
			{
				y[count++] = i; //y的0下标用到了，這和後面的rand()%count 保持一緻；
			}
		}
		if( count > 0 )
		{
			x[k++] = y[rand()%count]; //選擇一個可以的随機位置，放到k列上
			//++vistedNodes; //随機放一個皇後，算是通路了一個節點吧
		}
	}
	return (count>0);  //count>0 表示放置成功
}


/*
	n		 皇後大小
	stopVegas随機放置的個數
	VistedNodes 本次搜尋，算法通路的節點數
*/
bool nQueen(int n, int stopVegas,int &vistedNodes)
{//與回溯法相結合的解n後問題的LasVegas算法
	Queen X;
	X.n = n;
	X.vistedNodes = 0;
	int *p = new int[n+1]; //
	int *q = new int[n+1]; //0下标的空間不用
	for( int i=0; i <= n; ++i)
	{
		p[i] = 0;
		q[i] = 0;
	}
	X.y = p;  //y 的0下标好像是用的
	X.x = q;  
	bool found = false;
	
	while(!X.QueensLV(stopVegas));


	//算法的回溯搜尋部分
	if(X.Backtrack(stopVegas+1))
	{
		found = true;
		/*for (int i=1; i<=8; ++i) //輸出結果
		{
			std::cout<<X.x[i]<<",";
		}*/
	}		
	delete[] p;
	delete[] q;
	vistedNodes = X.vistedNodes;
	return found;
}
#endif