因此深度优先搜索的空间复杂度是d的线性函数
O(bd) 。
2018/12/18 人工智能 丁世飞 12

DFS时间复杂性
如果搜索在d层最左边的位置找到了目标，则检
查的节点数为(d+1)。另一方面，，如果只是搜索 到d层，而在d层的最右边找到了目标，则检查的 节点包括了树中所有节点，其数量为： 1+b+b2+┅+bd=(bd+1-1)/(b-1)
当搜索过程到达了最大深度的时候，所需
要的内存最大。
2018/12/18
人工智能 丁世飞
11
DFS空间复杂性

假设每个节点的分支系数为b，当我们考虑深度为d
的一个节点时，保存在内存中的节点的数量包括到
达深度d时所有未扩展的节点以及正在被考虑的节 点。因此，在每个层次上都有(b-1)个未扩展的节点， 总的内存需要量为d(b-1)+1。
2018/12/18 人工智能 丁世飞 16

2018/12/18
人工智能 丁世飞
4
基于栈实现的DFS算法
Procedure Depth First Search Begin (1)把初始节点压入栈，并设置栈顶指针； (2)While 栈不空 do Begin 弹出栈顶元素； If 栈顶元素=goal，成功返回并结束； Else 以任意次序把栈顶元素的子女压入栈中； End While End
2018/12/18 人工智能 丁世飞 7

遍历一棵树的过程（下图）。
2018/12/18
人工智能 丁世飞
8
DFS例题分析
例3.3 卒子穿阵问题: 要求一卒子从顶部通过图3.10所 示的列阵到达底部。要求卒子行进中不可进入到代表敌兵 驻守的区域内（标注1），并不准后退。假定限制值为5
行 1 2 3 1 2 3 4 列


深度优先——扩展当前节点后生成的子节 点总是置于OPEN表的前端，即OPEN表 作为栈，后进先出，使搜索优先向纵深方 向发展。
人工智能 丁世飞 2
2018/12/18
DFS的基本思想

深度优先搜索生成节点并与目标节点进行比较 是沿着树的最大深度方向进行的，只有当上次 访问的节点不是目标节点，而且没有其他节点 可以生成的时候，才转到上次访问节点的父节 点。
第3章 搜索策略
3.1 引言 3.2 基于状态空间图的搜索技术(1)(2)
√3.3 盲目搜索(2)
--DFS搜索
2018/12/18 人工智能 丁世飞 1
3.3.2 深度优先搜索

深度优先搜索(Depth First Search, DFS)，是 一种一直向下的搜索策略。 OPEN表中节点简单的排序方式：

深度优先搜索的存储器要求是深度约束的 线性函数O(bd)。

2018/12/18 人工智能 丁世飞 14

DFS的缺点
既不是完备的，也不是最优的。
主要问题是可能搜索到了错误的路径上。很多问
题可能具有很深甚至是无限的搜索树，如果不幸选 择了一个错误的路径，则深度优先搜索会一直搜索 下去，而不会回到正确的路径上。这样一来对于这 些问题，深度优先搜索要么陷入无限的循环而不能 给出一个答案，要么最后找到一个答案，但路径很 长而且不是最优的答案。
1 0 0
0 0 1
0 1 0
0 0 0
4
1
0
0
0
图3.10 阵列图
2018/12/18 人工智能 丁世飞 9
S0
S1(1,1)
S2(1,2)
S8(1,3)
S18(1,4)
死
S3(2,2) S9(1,2) S14(1,4)
S4(2,1)
S5(3,1) S6(3,2)
S7(2,3)
S10(2,2)
S13(2,3)
所以,平均来说,检查的节点数量为
(bd+1-1)/2(b-1)+(1+d)/2≈b(bd+d)/2(b-1)
因此深度优先搜索的平均时间复杂度O(bd)。
2018/12/18 人工智能 丁世飞 13

DFS的优点
深度优先搜索的优点是比宽度优先搜索算 法需要较少的空间。该算法只需要保存搜 索树的一部分，它由当前正在搜索的路径 和该路径上还没有完全展开的节点标志所 组成。

转移到父节点后，该算法会搜索父节点的其他 的子节点。
2018/12/18
人工智能 丁世飞
3
DFS的基本思想

深度优先搜索也称为回溯搜索，它总是首先扩展 树的最深层次上的某个节点，只是当搜索遇到一 个死亡节点（非目标节点而且不可扩展），搜索 方法才会返回并扩展浅层次的节点。 上述原理对树中的每一节点是递归实现的，实现 该递归过程的比较简单的一种方法是采用栈。
2018/12/18 人工智能 丁世飞 5
算法说明

初始节点放到栈中，栈指针指向栈的最上 边的元素。

为了对该节点进行检测，需要从栈中弹出 该节点，如果是目标，该算法结束，否则 把其子节点以任何顺序压入栈中。
该过程直到栈变成为空。

2018/12/18
人工智能 丁世飞
6
基于栈实现的DFS流程
(1)把初始节点S0放入OPEN表； (2)如果OPEN表为空，则问题无解，失败并退出。 (3)把OPEN表中的第一个节点取出放入CLOSE表中， 并按顺序冠以编号n； (4)考察节点n是否为目标节点。若是，则求得了问题的 解，成功并退出。 (5)若节点n不可扩展，则转第(2)步； (6)扩展节点n，将其予节点放到OPEN表的首部，并为 其配置指向父节点的指针，然后转第(2)步4,4)
死
S11(2,1) S12(3,1)
死 死 深度限制 解
图3.11 卒子穿阵的深度优先搜索树
2018/12/18
人工智能 丁世飞
10

DFS空间复杂性
深度优先搜索对内存的需求是比较适中的。
它只需要保存从根到叶的单条路径，包括在 这条路径上每个节点的未扩展的兄弟节点。
2018/12/18 人工智能 丁世飞 15
3.3.3 有界深度搜索和迭代加深搜索

对于深度d比较大的情况，深度优先搜索需要很 长的运行时间，而且还可能得不到解答。一种 比较好的问题求解方法是对搜索树的深度进行 控制，即有界深度优先搜索方法。

有界深度优先搜索过程总体上按深度优先算法 方法进行，但对搜索深度需要给出一个深度限 制dm，当深度达到了dm的时候，如果还没有找 到解答，就停止对该分支的搜索，换到另外一 个分支进行搜索。