共有回帖数 0 个
-
最近看到又有不少人在讨论八皇后问题，乃至N皇后问题，我就把去年的作业贴出来给大家探讨下吧。
本文主要内容：用回溯和局部搜索方法，实现求解N皇后问题的程序，并且比较耗费时间
先给出两种方法的耗费时间比较：
方法棋盘大小 15 20 27 29 30 100 200 500 1000
回溯法耗时(ms) 0 47 125 409 15719
局部搜索法耗时(ms) 0 0 0 0 15 100 1000 12000 40000
以下是两种方法的程序：
回溯法程序：
#includeiostream.h
#includestring.h
#includetime.h
#define size 100
int board[size];
int ver[size];
int ru[size*2];//右上
int rd[size*2];//右下
int n,find; int rec[size];
//回溯搜索
void dfs(int t)
{
int i;
if(find) return;
if(t==n)
{
find=1;
for(i=0;in;i++)
{
rec=board;
}
return;
}
for(i=0;in;i++)
{
if(ver==1) continue;
if(ru[i-t+n]==1) continue;
if(rd[i+t]==1) continue;
ver=1;
ru[i-t+n]=1;
rd[i+t]=1;
board[t]=i;
dfs(t+1);
rd[i+t]=0;
ru[i-t+n]=0;
ver=0;
}
return;
}
int main()
{
int i,j,t1,t2;
cout"输入棋盘大小：";
cinn;
t1=clock();
find=0; memset(ver,0,sizeof(ver));
memset(ru,0,sizeof(ru)); memset(rd,0,sizeof(rd));
dfs(0);
t2=clock();
if(find)
for(i=0;in;i++)
{
for(j=0;jn;j++)
{
if(rec==j) cout'X';
else cout'+';
}
coutendl;
}
else
cout"Can't find!n";
cout"耗费时间："t2-t1"msn";
return 0;
}
局部搜索程序：
#includeiostream.h
#includestring.h
#includestdlib.h
#includetime.h
#define size 2000
int board[size];//记录棋盘状况的数组
//记录冲突的数组
int ru[size*2];//右上
int rd[size*2];//右下
int recran[size];
int n; int rec[size];
int f()
{//计算冲突的函数
int i,r=0;
memset(ru,0,sizeof(ru));
memset(rd,0,sizeof(rd));
for(i=0;in;i++)
{
ru[board-i+n]++;
rd[board+i]++;
}
for(i=0;i2*n;i++)
{
if(ru1) r+=ru-1;
if(rd1) r+=rd-1;
}
return r;
}
//生成x个不重复的随机数，放入board数组
void randgen(int x)
{
int i,temp;
memset(recran,0,sizeof(int)*(n+1));
for(i=0;in;i++)
{
do
{
temp=rand()%x;
}
while(recran[temp]==1);
board=temp;
recran[temp]=1;
}
}
int main()
{
srand((unsigned) time(NULL));
int i,j,temp,now,t1,t2,fnow;
cout"输入棋盘大小：";
cinn;
coutendl;
t1=clock();
//find=0;
//局部搜索部分
while(1)
{
randgen(n);
now=f();
next: if(now==0) goto over;
for(i=0;in-1;i++)
{
for(j=i+1;jn;j++)
{
temp=board; board=board[j]; board[j]=temp;
fnow=f();
if(fnownow)
{
now=fnow;
goto next;
}
temp=board; board=board[j]; board[j]=temp;
}
}
}
over:
t2=clock();
/*for(i=0;in;i++)
{
for(j=0;jn;j++)
{
if(board==j) cout'X';
else cout'+';
}
coutendl;
}*/
cout"耗费时间："t2-t1"msn";
return 0;
}
经检验，在有解并且时间允许的情况下，两程序均可以找到一组正确解。
棋盘大小在30以上，回溯法在有限时间内基本无法找到解，而棋盘大小直到1000，局部搜索法仍能找到正确��
楼主 2016-02-19 16:44 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
