《算法三部曲》之 搜索算法（上篇）

Knuth学徒

Content  目录：
搜索算法（中篇）：https://www.chinapyg.com/viewthread.php?tid=61783
搜索算法（下篇）：https://www.chinapyg.com/viewthr ... &extra=page%3D1

        在介绍搜索之前，我先引入一个例子，看看可以用什么办法解决它。

        N皇后问题：
        在 N*N 的国际棋盘上放入N个皇后，使得这N个皇后互相不攻击，其中皇后的攻击范围是：同行、同列、同对角线。    问:一共有多少种放法？

        这个题目是IT公司面试题的经典题目，虽然现在这题出现的少，但是在以前是一个程序员必定要会的。

        要做这个题目，需要解释一下搜索的本质：对于一些问题，无法直接通过数学的计算算出结果，需要进行逐步试探，在试探的过程中得到解。

        而如果我们亲自去逐步试探可能会因为问题规模过大而无法进行，这时候就可以利用计算机的高效的运算速度来进行搜索。

        搜索一般分为 深度优先搜索——Depth_First_Search，一下简称 DFS， 和 广度优先搜索——Breadth_First_Search,一下简称 BFS,  这两种搜索的方法原理不一样，过程也不一样，但是它们都可以遍历整个解空间，所以我们可以在不同的问题中选取不同的搜索方法。

       回到 N 皇后的问题，这个问题无法用数学公式直接计算出来，但是我们可以通过计算机逐步试探皇后的位置来得到解。

       根据皇后攻击的定义，可以知道—— 在每行、每列、每个对角线上最多只能有 1 个皇后，那么我们“人脑”是这样想的：
      先在第一行的第一列位置先放一个皇后，然后再考虑第二行，第二行的第一个合法位置是第三列，于是把第二个皇后放在第三列。   然后在考虑第三行，第三行的第一个合法位置是第四列。。。。以此试探下去。

      于是，可以把上面的过程抽象成一棵搜索树：树的根节点就是"没放任何皇后",那么树的第一层的子节点就是在第一行的合法位置放入一个皇后，于是 第一层 的第1个子节点代表 “在第一行的第 1个合法位置放入皇后”  ，第二层 的第 3个 子节点代表"在第二行 的 第三个合法位置放入一个皇后"……   归纳一下：第 m 层的 第 n 个子节点代表 “在第m行的第n个合法位置放入一个皇后”。

       现在我们搜索树的模型已经建立好了，那么这里采用 DFS 还是 BFS呢？  取决于这两种搜索算法的区别：

       深度优先搜索：  在一棵搜索树中，采用 先序遍历 的方法遍历整棵树
       广度优先搜索：  在一棵搜索树中，采用 层次遍历 的方法遍历整棵树

      我们仔细体味一下 “人脑” 的思维过程，在放好一个皇后之后，我们考虑的是下一行的皇后再放一个，然后再考虑下下一行……如果对于树的4种遍历方式很熟悉的朋友，应该很快就能想到 这就是 先序遍历，于是自然而然的采用 深度优先搜索即 DFS，在找到一个结果后，用一个计数器累加，直到所有的情况都搜索完了再返回计数器的值。

       实现代码如下：

1. 
   
2. #include<cstdio>
   
3. #include<cstdlib>
   
4. #include<cstring>
   
5. using namespace std;
   
6. #define  N  8               //先定义棋盘的大小，当然可以用键盘输入来定义，这里先用8来做例子
   
7. int  map[N][N] = {0}; // 这个二维数组 用来表示当前的位置是否合法，合法为0,不合法非0
   
8. int  count (0) ;           //   计数器
   
9. 
   
10. void change(int x, int y , bool flag )  //在第x行,第y列放/拿皇后,更新map数组的值
    
11. {
    
12.          if(flag){   //拿掉皇后
    
13.                   for(int i = x ; i < N ;++i)
    
14.                          if(map[i][y] == x + 1) map[i][y] = 0;    //列
    
15.                   for(int j = y - 1 ; j >= 0 && (x-j+y < N) ; --j)
    
16.                          if(map[x-j+y][j] == x+1) map[ x - j + y ][j] = 0;   //左下
    
17.                   for(int k= y+1 ;  k < N   && (x+k-y < N); ++k)
    
18.                          if( map[x + k - y ][k] == x+1) map[x+k-y][k] = 0;//右下
    
19.         }
    
20.         else      //放皇后
    
21.         {
    
22.                  for(int i = x ; i < N ;++i)
    
23.                          if(map[i][y] == 0) map[i][y] = x+1;    //列
    
24.                  for(int j = y - 1 ; j >= 0 && (x-j+y < N) ; --j)
    
25.                          if(map[x-j+y][j] == 0) map[ x - j + y ][j] = x+1;//左下
    
26.                  for(int k= y+1 ;  k < N   && (x+k-y < N); ++k)
    
27.                          if( map[x + k - y ][k] == 0) map[x+k-y][k] = x+1;//右下
    
28.           }
    
29. }
    
30. 
    
31. void   Depth_First_Search(int line)       //深度优先搜索函数，递归实现
    
32. {
    
33.          if( line == N + 1 ) { count ++; return;}  //如果已经放入了N个皇后,计数器+1,继续搜索
    
34.               
    
35.          for(int i = 0; i< N ; ++i )        //对每列进行试探
    
36.          {
    
37.                  if( map[line - 1][i] == 0)    //如果当前列合法
    
38.                 {
    
39.                        change ( line - 1 , i  , false ) ;        // 在这个位置放皇后
    
40.                        Depth_First_Search ( line + 1);   //递归试探下一行
    
41.                        change ( line - 1 , i  , true ) ;       //在这个位置拿掉皇后
    
42.                 }
    
43.          }
    
44. }
    
45. 
    
46. int main()
    
47. {
    
48.          count = 0;          //计数器归零
    
49.          Depth_First_Search(1);  //从第一行开始搜索
    
50.          printf("%d\n", count);
    
51.          system("pause");
    
52.          return 0;
    
53. }
    

复制代码

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
       我用了深度优先搜索的方法解决了N皇后问题的方案数，但是我没有进行优化剪枝。

       在搜索算法（中） 我会讨论 另一个经典的搜索问题——迷宫问题，这个问题有两种问法，比如输出从入口走到终点的路径，或者是求从入口走到终点的需要的最短步数。
      这两个问题要用不同的搜索方法，前者用 DFS ，后者用 BFS，然后还有 深搜和广搜结合的方法，可以 输出 最短路线，这点在 （上）就不深入探讨了。

      第一部曲——搜索算法的三分之一 就到此为止了.
      转载请注明出处作者，谢谢
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Knuth学徒

自己先顶一个。。。
这个帖子花了我很多精力

Knuth学徒

虽然N皇后现在面试题不多了，但是下一节要讲的 迷宫问题 是经常被问道的，我会尽力写好。

Ever.G

支持，C还在初学阶段，预留一下

Ever.G

/:L学到C++的路还长着呢。。

Knuth学徒

回复 5# Ever.G

一起学习，一起努力！

Knuth学徒

回复 7# wlm2421331

C语言固然强大，配上 优秀的算法，将会使程序变得高效，健壮

consult1026913

这个要好好学习一下

Knuth学徒

回复 9# consult1026913


    谢谢关注哈，中篇已经写完了。