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

Knuth学徒

注：此贴首发于飘云阁

Content 目录：

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

        上一节里我介绍了 深度优先搜索算法，以及它在N皇后问题中发挥的作用，这一节我讲深入讲解，引入迷宫问题的例子，并且引出第二种搜索算法——广度优先搜索。
         并说明两种算法在用途上的不同。     
         
         这里先回顾一下我 之前讲的深度优先搜索： 首先，在做搜索题的时候，脑子里要建立一棵搜索树，就是说树中的任意一个节点都表示一个状态，然后每个状态它的子状态都可以确定的表示出来，所谓的子状态就是指一步就能够达到的下一个状态的集合。

         然后采用 树的先序遍历的 方法递归的遍历整棵树，直到找到表示目标状态的节点。（注意这里的先序遍历并不仅仅是二叉树了，也许每个节点都有N个子节点，但是也没关系，只要一个循环就可以）

        这里，我先引入迷宫问题： 给你一个 大小为 N*M 的迷宫地图，并且给你一个起点和终点，让你找到一条从起点通往终点的路径，并且输出这条路径，如果起点和终点不连通，则输出“不连通”

        按照搜索题的分析方法，我们先建立一棵搜索树：
     
      

根节点： 起点位置

        根节点的子节点： 起点位置的上下左右的位置（如果有墙挡住就不算）

        任意一个节点：  这个节点表示的位置

        任意一个节点的子节点： 该节点的上下左右的位置（如果有墙挡住就不算）

        目标状态节点：终点的位置

        搜索树是搜索问题的骨架，所以建立好之后就可以一直用了，这棵搜索树对于以后的广度优先搜索也有用，请务必仔细体会。

        接着的算法就是先序遍历这棵树了，但是我们用什么数据结构来实现它呢？    众所周知算法是建立在数据结构上的，一个好的算法需要有一个好的数据结构来实现。

        我这里采用的数据结构是：

        一个判断之前是否已经访问过的标记数组：
        bool  hash[N][M];

        以及一个矩阵来存储迷宫的地图：

        char map[N][M];           //如果是墙壁则 map = #,  如果是空地则map = '  '

        最后一个栈，用来保存路径
        struct node{
              int x,y;
        }
        于是，我们可以得到：对于起点位置，扩展它的四个方向位置，判断它们是墙还是空地，若是墙壁则不搜索。     如果是空地，则判断该位置以前是否已经访问过，如果访问过则不搜索，反之搜索这个子节点。


        实现代码：

1. #include<cstdio>
   
2. #include<stack>
   
3. #include<cstring>
   
4. #include<cstdlib>
   
5. using namespace std;
   
6. 
   
7. #define M  8
   
8. #define N  8
   
9. 
   
10. bool  hash[N][M];
    
11. char  map[N][M];  
    
12. struct Node{
    
13.       int x,y;         //节点的横纵坐标
    
14. };
    
15. 
    
16. int EndX,EndY;  //定义终点坐标为全局变量
    
17. 
    
18. stack<Node> s;   //保存路径的栈
    
19. 
    
20. const int direction[4][2] = {(0,-1) , (0, 1) , (-1, 0), (1, 0 )} // 四个方向的数组,分别为"上下左右"
    
21. 
    
22. bool  is_legal( int x , int y )  //判断位置是否越界或者是否是墙壁
    
23. {
    
24.       if( x < 0 || x >= N || y < 0 || y >= M) //越界
    
25.       {
    
26.              return false;
    
27.       }
    
28.       else if( map[x][y] == '#' ){   //墙壁
    
29.              return false;
    
30.       }
    
31.       else
    
32.       {
    
33.              return true;
    
34.       }
    
35. }
    
36. 
    
37. bool  is_end( int x , int y , int endX, int endY ) //判断是否终点
    
38. {
    
39.        return ( (x == endX) && (y == endY) );
    
40. }
    
41. 
    
42. void input(){      //输入迷宫地图
    
43.        for(int i = 0; i < N ; ++i )
    
44.             for(int j = 0; j < M ; ++j){
    
45.                  scanf("%c", &map[i][j]);
    
46.             }
    
47. }
    
48. 
    
49. bool  Depth_First_Search( int x , int y )  
    
50. //深度优先搜索，如果能够找到路径返回 true,并且把路径保存在栈中。
    
