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\" using namespace std;class Queen
{
friend int nQueen( int ); private :
// 定义友元函数，可以访问私有数据
bool Place( int k); // 判断该位置是否可用的函数 void Backtrack( int t); // 定义回溯函数 int n; // 皇后个数 int *x; // 当前解
long sum; // 当前已找到的可行方案数 };
int main() int m,n;
for (int i=1;i<=1;i++)
{
{
cout<< \" 请输入皇后的个数： \"; // 输入皇后个数 cin>>n;
cout<< \" 皇后问题的解为： \" <clock_t start,end,over; // 计算程序运行时间的算法 start=clock(); end=clock(); over=end-start; start=clock();m=nQueen(n); // 调用求解的函数 cout<end=clock();printf( \"The time is %6.3f\" ,( double )(end-start-over)/CLK_TCK); // 显
示运行时间
cout<}system( \"pause\" ); return 0;
}
bool Queen::Place( int k) // 传入行号
{
for (int j=1;j{if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
线或者在同一列上，说明冲突，该位置不可用{
return false ;
}
}
return true ;
}
void Queen::Backtrack( int t)
{
if (t>n)
sum++;
{
// 如果两个在同一斜
/*for(int i=1;i<=n;i++) //
{
输出皇后排列的解
cout<}cout<}else
{// 回溯探索第 i 行的每一列是否有元素满足要求
for (int i=1;i<=n;i++)
{
x[t]=i; if (Place(t))
{
Backtrack(t+1);
}
}
}
}
int nQueen( int n)
Queen X; // 定义 Queen类的对象 X
{
// 初始化 X X.n=n; X.sum=0;
int *p= new int [n+1]; // 动态分配 for (int i=0;i<=n;i++) // 初始化数组
{
p[i]=0;
}
X.x=p; X.Backtrack(1); delete [] p;
return X.sum; // 输出解的个数
}
完整代码(回溯法)
// 回溯算法 迭代回溯 n 皇后问题
#include #include #include #include \"math.h\" using namespace std;class Queen
friend int nQueen( int ); // 定义友元函数 private :
{
bool Place( int k); // 定义位置是否可用的判断函数 void Backtrack( void ); int n; int *x;
// 定义回溯函数
// 皇后个数 // 当前解
long sum; // 当前已找到的可行方案数
};
int main()
{
int n,m;
for (int i=1;i<=1;i++)
{
cout<< \" 请输入皇后的个数： \";
cin>>n; cout<clock_t start,end,over; start=clock(); end=clock(); over=end-start;// 计算程序运行时间的算法
start=clock();
m=nQueen(n); // 调用求解皇后问题的函数 cout<end=clock();printf( \"The time is %6.3f\" ,( double )(end-start-over)/CLK_TCK);
// 显示运行时间
cout<}system( \"pause\" ); return 0;
}
bool Queen::Place( int k)
{
for ( int j=1;jif ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) // 如果两个皇后在同一斜线或者在同一列上，说明冲突，该位置不可用
return false
} }
{
return true ;
}
void Queen::Backtrack() // 迭代法实现回溯函数
{
x[1] = 0; int k = 1; while (k>0) {
x[k] += 1; // 先将皇后放在第一列的位置上
while ((x[k]<=n)&&!(Place(k))) // 寻找能够放置皇后的位置 {
x[k] += 1; }
if (x[k]<=n) // 找到位置 {
if (k == n) // 如果寻找结束输出结果
/*for (int i=1;i<=n;i++)
{ cout<cout<{}
else // 没有结束则找下一行 { k++; x[k]=0; } }
else // 没有找到合适的位置则回溯 { k--; } }
}
int nQueen( int n)
{
Queen X; // 初始化 X
// 定义 Queen类的对象 X
X.n=n; X.sum=0;
int *p= new int [n+1];
for (int i=0;i<=n;i++)
{
p[i]=0;
}
X.x=p; X.Backtrack();
delete []p;
return X.sum; // 返回不同解的个数
}
