Chinaunix首页 | 论坛 | 博客
  • 博客访问: 868095
  • 博文数量: 82
  • 博客积分: 2283
  • 博客等级: 大尉
  • 技术积分: 2007
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-15 22:19
文章分类

全部博文(82)

文章存档

2012年(82)

分类: C/C++

2012-08-12 17:33:29

  回溯法解题思路
(1)针对所给问题,定义问题的解空间;   
(2)确定易于搜索的解空间结构;   
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

回溯就是让计算机自动的去搜索,碰到符合的情况就结束或者保存起来,在一条路径上走到尽头也不能找出解,就回到原来的岔路口,选择一条以前没有走过的路继 续探测,直到找到解或者走完所有路径为止。就这一点,回溯和所谓的DFS(深度优先搜索)是一样的。那现在的关键是,怎么实现搜索呢?回溯既然一般使用递 归来实现,那个这个递归调用该如何来写呢?我现在的理解就是,进行回溯搜索都会有一系列的步骤,每一步都会进行一些查找。而每一步的情况除了输入会不一样 之外,其他的情况都是一致的。这就刚好满足了递归调用的需求。通过把递归结束的条件设置到搜索的最后一步,就可以借用递归的特性来回溯了。因 为合法的递归调用总是要回到它的上一层调用的,那么在回溯搜索中,回到上一层调用就是回到了前一个步骤。当在当前步骤找不到一种符合条件情况时,那么后续 情况也就不用考虑了,所以就让递归调用返回上一层(也就是回到前一个步骤)找一个以前没有尝试过的情况继续进行。当然有时候为了能够正常的进行继续搜索, 需要恢复以前的调用环境。

点击(此处)折叠或打开

  1. /*
  2.      * 回溯法解N皇后问题
  3.      * 使用一个一维数组表示皇后的位置
  4.      * 其中数组的下标表示皇后所在的行
  5.      * 数组元素的值表示皇后所在的列
  6.      * 这样设计的棋盘,所有皇后必定不在同一行
  7.      *
  8.      * 假设前n-1行的皇后已经按照规则排列好
  9.      * 那么可以使用回溯法逐个试出第n行皇后的合法位置
  10.      * 所有皇后的初始位置都是第0列
  11.      * 那么逐个尝试就是从0试到N-1
  12.      * 如果达到N,仍未找到合法位置
  13.      * 那么就置当前行的皇后的位置为初始位置0
  14.      * 然后回退一行,且该行的皇后的位置加1,继续尝试
  15.      * 如果目前处于第0行,还要再回退,说明此问题已再无解
  16.      *
  17.      * 如果当前行的皇后的位置还是在0到N-1的合法范围内
  18.      * 那么首先要判断该行的皇后是否与前几行的皇后互相冲突
  19.      * 如果冲突,该行的皇后的位置加1,继续尝试
  20.      * 如果不冲突,判断下一行的皇后
  21.      * 如果已经是最后一行,说明已经找到一个解,输出这个解
  22.      * 然后最后一行的皇后的位置加1,继续尝试下一个解
  23.      */
  24.     #define MAX_LENGTH 1024
  25.     /*
  26.      * 检查第n行的皇后与前n-1行的皇后是否有冲突
  27.      * 发生冲突的充分必要条件是:
  28.      * a) 两皇后处于同一列,即a[i] == a[n]
  29.      * b) 两皇后处于同一斜线,即|a[i] - a[n]| == |i - n| == n - i
  30.      */
  31.     int is_conflict(int *a, int n) {
  32.         int flag = 0;
  33.         int i;
  34.         for ( i = 0; i < n; i++ ) {
  35.             if ( a[i] == a[n] || a[i] - a[n] == n - i || a[n] - a[i] == n - i ) {
  36.                 flag = 1;
  37.                 break;
  38.             }
  39.         }
  40.         return flag;
  41.     }
  42.     /*
  43.      * 输出皇后的排列
  44.      */
  45.     void print_board(int *a, int n) {
  46.         int i, j;
  47.         for ( i = 0; i < n; i++ ) {
  48.             for ( j = 0; j < a[i]; j++ ) {
  49.                 printf(" ");
  50.             }
  51.             printf("Q");
  52.             for ( j = a[i] + 1; j < n; j++ ) {
  53.                 printf(" ");
  54.             }
  55.             printf("/n");
  56.         }
  57.         printf("--------/n");
  58.     }
  59.     /*
  60.      * 初始化棋盘,所有皇后都在第0列
  61.      */
  62.     void init_board(int *a, int n) {
  63.         int i;
  64.         for ( i = 0; i < n; i++ ) {
  65.             a[i] = 0;
  66.         }
  67.     }
  68.     /*
  69.      * 解决N皇后问题
  70.      */
  71.     int queen(int n) {
  72.         int count = 0;
  73.         int a[MAX_LENGTH];
  74.         init_board(a, n);
  75.         int i = 0;
  76.         while ( 1 ) {
  77.             if ( a[i] < n ) {
  78.                 // 如果皇后的位置尚未超出棋盘范围
  79.                 // 需要检查第i行的皇后是否与前i-1行的皇后冲突
  80.                 if ( is_conflict(a, i) ) {
  81.                     // 如果冲突,尝试下一个位置
  82.                     a[i]++;
  83.                     continue;
  84.                 }
  85.                 if ( i >= n - 1 ) {
  86.                     // 如果已经到最后一行,也即找到一个解,首先输出它
  87.                     count++;
  88.                     print_board(a, n);
  89.                     // 然后尝试当前行的皇后的下一个位置
  90.                     a[n-1]++;
  91.                     continue;
  92.                 }
  93.                 // 没有冲突,尝试下一行
  94.                 i++;
  95.                 continue;
  96.             }
  97.             else {
  98.                 // 皇后的位置已经超出棋盘范围
  99.                 // 那么该行的皇后复位
  100.                 a[i] = 0;
  101.                 // 回退到上一行
  102.                 i--;
  103.                 if ( i < 0 ) {
  104.                     // 已经不能再退了,函数结束
  105.                     return count;
  106.                 }
  107.                 // 尝试上一行的皇后的下个位置
  108.                 a[i]++;
  109.                 continue;
  110.             }
  111.         }
  112.     }
  113.     int main(void) {
  114.         int n = 8;
  115.         int count = queen(n);
  116.         printf("%d solutions in %d queens problem\n", count, n);
  117.         return 0;
  118.     }




阅读(11767) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~