???今天復(fù)習(xí)了回溯算法。N皇后問題是一個(gè)典型的需要用回溯算法來解決的問題。回溯算法可以用遞歸方法來實(shí)現(xiàn)，也可以用非遞歸方法來實(shí)現(xiàn)。用遞歸的方法來解決回溯的問題思路很清晰，但是耗費(fèi)的內(nèi)存資源較多，速度也較慢；非遞歸方法具有速度快和耗費(fèi)較少內(nèi)存資源的優(yōu)點(diǎn)，但是程序的邏輯結(jié)構(gòu)卻很復(fù)雜——不過搞懂之后覺得也很簡單。
???在寫非遞歸算法之前，參考了網(wǎng)上的一些文章，但是覺得那些程序都很晦澀難懂，而且存在一些問題，我索性自己寫了一個(gè)，花了我不少時(shí)間。
???遞歸實(shí)現(xiàn)：
#include?"stdio.h"
#include?"stdlib.h"
#include?"time.h"
/**//*?記錄當(dāng)前的放置方案?*/
int?*x;?
/**//*?皇后的個(gè)數(shù)N?和?方案數(shù)目?*/
int?n,sum=0;
/**//*?檢查參數(shù)所指示的這一行皇后放置方案是否滿足要求?*/
int??Place(int);
/**//*?遞歸方法求取皇后放置方案*/
void?Queen1(void);
/**//*?用戶遞歸求取皇后放置方案的遞歸方法?*/
void?TraceBack(int);
/**//*?打印當(dāng)前成功的放置方案?*/
void?PrintMethod(void);
void?main(void)
{
????long?start,stop;
????printf("input?n:?");
????scanf("%d",&n);
????x=(int?*)malloc(sizeof(int)*n);
????time(&start);/**//*記錄開始時(shí)間*/
????Queen1();
????time(&stop);/**//*記錄結(jié)束時(shí)間*/
????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);
}
???非遞歸實(shí)現(xiàn)：
#include?"stdio.h"
#include?"stdlib.h"
#include?"time.h"
/**//*?記錄當(dāng)前的放置方案?*/
int?*x;?
/**//*?皇后的個(gè)數(shù)N?和?方案數(shù)目?*/
int?n,sum=0;
/**//*?檢查參數(shù)所指示的這一行皇后放置方案是否滿足要求?*/
int??Place(int);
/**//*?非遞歸的方法求取皇后放置方案?*/
void?Queen2(void);
/**//*?打印當(dāng)前成功的放置方案?*/
void?PrintMethod(void);
void?main(void)
{
????long?start,stop;
????printf("input?n:?");
????scanf("%d",&n);
????x=(int?*)malloc(sizeof(int)*n);
????time(&start);/**//*記錄開始時(shí)間*/
????Queen2();
????time(&stop);/**//*記錄結(jié)束時(shí)間*/
????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){
????????????/**//*?如果當(dāng)前第K行的放置位置超出了范圍，那么檢查該行是否為第0行
???????????????如果是第0行，說明所有的方案都已經(jīng)遍歷完畢，函數(shù)返回；否則回退到前一行
????????????*/
????????????if(k==0)?break;
????????????x[k]=0;?/**//*?下次遍歷的初始位置?*/
????????????k--;?/**//*?返回上一行?*/
????????????x[k]++;?/**//*下一種放置方案*/
????????}
????????else?if(!Place(k)){
????????????/**//*?如果當(dāng)前第K行的放置方案不滿足要求，采取下一種放置方案*/
????????????x[k]++;
????????}
????????else{
????????????if(k==(n-1)){
????????????????/**//*?如果已經(jīng)是最后一行，那么表示已經(jīng)成功得到一種放置方案*/
????????????????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 | 遞歸算法所用時(shí)間（秒） | 非遞歸算法所用時(shí)間（秒） |
13 | 6 | 6 |
14 | 37 | 35 |
15 | 267 | 254 |
???從上面的數(shù)據(jù)可以看出，兩種方法所用的時(shí)間相差并不大，但是遞歸算法所耗用的內(nèi)存空間要比非遞歸算法大得多。因?yàn)槲疫€不知道如何檢測(cè)應(yīng)用程序所用的內(nèi)存空間的大小，所以無法給出準(zhǔn)確的證明。
?
?
?