《算法三部曲》 之 搜索算法（下篇）——首发于飘云阁

Knuth学徒

注：此贴首发于飘云阁

Content 目录：
搜索算法 （上篇）：https://www.chinapyg.com/viewthread.php?tid=61759
搜索算法 （中篇）：https://www.chinapyg.com/viewthread.php?tid=61783

      今天终于要完成第一部曲了，有点感慨，有点激动，看到了(上中)两篇在热门帖子里均排在前2名，我很欣慰。    也许很多朋友们以前不注重基本的算法，也许他们本来认为程序只是某种语言的架构，但是我希望我的 算法三部曲成为热门帖之后会有更多人看到它，认识到原来算法那么具有逻辑性，具有指导性，那么我的努力就没有白费。

      搜索算法本来作为一个很基础的算法，但是其中蕴含的思想却是可以细细体味的。 今天，我就深入讨论下 广度优先搜索 以及它的应用。

      中篇里我已经稍微介绍了广搜的概念——围绕根节点逐层展开，我也抽象了一棵搜索树来解决迷宫问题。  但是具体的实现方式我还没有讲，那么，我现在来介绍下广搜是如何实现的，以及他和深搜最本质的区别。

      广度优先搜索： 在搜索树中以层次遍历 方式遍历整棵树

      如果知道层次遍历的话，那么就不需要细讲了，如果不知道的话，我可以简要的介绍下：，所谓层次遍历就是指：

            先访问第一层的根节点，然后再从左至右逐个访问 第二层的子节点，然后再从左往右逐个访问 第三层的子节点，……逐层深入，直到找到目标节点或者遍历完整棵树。

      那么，我们如何按照层次展开呢？     可以发现在访问的过程中，我们假设先访问 第n层的第1个节点，记为A节点，那么我们必然也是最先访问 第n+1层的A节点的子节点，同样的，如果我们在A节点后访问到 第n层的第3个节点，记为B节点，那么我们必然也是在第n+1层 在访问了A的子节点之后 访问了B的子节点。

     于是，一个很明显的 “先进先出” 关系便出现了。

     一说到“先进先出”，最先想到的就应该是“队列”——先压入队尾的元素将会先从队首弹出。

     你们还记得 队列的实现方式么？     如果学过数据结构的同学也许还有印象，如果没学过，也没关系，我关于队列写了详细的 C++类模板，具体参照：https://www.chinapyg.com/viewthr ... &extra=page%3D1

      现在，就用队列来实现广搜，步骤如下：

            首先把 搜索树的根节点 压入队尾—— queue.push_back( root )
            然后取出队头元素 ，此时就是根节点，访问之，然后将根节点的 k 个子节点按顺序压入队尾—— for(k个子节点 A_k){ queue.push_back( A_k );}
            然后再从队头取出元素，访问，然后再将它的 N 个子节点压入。。。。。。

      于是，解决走迷宫的最少步数 的算法就没问题了，接着我们需要一个良好的数据结构：

      用结构体: struct Node{
                             int  x,y;  //表示该点的横纵坐标
                             int step;  //表示该节点到根节点的深度——即是该点到起点所需的最短步数
                    };

      用bool型的哈希数组 hash[N][M]来判重
      用char型的地图数组 map[N][M]存储迷宫     // map = '#' 表示墙壁，map = ' ' 表示空地

1. 
   
2. #include<cstdio>
   
3. #include<queue>
   
4. #include<cstring>
   
5. #include<cstdlib>
   
6. using namespace std;
   
7. 
   
8. #define  N 8
   
9. #define  M 8
   
10. 
    
11. bool  hash[N][M];
    
12. char  map[N][M];
    
13. 
    
14. struct Node{
    
15.         int x,y;
    
16.         int step;
    
17. };
    
18. int  EndX,EndY,StartX,StartY;
    
19. 
    
20. queue<Node> q;  //实现广搜的队列
    
21. 
    
22. bool  is_end(int x,int y)   //判断是否到终点
    
23. {
    
24.         return ((x == EndX) && (y == EndY));
    
25. }
    
26. 
    
27. const int direction[4][2] = {(0,-1) , (0, 1) , (-1, 0), (1, 0 )}
    
28. // 四个方向的数组,分别为"上下左右"
    
29. 
    
30. bool  is_legal( int x , int y )  //判断位置是否越界或者是否是墙壁
    
31. {
    
32.       if( x < 0 || x >= N || y < 0 || y >= M) //越界
    
33.       {
    
34.              return false;
    
35.       }
    
36.       else if( map[x][y] == '#' ){   //墙壁
    
37.              return false;
    
38.       }
    
39.       else
    
40.       {
    
41.              return true;
    
42.       }
    
43. }
    
44. 
    
45. void input(){      //输入迷宫地图
    
46.        for(int i = 0; i < N ; ++i ){
    
47.             for(int j = 0; j < M ; ++j){
    
48.                  scanf("%c", &map[i][j]);
    
49.             }
    
50.        }
    
51.        printf("再输入起点坐标\n");
    
52.        scanf("%d %d", &StartX,&StartY);
    
53.        printf("再输入终点坐标\n");
    
54.        scanf("%d %d",&EndX, &EndY);
    
55. }
    
56. 
    
57. int  Breadth_First_Search( int x, int y)
    
