ChenGen

一切归零,重新开始
随笔 - 13, 文章 - 10, 评论 - 21, 引用 - 0

导航

<2008年10月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(5)

随笔分类

随笔档案

文章分类

文章档案

收藏夹

Good BLogs

搜索

  •  

最新评论

阅读排行榜

评论排行榜

复习回溯算法——N皇后问题

   今天复习了回溯算法。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==0break;
            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

   从上面的数据可以看出,两种方法所用的时间相差并不大,但是递归算法所耗用的内存空间要比非递归算法大得多。因为我还不知道如何检测应用程序所用的内存空间的大小,所以无法给出准确的证明。

 

 

 

posted on 2006-09-27 22:11 ChenGen 阅读(6801) 评论(6)  编辑  收藏 所属分类: 数据结构复习

评论

# re: 复习回溯算法——N皇后问题  回复  更多评论   

在吗?加个友情链接啊,以后复习算法就来找你!
2006-09-27 22:31 | 坏男孩

# re: 复习回溯算法——N皇后问题  回复  更多评论   

@坏男孩
有什么算法方面的问题的话,可以发邮件给我,很乐意为大家解决算法的问题~
2006-09-27 22:43 | ChenGen

# re: 复习回溯算法——N皇后问题  回复  更多评论   

。。。你的递归算法不用回溯?
2008-09-24 11:01 | sw

# re: 复习回溯算法——N皇后问题[未登录]  回复  更多评论   

@sw
这是非递归算法
2008-10-05 17:35 | chengen

# re: 复习回溯算法——N皇后问题  回复  更多评论   

你的递归实现有问题吧?
2009-09-01 11:17 | 啊啊啊

# re: 复习回溯算法——N皇后问题[未登录]  回复  更多评论   

用数据结构实现五皇后问题,你有代码吗
2012-06-20 23:54 | su

只有注册用户登录后才能发表评论。


网站导航: