《算法三部曲》 之 搜索算法（下篇）——首发于飘云阁
本帖最后由 Knuth学徒 于 2011-3-26 18:10 编辑注：此贴首发于飘云阁
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/viewthread.php?tid=61755&extra=page%3D1
现在，就用队列来实现广搜，步骤如下：
首先把 搜索树的根节点 压入队尾—— queue.push_back( root )
然后取出队头元素 ，此时就是根节点，访问之，然后将根节点的 k 个子节点按顺序压入队尾—— for(k个子节点 A_k){ queue.push_back( A_k );}
然后再从队头取出元素，访问，然后再将它的 N 个子节点压入。。。。。。
于是，解决走迷宫的最少步数 的算法就没问题了，接着我们需要一个良好的数据结构：
用结构体: struct Node{
intx,y;//表示该点的横纵坐标
int step;//表示该节点到根节点的深度——即是该点到起点所需的最短步数
};
用bool型的哈希数组 hash来判重
用char型的地图数组 map存储迷宫 // map = '#' 表示墙壁，map = ' ' 表示空地
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
using namespace std;
#defineN 8
#defineM 8
boolhash;
charmap;
struct Node{
int x,y;
int step;
};
intEndX,EndY,StartX,StartY;
queue<Node> q;//实现广搜的队列
boolis_end(int x,int y) //判断是否到终点
{
return ((x == EndX) && (y == EndY));
}
const int direction = {(0,-1) , (0, 1) , (-1, 0), (1, 0 )}
// 四个方向的数组,分别为"上下左右"
boolis_legal( int x , int y )//判断位置是否越界或者是否是墙壁
{
if( x < 0 || x >= N || y < 0 || y >= M) //越界
{
return false;
}
else if( map == '#' ){ //墙壁
return false;
}
else
{
return true;
}
}
void input(){ //输入迷宫地图
for(int i = 0; i < N ; ++i ){
for(int j = 0; j < M ; ++j){
scanf("%c", &map);
}
}
printf("再输入起点坐标\n");
scanf("%d %d", &StartX,&StartY);
printf("再输入终点坐标\n");
scanf("%d %d",&EndX, &EndY);
}
intBreadth_First_Search( int x, int y)
{
while(!q.empty()) q.pop(); // 初始化清空队列
Node node; //根节点
node.x = x; node.y = y;
node.step = 0; //深度为0
hash = true;
q.push_back(node); //根节点压入队尾
while(!q.empty()) //若队列非空
{
Node tmp;
tmp = q.front();//取出队首元素
q.pop();
if(is_end(tmp.x,tmp.y)) //如果到了终点
{
return tmp.step;
}
for(int k=0;k<4;++k)
//扩展子节点——四个方向
{
int tmpX = tmp.x + direction;
int tmpY = tmp.y + direction;
if(is_legal( tmpX , tmpY ) && !hash)
//如果该点合法并且没有被访问过
{
hash = true;
Node temp;
temp.x = tmpX;
temp.y = tmpY;
temp.step = tmp.step + 1;
q.push_back(temp); //将该点压入队列
}
}
}
return-1; //没有解
}
int main()
{
input();
memset(hash,false,sizeof(hash));
int result;
result = Breadth_First_Search(StartX,StartY);
if(result >= 0)
{
printf("最少需要 %d 步到达终点\n", result);
}
else
{
printf("起点和终点不连通\n");
}
return 0;
}以上代码就是根据广搜的定义和迷宫的具体结构写出来的，如果要理解 "逐层展开"的含义，建议将上面代码中的 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倍！
由此不得不感叹剪枝的重要性。 算法就在于优化，在于如何用最小的时空复杂度来完成最大规模的问题。
我想，分析到这里，这道面试题就可以算是被我们完虐了。
///////////////////////////后记/////////////////////////////////////
最后： 算法三部曲的第一部曲 终于完成了，当然了，第一部曲也是最简单的。
感谢阅读，感谢关注。
转载请注明出处。
//////////////////////////////////////////////////////////////////// 自己顶一个 很强大！！！ 好好学习天天向上
页:
[1]