58. {
    
59.        while(!q.empty()) q.pop();   // 初始化清空队列
    
60.        Node node;                          //根节点
    
61.        node.x = x; node.y = y;
    
62.        node.step = 0;                     //深度为0
    
63.        hash[x][y] = true;
    
64.        q.push_back(node);          //根节点压入队尾
    
65.        while(!q.empty())         //若队列非空
    
66.        {
    
67.                Node tmp;
    
68.                tmp = q.front();  //取出队首元素
    
69.                q.pop();
    
70.                if(is_end(tmp.x,tmp.y)) //如果到了终点
    
71.                {
    
72.                         return tmp.step;
    
73.                }
    
74.                for(int k=0;k<4;++k)
    
75.               //扩展子节点——四个方向
    
76.                {
    
77.                         int tmpX = tmp.x + direction[k][0];
    
78.                         int tmpY = tmp.y + direction[k][1];
    
79. 
    
80.                         if(is_legal( tmpX , tmpY ) && !hash[tmpX][tmpY])
    
81.                         //如果该点合法并且没有被访问过
    
82.                         {
    
83.                                  hash[tmpX][tmpY] = true;
    
84.                                  Node temp;
    
85.                                  temp.x = tmpX;
    
86.                                  temp.y = tmpY;
    
87.                                  temp.step = tmp.step + 1;
    
88.                                  q.push_back(temp);   //将该点压入队列
    
89.                          }
    
90.                 }
    
91.         }
    
92.         return  -1;      //没有解
    
93. }
    
94. 
    
95. int main()
    
96. {
    
97.          input();
    
98.          memset(hash,false,sizeof(hash));
    
99.          int result;
    
100.          result = Breadth_First_Search(StartX,StartY);
     
101.          if(result >= 0)
     
102.          {
     
103.                   printf("最少需要 %d 步到达终点\n", result);
     
104.          }
     
105.          else
     
106.          {
     
107.                   printf("起点和终点不连通\n");
     
108.          }
     
109.          return 0;
     
110. }

复制代码

以上代码就是根据广搜的定义和迷宫的具体结构写出来的，如果要理解 "逐层展开"的含义，建议将上面代码中的 Breadth_First_Search() 函数弄懂。

       到这里，本来是应该结束了，不过我突然想起来，记得 Nisy  老师曾经在群里 提过一个面试题，当时好像群里没什么人给出解答，这道题就是经典的广搜。

       那我把 当时的题目的大意重新叙述下，如果记忆有差错还是请 Nisy老师来指正：

      

        给你一个中国象棋的棋盘，给你一个起点，再给你一个终点，问你：如果在棋盘上的起点放一个"马”，按照跳马步的方式至少要几步才能跳到终点。

       大致意思就是这样，其实这道面试题说难不难，说简单也不简单，如果以前没有看过我写的这篇搜索算法，也许就会被难倒。  但是，自从我们接触了广度优先搜索以后，发现这题和迷宫问题 有异曲同工之妙，我们只需将大致框架稍微做些修改就可以了。

       首先是搜索树的修改:
       根节点: 起点
       根节点的子节点：从起点按照马步的跳法能够跳到的位置

       任意节点：该节点表示的位置
       任意节点的子节点：从该节点按照马步的跳法能够跳到的位置集合

       然后再按照广搜的实现方式就能解决了。

       不过这里有个问题，假设终点位置在当前位置的右上角，那么我们此时还需不需要往左下角搜索呢？

       由于我们要求的最小步数，如果往反方向跳的话，必然会增加步数，所以我们这里可以针对具体情况对这个算法进行优化——就是所谓的“搜索剪枝”

       剪枝方法：
       终点坐标（EndX, EndY） ,当前位置坐标( CurX, CurY )
       在扩展的8个子节点中，至少有6个可以被删去。

       那么如何判断哪6个方向可以被去掉呢？   就是所谓的“反方向跳”或者更准确的说是“偏离正方向的位置”

       根据 数学中的解析几何的知识：（PS：这里体会到高中的数学知识不是白学的了吧？   其实算法的本质就是数学，要想做一个好的程序师，数学功底是必须的。）
                    
               方向向量n的终点 如果在 矩形( (EndX,EndY) , (CurX,EndY) , (CurX, CurY) , (EndX, CurY) ) 之外，就是偏离了正确方向，需要剪去。

               判断一个点是否在矩形内的方法是： 该点的横坐标的范围在 矩形的两竖直边内  且  该点的纵坐标的范围在矩形的两水平边内。

       接下来就可以提高相当高的效率了，不知道多少朋友想到了这个剪枝呢？

       但是别高兴太早， 也许面试官可能更加的挑剔，需要你再剪枝，继续提高效率，那么这时候我们想想还有哪里会浪费效率的呢？

       我们假设 起点和终点 的位置距离很远，这时候如果就算进行了“偏离方向”的剪枝，也许还会有非常多的无用节点产生，那么我想到了一个办法是：

                先固定让马从起点 按照终点的方向 日字形 跳跃若干步，直到 离开终点位置不远了。
                那么什么叫“不远了”，我们这里可以自己设置一个阀值，比如离开在终点位置的半径为2的圆内。
                这时候只要当前位置 在这个范围圆外，我们就可以按照一个位置进行跳动，直到了这个圆内，再按照普通的广搜来搜索。

       可以惊奇的发现，在圆外时，扩展的效率竟然是不加任何剪枝的广搜的 8倍， 是 加了“偏离方向”剪枝的广搜的 2倍！

       由此不得不感叹剪枝的重要性。    算法就在于优化，在于如何用最小的时空复杂度来完成最大规模的问题。

       我想，分析到这里，这道面试题就可以算是被我们完虐了。

///////////////////////////后记/////////////////////////////////////
       最后： 算法三部曲的第一部曲 终于完成了，当然了，第一部曲也是最简单的。

       感谢阅读，感谢关注。

       转载请注明出处。
////////////////////////////////////////////////////////////////////

Knuth学徒

自己顶一个

fgc5789

很强大！！！

jmgsdz

好好学习天天向上