???今天复习了回溯算法。N皇后问题是一个典型的需要用回溯算法来解决的问题。回溯算法可以用递归方法来实现，也可以用非递归方法来实现。用递归的方法来解决回溯的问题思路很清晰，但是耗费的内存资源较多，速度也较慢；非递归方法具有速度快和耗费较少内存资源的优点，但是程序的逻辑结构却很复杂——不过搞懂之后觉得也很简单。
???在写非递归算法之前，参考了网上的一些文章，但是觉得那些程序都很晦涩难懂，而且存在一些问题，我索性自己写了一个，花了我不少时间。
???递归实现：
#include?"stdio.h"
#include?"stdlib.h"
#include?"time.h"
/**//*?记录当前的放置方案?*/
int?*x;?
/**//*?皇后的个数N?和?方案数目?*/
int?n,sum=0;
/**//*?检查参数所指示的这一行皇后放置方案是否满足要求?*/
int??Place(int);
/**//*?递归方法求取皇后放置方案*/
void?Queen1(void);
/**//*?用户递归求取皇后放置方案的递归方法?*/
void?TraceBack(int);
/**//*?打印当前成功的放置方案?*/
void?PrintMethod(void);
void?main(void)
{
????long?start,stop;
????printf("input?n:?");
????scanf("%d",&n);
????x=(int?*)malloc(sizeof(int)*n);
????time(&start);/**//*记录开始时间*/
????Queen1();
????time(&stop);/**//*记录结束时间*/
????printf("\nmethod?total?%d?\n",sum);
????printf("\nuse?%d?seconds?\n",(int)(stop-start));
}
int?Place(int?r)
{
????int?i;
????for(i=0;i<r;i++){
????????if(x[r]==x[i]?||?abs(r-i)==abs(x[r]-x[i]))
????????????return?0;
????}
????return?1;
}
void?TraceBack(int?r)
{
????int?i;
????if(r>=n){
????????sum++;
????????/**//*?PrintMethod();?*/
????}else{
????????for(i=0;i<n;i++){
????????????x[r]=i;
????????????if(Place(r))?TraceBack(r+1);
????????}
????}
}
void?PrintMethod(void)
{
????int?i,j;
????printf("\nmethod?%d\n",sum);
????for(i=0;i<n;i++){
????????for(j=0;j<n;j++){
????????????if(j==x[i])?printf("*");
????????????else?printf("#");
????????}
????????printf("\n");
????}
}
void?Queen1(void)
{
????TraceBack(0);
}
???非递归实现：
#include?"stdio.h"
#include?"stdlib.h"
#include?"time.h"
/**//*?记录当前的放置方案?*/
int?*x;?
/**//*?皇后的个数N?和?方案数目?*/
int?n,sum=0;
/**//*?检查参数所指示的这一行皇后放置方案是否满足要求?*/
int??Place(int);
/**//*?非递归的方法求取皇后放置方案?*/
void?Queen2(void);
/**//*?打印当前成功的放置方案?*/
void?PrintMethod(void);
void?main(void)
{
????long?start,stop;
????printf("input?n:?");
????scanf("%d",&n);
????x=(int?*)malloc(sizeof(int)*n);
????time(&start);/**//*记录开始时间*/
????Queen2();
????time(&stop);/**//*记录结束时间*/
????printf("\nmethod?total?%d?\n",sum);
????printf("\nuse?%d?seconds?\n",(int)(stop-start));
}
int?Place(int?r)
{
????int?i;
????for(i=0;i<r;i++){
????????if(x[r]==x[i]?||?abs(r-i)==abs(x[r]-x[i]))
????????????return?0;
????}
????return?1;
}
void?Queen2(void)
{
????int?i,k;
????for(i=0;i<n;i++)
????????x[i]=0;
????k=0;
????while(1){
????????if(x[k]>=n){
????????????/**//*?如果当前第K行的放置位置超出了范围，那么检查该行是否为第0行
???????????????如果是第0行，说明所有的方案都已经遍历完毕，函数返回；否则回退到前一行
????????????*/
????????????if(k==0)?break;
????????????x[k]=0;?/**//*?下次遍历的初始位置?*/
????????????k--;?/**//*?返回上一行?*/
????????????x[k]++;?/**//*下一种放置方案*/
????????}
????????else?if(!Place(k)){
????????????/**//*?如果当前第K行的放置方案不满足要求，采取下一种放置方案*/
????????????x[k]++;
????????}
????????else{
????????????if(k==(n-1)){
????????????????/**//*?如果已经是最后一行，那么表示已经成功得到一种放置方案*/
????????????????sum++;
????????????????/**//*?PrintMethod();?*/
????????????????x[k]=0;?/**//*下次遍历的初始位置*/
????????????????k--;?/**//*返回上一行*/
????????????????x[k]++;?/**//*下一种放置方案*/
????????????}else
????????????????k++;?/**//*?否则开始配置下一行的皇后?*/
????????}
????}
}
void?PrintMethod(void)
{
????int?i,j;
????printf("\nmethod?%d\n",sum);
????for(i=0;i<n;i++){
????????for(j=0;j<n;j++){
????????????if(j==x[i])?printf("*");
????????????else?printf("#");
????????}
????????printf("\n");
????}
}
???两种方法的性能比较：
N | 递归算法所用时间（秒） | 非递归算法所用时间（秒） |
13 | 6 | 6 |
14 | 37 | 35 |
15 | 267 | 254 |
???从上面的数据可以看出，两种方法所用的时间相差并不大，但是递归算法所耗用的内存空间要比非递归算法大得多。因为我还不知道如何检测应用程序所用的内存空间的大小，所以无法给出准确的证明。
?
?
?
|