《算法三部曲》 之 搜索算法（中篇）——首发于飘云阁
本帖最后由 Knuth学徒 于 2011-2-10 10:45 编辑注：此贴首发于飘云阁
Content 目录：
搜索算法（上篇）：https://www.chinapyg.com/viewthread.php?tid=61759
搜索算法（下篇）：https://www.chinapyg.com/viewthread.php?tid=61831&extra=page%3D1
上一节里我介绍了 深度优先搜索算法，以及它在N皇后问题中发挥的作用，这一节我讲深入讲解，引入迷宫问题的例子，并且引出第二种搜索算法——广度优先搜索。
并说明两种算法在用途上的不同。
这里先回顾一下我 之前讲的深度优先搜索： 首先，在做搜索题的时候，脑子里要建立一棵搜索树，就是说树中的任意一个节点都表示一个状态，然后每个状态它的子状态都可以确定的表示出来，所谓的子状态就是指一步就能够达到的下一个状态的集合。
然后采用 树的先序遍历的 方法递归的遍历整棵树，直到找到表示目标状态的节点。（注意这里的先序遍历并不仅仅是二叉树了，也许每个节点都有N个子节点，但是也没关系，只要一个循环就可以）
这里，我先引入迷宫问题： 给你一个 大小为 N*M 的迷宫地图，并且给你一个起点和终点，让你找到一条从起点通往终点的路径，并且输出这条路径，如果起点和终点不连通，则输出“不连通”
按照搜索题的分析方法，我们先建立一棵搜索树：
根节点： 起点位置
根节点的子节点： 起点位置的上下左右的位置（如果有墙挡住就不算）
任意一个节点：这个节点表示的位置
任意一个节点的子节点： 该节点的上下左右的位置（如果有墙挡住就不算）
目标状态节点：终点的位置
搜索树是搜索问题的骨架，所以建立好之后就可以一直用了，这棵搜索树对于以后的广度优先搜索也有用，请务必仔细体会。
接着的算法就是先序遍历这棵树了，但是我们用什么数据结构来实现它呢？ 众所周知算法是建立在数据结构上的，一个好的算法需要有一个好的数据结构来实现。
我这里采用的数据结构是：
一个判断之前是否已经访问过的标记数组：
boolhash;
以及一个矩阵来存储迷宫的地图：
char map; //如果是墙壁则 map = #,如果是空地则map = ''
最后一个栈，用来保存路径
struct node{
int x,y;
}
于是，我们可以得到：对于起点位置，扩展它的四个方向位置，判断它们是墙还是空地，若是墙壁则不搜索。 如果是空地，则判断该位置以前是否已经访问过，如果访问过则不搜索，反之搜索这个子节点。
实现代码：#include<cstdio>
#include<stack>
#include<cstring>
#include<cstdlib>
using namespace std;
#define M8
#define N8
boolhash;
charmap;
struct Node{
int x,y; //节点的横纵坐标
};
int EndX,EndY;//定义终点坐标为全局变量
stack<Node> s; //保存路径的栈
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;
}
}
boolis_end( int x , int y , int endX, int endY ) //判断是否终点
{
return ( (x == endX) && (y == endY) );
}
void input(){ //输入迷宫地图
for(int i = 0; i < N ; ++i )
for(int j = 0; j < M ; ++j){
scanf("%c", &map);
}
}
boolDepth_First_Search( int x , int y )
//深度优先搜索，如果能够找到路径返回 true,并且把路径保存在栈中。
{
if( is_end ( x , y , EndX, EndY) ) //终点
{
Node tmp;
tmp.x = x;tmp.y = y;
s.push(tmp); //保存该位置作为路径
return true;
}
if(hash) { return false; }
hash = true;
bool flag(false);
for(int k = 0; k < 4 ; ++k )//扩展4个方向
{
int tempX = x + dirction;
int tempY = y + dirction;
if( is_legal ( tempX, tempY) )//该子节点位置合法
{
flag = flag || Depth_First_Search(tempX, tempY);
if(flag){ //如果该子节点能够连到出口
Node temp;
temp.x = x;temp.y = y;
s.push(temp); //将该父节点压栈作为路径保存
return true;
}
}
}
if(!flag){
//如果该位置的四个位置都不连终点，那么该位置也不连终点
return false;
}
}
void output()
{
printf("入口->");
while(!s.empty())
{
Node node = s.top();
s.pop();
printf("( %d , %d ) -> ", node.x , node.y );
}
printf("出口\n");
}
int main()
{
int StartX,StartY;
input();
memset(hash,false,sizeof(hash));
printf("再输入起点坐标\n");
scanf("%d %d", &StartX,&StartY);
printf("再输入终点坐标\n");
scanf("%d %d",&EndX, &EndY);
if(Depth_First_Search(StartX,StartY))
//判断起点能否连通到终点，能连通就输出路径
{
output();
}
else
{
printf("不连通\n");
}
system("pause");
return 0;
}以上的代码注释算是详细了，如果要理解深搜的话，建议仔细体味。
这样，迷宫问题的路径问题就解决了。
深度优先搜索介绍到此为止。
/////////////////////////分割线///////////////////////////
广度优先搜索开始：
介绍广搜，还是引用迷宫问题的例子，只是这下我改变问法：
前提条件还是不变，我这次改问，从起点到终点至少要走多少步，并输出最小步数。
对比深搜，这次问的是最少步数，我们用深搜只求出了一条路径，但是这条路径的步数并不是最小的，那么我们如果不借助广搜的方法，是否要用深搜把所有路径全部求出来，然后取一个步数最小值，显然这个耗时非常的多。
那么就要用到 基于 “层次遍历” 的广度优先搜索。
讲解广搜，还是得用到我们先前建立的 搜索树，不知道有多少朋友还记得，不记得的话可以往上翻，这里就不再鳌述了。
因为广搜是层次遍历，所以根据搜索树的性质，我们可以发现，广搜最先访问的是 起点，然后把起点周围的位置搜索一圈，然后把起点周围第2层再搜索一边，接着再搜索起点周围的第3层。。。。逐层展开。
这样，由于是逐层展开，所以第一次搜索到终点的层数，就是最少的步数！~
如果熟悉二叉树遍历的话，我们知道，层次遍历需要借助一个数据结构 ——“队列”，关于队列的详细介绍，我也在飘云阁写过，见链接：https://www.chinapyg.com/viewthread.php?tid=61755&extra=page%3D1
那么，这里开个头，关于广搜的具体算法，将在 搜索算法（下篇）深入讨论。
//////////////////////////////后记////////////////////////////////////////////////
我在写算法三部曲的第一部曲时，发现帖子变成热门帖子一类了，感谢大家的阅读，我旨在传播算法的重要性，以及一些基本算法，我尽可能的把算法抽象成模型，帮助大家理解。
我相信面试过大公司的朋友，一定会发现，那些IT公司对于应聘者的算法功底的要求非常高，经常会出一些算法的问题，所以我就因此打算写“算法三部曲”，同时也希望大家能够借此提高算法功底。
转载请注明出处。
谢谢
////////////////////////////////////////////////////////////////////////////////////////////////////////// 自己先顶一下。。。 拜读了，代码还没读明白/:017 回复 3# tianfire
/:014其实如果完全理解搜索树的想法和 递归的思想的话，应该可以看到一部分了。
当然如果以前没写过这些，一下子要全看懂也许有点困难。 将 搜索（上）（中）（下）放在一起，免得人家看了上忘了下 学习了。谢谢 学习下..... 过来膜拜一下，算法的力量。 看不懂 楼主牛/:good 我真的没有看明白 很是郁闷
页:
[1]
2