文章目录

前言一、终点未知的搜索（Uninformed search strategies）深度优先搜索（DFS）和广度优先搜索（BFS）深度限制搜索迭代加深搜索评价

---

前言

Uninformed search strategies直译为不知情的搜索，即在已知起点位置，未知终点未知的情况下寻找最佳路径的方法。与启发式搜索不同，启发式搜索详见第二章。

---

一、终点未知的搜索（Uninformed search strategies）

Breadth-First Search（BFS）广度优先广度优先搜索

Depth-First Search（DFS）深度优先

Depth-Limited Search（DLS）深度限制搜索

Iterative Deepening Search（IDS）迭代加深搜索

深度优先搜索（DFS）和广度优先搜索（BFS）

区别仅仅在：

- 深度优先搜索，在队列的头加入新的候选节点- 广度优先搜索，在队列的尾加入新的候选节点

二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

先序遍历：35 20 15 16 29 28 30 40 50 45 55

中序遍历：15 16 20 28 29 30 35 40 45 50 55

后序遍历：16 15 28 30 29 20 45 55 50 40 35

广度优先遍历：35 20 40 15 29 50 16 28 30 45 55

深度限制搜索

深度限制搜索其实是深度优先搜索的变体，它限制住了访问的深度。因为当一棵树的子树过深时，进行深度搜索会在该子树上消耗太多的时间，所以，在在DLS算法中，若该节点当前深度大于限制深度K，那就不再继续遍历K节点的子女。实质上就是限定下界的深度优先搜索。

迭代加深搜索

迭代加深（Iterative deepening）搜索是深度限制搜索的升级版本，即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。

在迭代加深搜索的算法中，连续的深度优先搜索被引入，每一个深度约束逐次加1，直到搜索到目标为止。

评价

根据以下维度评估策略：

完整性（Complete）：是否总会找到解决方案？

时间复杂度（Time）：生成的节点数

空间复杂度（Space）：内存中的最大节点数

最优性（Optimal）：是否总能找到成本最低的解决方案？

时间和空间的复杂性是根据

b：搜索树的最大分支因子

d：成本最低的解决方案的深度

m：状态空间的最大深度（可以为∞）

广度优先搜索评价

深度优先搜索评价

迭代加深搜

summary