Chinaunix首页 | 论坛 | 博客

wqfhenanxc

首页　| 　博文目录　| 　关于我

wqfhenanxc

  • 博客访问： 1124231
  • 博文数量： 242
  • 博客积分： 10209
  • 博客等级： 上将
  • 技术积分： 3028
  • 用 户 组： 普通用户
  • 注册时间： 2008-03-12 09:27
文章分类

全部博文（242）

文章存档

2014年（1）

2013年（1）

2010年（51）

2009年（65）

2008年（124）

我的朋友
最近访客
推荐博文
相关博文
回溯 转载

分类： C/C++

2010-10-09 22:46:05

转载自http://fuliang.javaeye.com/blog/164686和http://fuliang.javaeye.com/blog/164744

回溯法之一---算法框架及基础

回溯法其实也是一种搜索算法，它可以方便的搜索解空间。
回溯法解题通常可以从以下三步入手：
1、针对问题，定义解空间
2、确定易于搜索的解空间结构
3、以深度优先的方式搜索解空间，并在搜索的过程中进行剪枝
回溯法通常在解空间树上进行搜索，而解空间树通常有子集树和排列树。
针对这两个问题，算法的框架基本如下：
用回溯法搜索子集合树的一般框架：

Cpp代码
  1. void backtrack(int t){  
  2.   if(t > n) output(x);  
  3.   else{  
  4.     for(int i = f(n,t); i <= g(n,t);i++){  
  5.           x[t] = h(i);  
  6.           if(constraint(t) && bound(t)) backtrack(t+1);  
  7.      }  
  8.   }  
  9. }  


用回溯法搜索排列树的算法框架：

Cpp代码
  1. void backtrack(int t){  
  2.   if(t > n) output(x);  
  3.   else{  
  4.     for(int i = f(n,t); i <= g(n,t);i++){  
  5.           swap(x[t],x[i]);  
  6.           if(constraint(t) && bound(t)) backtrack(t+1);  
  7.           swap(x[t],x[i]);   
  8.     }  
  9.   }  
  10. }  


其中f(n,t),g(n,t)表示当前扩展结点处未搜索过的子树的起始标号和终止标号,
h(i)表示当前扩展节点处，x[t]第i个可选值。constraint(t)和bound(t)是当前
扩展结点处的约束函数和限界函数。constraint(t)返回true时，在当前扩展结点
x[1:t]取值满足约束条件，否则不满足约束条件，可减去相应的子树。bound(t)返
回的值为true时，在当前扩展结点x[1:x]处取值未使目标函数越界，还需要由backtrack(t+1)
对其相应的子树进一步搜索。
用回溯法其实质上是提供了搜索解空间的方法，当我们能够搜遍解空间时，
显然我们就能够找到最优的或者满足条件的解。这便是可行性的问题， 而效率可以
通过剪枝函数来降低。但事实上一旦解空间的结构确定了，很大程度上时间复杂度
也就确定了，所以选择易于搜索的解空间很重要。
下面我们看看两个最简单的回溯问题，他们也代表了两种搜索类型的问题：子集合问题和
排列问题。
第一个问题：
求集合s的所有子集(不包括空集),我们可以按照第一个框架来写代码：

Cpp代码
  1. #include  
  2. using namespace std;  
  3.   
  4. int s[3] = {1,3,6};  
  5. int x[3];  
  6. int  N = 3;  
  7. void print(){  
  8.    for(int j = 0; j < N; j++)  
  9.     if(x[j] == 1)  
  10.        cout << s[j] << " ";  
  11.    cout << endl;  
  12. }  
  13.   
  14. void subset(int i){  
  15.     if(i >= N){  
  16.         print();  
  17.         return;  
  18.     }  
  19.   
  20.     x[i] = 1;//搜索右子树  
  21.     subset(i+1);  
  22.     x[i] = 0;//搜索左子树  
  23.     subset(i+1);  
  24. }  
  25.   
  26. int main(){  
  27.   subset(0);  
  28.   return 0;  
  29. }  



下面我们看第二个问题：排列的问题，求一个集合元素的全排列。
我们可以按照第二个框架写出代码：

Cpp代码
  1. #include  
  2. using namespace std;  
  3.   
  4. int a[4] = {1,2,3,4};  
  5. const int N = 4;  
  6.   
  7. void print(){  
  8.     for(int i = 0; i < N; i++)  
  9.            cout << a[i] << " ";  
  10.     cout << endl;  
  11. }  
  12.   
  13. void swap(int *a,int i,int j){  
  14.   int temp;  
  15.   temp = a[i];  
  16.   a[i] = a[j];  
  17.   a[j] = temp;  
  18. }  
  19.   
  20. void backtrack(int i){  
  21.     if(i >= N){  
  22.         print();  
  23.     }  
  24.     for(int j = i; j < N; j++){  
  25.         swap(a,i,j);  
  26.         backtrack(i+1);  
  27.         swap(a,i,j);  
  28.     }  
  29. }  
  30.   
  31. int main(){  
  32.   backtrack(0);  
  33.   return 0;  
  34. }  


