回溯法实验n皇后问题迭代法.doc
《回溯法实验n皇后问题迭代法.doc》由会员分享，可在线阅读，更多相关《回溯法实验n皇后问题迭代法.doc（9页珍藏版）》请在冰点文库上搜索。
算法分析与设计实验报告
第三次附加实验
姓名
学号
班级
时间
12.26上午
地点
工训楼309
实验名称
回溯法实验（n皇后问题）（迭代法）
实验目的
1.掌握回溯法求解问题的思想
2.学会利用其原理求解相关问题
实验原理
用n元组x[1:
n]表示n后问题的解。
其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。
由于不允许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。
2个皇后不能放在同一斜线上是问题的隐形约束。
用回溯法解n后问题时，用完全n叉树表示解空间。
可行性约束Place剪出不满足行、列和斜线约束的子树。
递归函数Backtrack
（1）实现对整个解空间的回溯搜索。
Backtrack（i）搜索解空间中第i层子树。
类Queen的数据成员记录解空间中结点信息，以减少传给Backtrack的参数。
Sum记录当前已找到的可行方案数。
实验步骤
数组法：
（1）根据n皇后问题，可以把其设想为一个数组；
（2）根据n皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都不能相同，由此可以得到判断条件；
（3）根据判断条件之后，建立回溯点，即可解决问题。
堆栈法：
（1）检索当前行是否可以放置一个皇后；
（2）利用检索过程，通过递归的方式，来确定每一个皇后的位置。
关键代码
递归回溯：
voidQueen:
:
Backtrack（intt）
{
if（t>n）
{
sum++;
/*for（inti=1;i<=n;i++）//输出皇后排列的解
{
cout< }
cout< }
else
{//回溯探索第i行的每一列是否有元素满足要求
for（inti=1;i<=n;i++）
{
x[t]=i;
if（Place（t））
{
Backtrack（t+1）;
}
}
}
}
迭代回溯：
voidQueen:
:
Backtrack（）//迭代法实现回溯函数
{
x[1]=0;
intk=1;
while（k>0）
{
x[k]+=1;//先将皇后放在第一列的位置上
while（（x[k]<=n）&&!
（Place（k）））//寻找能够放置皇后的位置
{x[k]+=1;}
if（x[k]<=n）//找到位置
{
if（k==n）//如果寻找结束输出结果
{
/*for（inti=1;i<=n;i++）
{cout<cout<sum++;
}
else//没有结束则找下一行
{
k++;
x[k]=0;
}
}
else//没有找到合适的位置则回溯
{k--;}
}
}
测试结果
较小皇后个数结果：
递归法较大的皇后个数：
迭代法较大的皇后个数：
输入较大的皇后个数15：
输入皇后个数是16时：
当输入的皇后个数是20时：
运行了一个上午都没有出结果，所以果断放弃了。
实验分析
在上述的实验结果中:
（1）我们可以观察到输出皇后排序结果与不输出结果，只输出解的个数是有差距的。
（2）而且通过对比递归与迭代两种不同的实现方法，发现情况是基本相同的，时间上并没有什么太大的差距，但是相对的迭代会稍微快一点点。
（3）然后对比输入较大的皇后个数之后，仅仅一个皇后之差就会使得时间上相差很大，如15个皇后的时候所用的时间是280.102，而当皇后个数是16时，所用的时间是2153.463，从而我们可以看出n皇后问题的时间复杂度是指数级的，从而n皇后问题确实是NP问题。
实验心得
Dijkstra算法在之前的数据结构中就学过，在当时只是学过这种思想，并没有去深思这种思想其背后到底是一种怎样的思想在里面。
后来经过本门课的学习，对于贪心算法有了更深刻的了解，也知道了如何利用贪心算法去解决问题。
最开心的是经过一定时间的练习，我的编程能力有了一定的提高，之前看见就很头疼的问题，现在也能静下心来去思考，而且实现Dijkstra算法也可以通过一定程度的思考也能写出来了，感觉还是很开心的。
Dijkstra算法求单源最短路径在很多地方都有应用，经过一次又一次的练习，终于能好好的掌握这一算法了，还是希望不要那么快忘记啊。
实验得分
助教签名
附录：
完整代码（回溯法）
//回溯算法递归回溯n皇后问题
#include
#include
#include
#include"math.h"
usingnamespacestd;
classQueen
{
friendintnQueen（int）;//定义友元函数，可以访问私有数据
private:
boolPlace（intk）;//判断该位置是否可用的函数
voidBacktrack（intt）;//定义回溯函数
intn;//皇后个数
int*x;//当前解
longsum;//当前已找到的可行方案数
};
intmain（）
{
intm,n;
for（inti=1;i<=1;i++）
{
cout<<"请输入皇后的个数：
";//输入皇后个数
cin>>n;
cout<<"皇后问题的解为：
"< clock_tstart,end,over;//计算程序运行时间的算法
start=clock（）;
end=clock（）;
over=end-start;
start=clock（）;
m=nQueen（n）;//调用求解的函数
cout< cout<"< end=clock（）;
printf（"Thetimeis%6.3f",（double）（end-start-over）/CLK_TCK）;//显示运行时间
cout< }
system（"pause"）;
return0;
}
boolQueen:
:
Place（intk）//传入行号
{
for（intj=1;j {
if（（abs（k-j）==abs（x[j]-x[k]））||（x[j]==x[k]））//如果两个在同一斜线或者在同一列上，说明冲突，该位置不可用
{
returnfalse;
}
}
returntrue;
}
voidQueen:
:
Backtrack（intt）
{
if（t>n）
{
sum++;
/*for（inti=1;i<=n;i++）//输出皇后排列的解
{
cout< }
cout< }
else
{//回溯探索第i行的每一列是否有元素满足要求
for（inti=1;i<=n;i++）
{
x[t]=i;
if（Place（t））
{
Backtrack（t+1）;
}
}
}
}
intnQueen（intn）
{
QueenX;//定义Queen类的对象X
//初始化X
X.n=n;
X.sum=0;
int*p=newint[n+1];//动态分配
for（inti=0;i<=n;i++）//初始化数组
{
p[i]=0;
}
X.x=p;
X.Backtrack
（1）;
delete[]p;
returnX.sum;//输出解的个数
}
完整代码（回溯法）
//回溯算法迭代回溯n皇后问题
#include
#include
#include
#include"math.h"
usingnamespacestd;
classQueen
{
friendintnQueen（int）;//定义友元函数
private:
boolPlace（intk）;//定义位置是否可用的判断函数
voidBacktrack（void）;//定义回溯函数
intn;//皇后个数
int*x;//当前解
longsum;//当前已找到的可行方案数
};
intmain（）
{
intn,m;
for（inti=1;i<=1;i++）
{
cout<<"请输入皇后的个数：
";
cin>>n;
cout<"< clock_tstart,end,over;//计算程序运行时间的算法
start=clock（）;
end=clock（）;
over=end-start;
start=clock（）;
m=nQueen（n）;//调用求解皇后问题的函数
cout< cout<"< end=clock（）;
printf（"Thetimeis%6.3f",（double）（end-start-over）/CLK_TCK）;//显示运行时间
cout< }
system（"pause"）;
return0;
}
boolQueen:
:
Place（intk）
{
for（intj=1;j{
if（（abs（k-j）==abs（x[j]-x[k]））||（x[j]==x[k]））//如果两个皇后在同一斜线或者在同一列上，说明冲突，该位置不可用
{
returnfalse;
}
}
returntrue;
}
voidQueen:
:
Backtrack（）//迭代法实现回溯函数
{
x[1]=0;
intk=1;
while（k>0）
{
x[k]+=1;//先将皇后放在第一列的位置上
while（（x[k]<=n）&&!
（Place（k）））//寻找能够放置皇后的位置
{
x[k]+=1;
}
if（x[k]<=n）//找到位置
{
if（k==n）//如果寻找结束输出结果
{
/*for（inti=1;i<=n;i++）
{
cout<}
cout<sum++;
}
else//没有结束则找下一行
{
k++;
x[k]=0;
}
}
else//没有找到合适的位置则回溯
{k--;}
}
}
intnQueen（intn）
{
QueenX;//定义Queen类的对象X
//初始化X
X.n=n;
X.sum=0;
int*p=newint[n+1];
for（inti=0;i<=n;i++）
{
p[i]=0;
}
X.x=p;
X.Backtrack（）;
delete[]p;
returnX.sum;//返回不同解的个数
}
升级会员 