51. {
    
52.        if( is_end ( x , y , EndX, EndY) ) //终点
    
53.        {
    
54.               Node tmp;
    
55.               tmp.x = x;  tmp.y = y;
    
56.               s.push(tmp);    //保存该位置作为路径
    
57.               return true;
    
58.        }
    
59.        if(hash[x][y]) { return false; }
    
60. 
    
61.        hash [x][y] = true;  
    
62.        bool flag(false);
    
63.        for(int k = 0; k < 4 ; ++k )  //扩展4个方向
    
64.        {
    
65.                int tempX = x + dirction[k][0];      
    
66.                int tempY = y + dirction[k][1];
    
67. 
    
68.                if( is_legal ( tempX, tempY) )  //该子节点位置合法
    
69.                {
    
70.                        flag = flag || Depth_First_Search(tempX, tempY);  
    
71.                        
    
72.                        if(flag){     //如果该子节点能够连到出口
    
73.                                Node temp;
    
74.                                temp.x = x;  temp.y = y;
    
75.                                s.push(temp);    //将该父节点压栈作为路径保存
    
76.                                return true;
    
77.                        }
    
78.                }
    
79.         }
    
80.         if(!flag){                  
    
81.         //如果该位置的四个位置都不连终点，那么该位置也不连终点
    
82.                return false;
    
83.         }
    
84. }
    
85. 
    
86. void output()
    
87. {
    
88.         printf("入口->");
    
89.         while(!s.empty())
    
90.         {
    
91.                 Node node = s.top();
    
92.                 s.pop();
    
93.                 printf("( %d , %d ) -> ", node.x , node.y );
    
94.          }
    
95.          printf("出口\n");
    
96. }
    
97. 
    
98. int main()
    
99. {
    
100.         int StartX,StartY;
     
101.         input();
     
102.         memset(hash,false,sizeof(hash));
     
103.         printf("再输入起点坐标\n");
     
104.         scanf("%d %d", &StartX,&StartY);
     
105.         printf("再输入终点坐标\n");
     
106.         scanf("%d %d",&EndX, &EndY);
     
107.         if(Depth_First_Search(StartX,StartY))
     
108.         //判断起点能否连通到终点，能连通就输出路径
     
109.         {
     
110.               output();
     
111.         }
     
112.         else
     
113.         {
     
114.               printf("不连通\n");
     
115.         }
     
116.         system("pause");
     
117.         return 0;
     
118. }

复制代码

以上的代码注释算是详细了，如果要理解深搜的话，建议仔细体味。

      这样，迷宫问题的路径问题就解决了。   
      深度优先搜索介绍到此为止。

/////////////////////////分割线///////////////////////////

      广度优先搜索开始：

            介绍广搜，还是引用迷宫问题的例子，只是这下我改变问法：
            前提条件还是不变，我这次改问，从起点到终点至少要走多少步，并输出最小步数。

            对比深搜，这次问的是最少步数，我们用深搜只求出了一条路径，但是这条路径的步数并不是最小的，那么我们如果不借助广搜的方法，是否要用深搜把所有路径全部求出来，然后取一个步数最小值，显然这个耗时非常的多。

            那么就要用到 基于 “层次遍历” 的广度优先搜索。

            讲解广搜，还是得用到我们先前建立的 搜索树，不知道有多少朋友还记得，不记得的话可以往上翻，这里就不再鳌述了。

            因为广搜是层次遍历，所以根据搜索树的性质，我们可以发现，广搜最先访问的是 起点，然后把起点周围的位置搜索一圈，然后把起点周围第2层再搜索一边，接着再搜索起点周围的第3层。。。。逐层展开。

           这样，由于是逐层展开，所以第一次搜索到终点的层数，就是最少的步数！~

           如果熟悉二叉树遍历的话，我们知道，层次遍历需要借助一个数据结构 ——“队列”，关于队列的详细介绍，我也在飘云阁写过，见链接：https://www.chinapyg.com/viewthr ... &extra=page%3D1

           那么，这里开个头，关于广搜的具体算法，将在 搜索算法（下篇）深入讨论。

//////////////////////////////后记////////////////////////////////////////////////

           我在写算法三部曲的第一部曲时，发现帖子变成热门帖子一类了，感谢大家的阅读，我旨在传播算法的重要性，以及一些基本算法，我尽可能的把算法抽象成模型，帮助大家理解。

           我相信面试过大公司的朋友，一定会发现，那些IT公司对于应聘者的算法功底的要求非常高，经常会出一些算法的问题，所以我就因此打算写“算法三部曲”，同时也希望大家能够借此提高算法功底。

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

Knuth学徒

自己先顶一下。。。

tianfire

拜读了，代码还没读明白/:017

Knuth学徒

回复 3# tianfire


    /:014  其实如果完全理解搜索树的想法和 递归的思想的话，应该可以看到一部分了。

     当然如果以前没写过这些，一下子要全看懂也许有点困难。

Knuth学徒

将 搜索（上）（中）（下）放在一起，免得人家看了上忘了下

jack_yu

学习了。谢谢

pkko005

学习下.....

whypro

过来膜拜一下，算法的力量。

ccggyy

看不懂 楼主牛/:good

liu3062315

我真的没有看明白 很是郁闷