这两个问题很有代表性，事实上有许多问题都是从这两个问题演变而来的。第一个问题，它穷举了所有问题的子集，这是所有第一种类型的基础，第二个问题,它给出了穷举所有排列的方法，这是所有的第二种类型的问题的基础。理解这两个问题,是回溯算法的基础.
下面看看一个较简单的问题：
整数集合s和一个整数sum，求集合s的所有子集su,使得su的元素之和为sum。
这个问题很显然是个子集合问题，我们很容易就可以把第一段代码修改成这个问题的代码：

Cpp代码
  1. int sum = 10;  
  2. int r = 0;  
  3. int s[5] = {1,3,6,4,2};  
  4. int x[5];  
  5. int  N = 5;  
  6.   
  7. void print(){  
  8.    for(int j = 0; j < N; j++)  
  9.     if(x[j] == 1)  
  10.        cout << s[j] << " ";  
  11.    cout << endl;  
  12. }  
  13. void sumSet(int i){  
  14.     if(i >= N){  
  15.         if(sum == r) print();  
  16.         return;  
  17.     }  
  18.     if(r < sum){//搜索右子树  
  19.       r += s[i];  
  20.       x[i] = 1;  
  21.       sumSet(i+1);  
  22.       r -= s[i];   
  23.     }  
  24.     x[i] = 0;//搜索左子树  
  25.     sumSet(i+1);  
  26. }  
  27.   
  28. int main(){  
  29.   sumSet(0);  
  30.   return 0;  
  31. }  

 

回溯法之二---8皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上.
问题分析:
第一步 定义问题的解空间
这个问题解空间就是8个皇后在棋盘中的位置.
第二步 定义解空间的结构
可以使用8*8的数组，但由于任意两个皇后都不能在同行，我们可以用数组下标表示
行，数组的值来表示皇后放的列，故可以简化为一个以维数组x[9]。
第三步 以深度优先的方式搜索解空间，并在搜索过程使用剪枝函数来剪枝
根据条件:x[i] == x[k]判断处于同一列
         abs(k-i) == abs(x[k]-x[i]判断是否处于同一斜线
我们很容易写出剪枝函数：
Cpp代码
  1. bool canPlace(int k){  
  2.     for(int i = 1; i < k; i++){  
  3.         //判断处于同一列或同一斜线  
  4.        if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i]))              return false;  
  5.     }  
  6.     return true;  
  7. }  

然后我们按照回溯框架一，很容易写出8皇后的回溯代码：
Cpp代码
  1. void queen(int i){  
  2.     if(i > 8){  
  3.         print();  
  4.         return;  
  5.     }  
  6.     for(int j = 1; j <= 8; j++){  
  7.       x[i] = j;//记录所放的列  
  8.       if(canPlace(i)) queen(i+1);  
  9.     }  
  10. }  

整个代码：
Cpp代码
  1. #include  
  2. #include  
  3. using namespace std;  
  4.   
  5. int x[9];  
  6. void print(){  
  7.     for(int i = 1; i <= 8; i++)  
  8.            cout << x[i] << " ";  
  9.     cout << endl;  
  10. }  
  11.   
  12. bool canPlace(int k){  
  13.     for(int i = 1; i < k; i++){  
  14.             //判断处于同一列或同一斜线  
  15.        if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i]))   
  16.            return false;  
  17.     }  
  18.     return true;  
  19. }  
  20.   
  21. void queen(int i){  
  22.     if(i > 8){  
  23.         print();  
  24.         return;  
  25.     }  
  26.     for(int j = 1; j <= 8; j++){  
  27.       x[i] = j;  
  28.       if(canPlace(i)) queen(i+1);  
  29.     }  
  30. }  
  31.   
  32. int main(){  
  33.   queen(1);  
  34.   return 0;  
  35. } 

八皇后问题的非递归实现
这里给出的递归实现和上面的差不多，放在这里主要是为了和下面的非递归作对应，因为它们的变量相似。
递归实现：
#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");
    }
}


阅读(2688) | 评论(1) | 转发(0) |
0

上一篇：数据库设计范式深入浅出 转载

下一篇：回来啦

给主人留下些什么吧！~~

chinaunix网友2010-10-13 16:33:52

很好的, 收藏了 推荐一个博客，提供很多免费软件编程电子书下载： http://free-ebooks.appspot.com

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6