• 做一个幸福的人,读书,旅行,努力工作,关心身体和心情。
  • 不管有没有人爱,也要努力做一个可爱的人。不埋怨谁,不嘲笑谁,也不羡慕谁,阳光下灿烂,风雨中奔跑,做自己的梦,走自己的路。

深度优先搜索

C/C++ lcq 5年前 (2013-07-27) 450次浏览 0个评论

最近想把大学学过的东西都复习一遍,刚好前面复习了一遍函数的递归。我就不由自主的联想到了深度优先搜索跟递归有很大的联系。所以就从深度优先搜索(DFS)开始吧。

深度优先搜索则像你在走迷宫,你不可能有分身术同时站在每一个点上,只能沿着一条路走到底。如果碰壁了,则退回来再搜索下一个可能的路径。深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。

从深度优先的策略上看就知道深搜一般是用递归来实现;深度优先搜索的框架很简单:

下面有一个简单的flash可以帮助我们理解深度优先搜索的执行过程。

我还是以老鼠走迷宫为例子来说明深度优先搜索的过程吧。

我们来想象一只老鼠,在一座不见天日的迷宫内,老鼠在入口处进去,要从出口出来。那老鼠会怎么走?当然可以是这样的:老鼠如果遇到直路,就一直往前走,如果遇到分叉路口,就任意选择其中的一条继续往下走,如果遇到死胡同,就退回到最近的一个分叉路口,选择另一条道路再走下去,如果遇到了出口,老鼠的旅途就算成功结束了。

深度优先搜索的基本原则就是这样:按照某种条件往前试探搜索,如果前进中遭到失败(正如老鼠遇到死胡同)则退回头另选通路继续搜索,直到找到满足条件的目标为止。

上面定义了一个二维数组,它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。

运用深度优先搜索的思想代码如下:

深度优先搜索使用递归的方法能大大的简化代码,但由于递归需要消耗大量的栈空间,从理论上来讲,所有的递归都可以使用非递归来实现,下面使用栈来模拟深度优先搜索。

代码输出如下:

稍微来解释一下代码的执行过程:从02 ~ 04的过程中只能往下走,首先出栈然后再压栈,所以栈里面的元素只有一个。当走到04的时候,这时候可以往左走跟下走,所以先将05,06依次压栈,这时候栈里面有两个元素。继续执行,将06出栈。此时只能往下走。沿着这条路直到走到09,发现再也无法走下去了,此时无元素入栈,将09出栈,此时栈的元素个数为1,回到05那里。然后05可以往前走,05出栈,10入栈……下面的步骤基本差不多。

这次堆栈里的元素是结构体类型的,用来表示迷宫中一个点的x和y坐标。我们用一个新的数据结构保存走迷宫的路线,每个走过的点都有一个前趋(Predecessor)点,表示是从哪儿走到当前点的,比如predecessor[4][4]是坐标为(3, 4)的点,就表示从(3, 4)走到了(4, 4),一开始predecessor的各元素初始化为无效坐标(-1, -1)。在迷宫中探索路线的同时就把路线保存在predecessor数组中,已经走过的点在maze数组中记为2防止重复走,最后找到终点时就根据predecessor数组保存的路线从终点打印到起点。为了帮助理解,我把这个算法改写成伪代码(Pseudocode)如下:

我在while循环的末尾插了打印语句,每探索一步都打印出当前迷宫的状态(标记了哪些点),从打印结果可以看出这种搜索算法的特点是:每次探索完各个方向相邻的点之后,取其中一个相邻的点走下去,一直走到无路可走了再退回来,取另一个相邻的点再走下去。这称为深度优先搜索(DFS,Depth First Search)。探索迷宫和堆栈变化的过程如下图所示。

图中各点的编号表示探索顺序,堆栈中保存的应该是坐标,我在画图时为了直观就把各点的编号写在堆栈里了。可见正是堆栈后进先出的性质使这个算法具有了深度优先的特点。如果在探索问题的解时走进了死胡同,则需要退回来从另一条路继续探索,这种思想称为回溯(Backtrack),一个典型的例子是很多编程书上都会讲的八皇后问题。

最后我们打印终点的坐标并通过predecessor数据结构找到它的前趋,这样顺藤摸瓜一直打印到起点。那么能不能从起点到终点正向打印路线呢?在上一节我们看到,数组支持随机访问也支持顺序访问,如果在一个循环里打印数组,既可以正向打印也可以反向打印。但predecessor这种数据结构却有很多限制:

1、不能随机访问一条路线上的任意点,只能通过一个点找到另一个点,通过另一个点再找第三个点,因此只能顺序访问。

2、每个点只知道它的前趋是谁,而不知道它的后继(Successor)是谁,所以只能反向顺序访问。

可见,有什么样的数据结构就决定了可以用什么样的算法。那为什么不再建一个successor数组来保存每个点的后继呢?从DFS算法的过程可以看出,虽然每个点的前趋只有一个,后继却不止一个,如果我们为每个点只保存一个后继,则无法保证这个后继指向正确的路线。由此可见,有什么样的算法就决定了可以用什么样的数据结构。设计算法和设计数据结构这两件工作是紧密联系的。

下面是一道可用深度优先搜索解决的题目。题目链接http://poj.org/problem?id=1321

棋盘问题

Time Limit:1000MS Memory Limit:10000K
Total Submissions:18519 Accepted:9180

Description

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n当为-1 -1时表示输入结束。随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

Output

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

Sample Input

Sample Output

这是我很久之前做过的一道简单的深度优先搜索的题目。还是看了代码才把这个题目做出来。刚开始题目意思多有点不明白。总之总结的题目的意思是将k颗棋子放在“#”上面,但是放上去的棋子需要满足的条件是该棋子所在的行跟所在的列都不能再放棋子。

还是先贴代码吧。


乐趣公园 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明深度优先搜索
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址