queen(局部搜索).cpp

局部搜索法求解N皇后问题。这个算法的特点是引入随机因素

#include<iostream>
#include<time.h>
using namespace std;
#define MaxSize 2100
int x[MaxSize];
int conf=0;
int n=0;
int conflicts()
{
	int res=0;
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(abs(x[i]-x[j])==abs(j-i))
				++res;
		}
	return res;
}
int delta_conflict(int i,int j)
{
	int res=0;
	for(int t=1;t<=n;t++)
	{
		if(abs(x[i]-x[t])==abs(t-i))
			res--;
		if(abs(x[t]-x[j])==abs(j-t))
			res--;
	}
	swap(x[i],x[j]);
	for(int t=1;t<=n;t++)
	{
		if(abs(x[i]-x[t])==abs(t-i))
			res++;
		if(abs(x[t]-x[j])==abs(j-t))
			res++;
		if(res>0) break;
	}
	return res;

}
bool succeed()
{
	return conf==0;
}

void display()
{
	for(int i=1;i<=n;i++)
		cout<<x[i]<<" ";
	cout<<endl;
}
int get_i()
{
	int max=0,res=0,t;
	for(int i=1;i<n;i++)
	{
		res=0;
		for(int j=i+1;j<n+1;j++)
			if(abs(x[i]-x[j])==abs(j-i))
				res++;
		if(res>max)
		{	
			max=res;t=i;
		}
		if(max>n-i)
			break;
	}
	return t;

}
void exchange(int j)//随机交换其中两行,直到指标conflicts下降,j为步长
{
	while(conf!=0)
	{
		int i;
		//if(conf==1)
		//	i=get_i();//主动寻找冲突数较多的行
		//else
			i=rand()%n+1;
		j=(i+j-1)%(n-i+1)+i;
		int d=delta_conflict(i,j);
		
		if(d<0)
		{conf+=d;//cout<<d<<endl;
		break;}
		else 
		{cout<<".";
		swap(x[i],x[j]);
		}
	}
}

void exchange()//随机交换其中两行,直到指标conflicts下降
{
	int i,j,d;
	while(conf!=0)
	{
		 i=rand()%n;
		/*int j=rand()%n+1;*/
		/*{
			
			while(i==j)
			{
				j=rand()%n+1;
			}
		}*/
		j=rand()%(n-i)+i+1;
		
		d=delta_conflict(i,j);
		/*if(d>10)
		cout<<"d="<<d<<endl;*/
		if(d<0)
		{conf+=d;//cout<<d<<endl;
		break;}
		else 
		{/*cout<<".";*/
		swap(x[i],x[j]);
		}
	}
}
bool localmin()//是否陷入局部最小
{
	
	if(conf==0) return true;
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(delta_conflict(i,j)<0)
			{	
				swap(x[i],x[j]);
				return false;
			}
			else 
				swap(x[i],x[j]);
		}
	/*cout<<"冲突数："<<min<<" 局部极小\n";*/
	return true;
}

bool localmin(int j)
{
	if(conf==0) return true;
	int t;
	for(int i=1;i<=n;i++)
		/*for(int j=i+1;j<=n;j++)*/
		{
			t=(i+j)%(n-1)+1;
			//t=(i+j-1)%(n-1)+1;
			if(delta_conflict(i,t)<0)
			{	
				swap(x[i],x[t]);
				return false;
			}
			else 
				swap(x[i],x[t]);
		}
	cout<<"冲突数："<<conf<<" 局部极小\n";
	return true;
}

void initial()
{
	
	for(int i=1;i<=n;i++)
		x[i]=i;
	
	//算法分析：时间复杂度为O(n)。这个是目前最优的随机洗牌算法，在算法上达到了最好的随机性（算法上是绝对随机的），而且是原地洗牌，时间复杂度也非常好。
	for(int t=1;t<=n;t++)
	{
		swap(x[t],x[rand()%(n-t+1)+t]);
	}
	conf=conflicts();
	/*display(n);*/
}
bool decrease()
{
	int d;
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			d=delta_conflict(i,j);
			if(d<0)
			{
				conf+=d;
				return true;
			}
			else swap(x[i],x[j]);
		}
	return false;

}


int main()
{
	int i=0;
	double average=0.0,Time;
	double begin,end;
	srand((unsigned int)time(NULL));
	while(cin>>n&&n!=0)
	{
		
		
		begin=clock();
		initial();
		cout<<"conflicts:"<<conf<<endl;
		while(!succeed())
		{
			
		
			if(n<500)
			{
				while(localmin())
				{
					i++;
					initial();
				}
			}
			exchange();
			//cout<<conf<<endl;
			
		}
		end=clock();
		i++;
		Time=(end-begin)/double(CLK_TCK);
		average+=Time;
		/*cout<<"局部极小次数："<<i<<endl;*/
		cout<<"皇后数："<<n<<" 个，用时："<<Time<<" 秒\n";
		if(i==5)
		{ 
			cout<<"次数："<<i<<" 平均时间："<<average/i<<" 秒\n";
			i=0;
			average=0;
		}
		/*display();*/
		
		
	}
}