c++搜索算法 树形搜索 深度优先搜索算法

本文将对搜索算法的基本概念、树形搜索、深度优先搜索算法进行详细的解释，并提供递归实现的程序框架和循环实现的方法。 一、搜索算法的基本概念 搜索算法是指在问题的状态空间中寻找解的过程。状态（state）是问题在某一时刻的进展情况的数学描述。算符（operator）/ 状态转移是问题从一种状态变换成另一种（或几种）状态的操作。解答树是搜索的过程实际是在遍历一个图，它的结点就是所有的状态，有向边对应于算符，而一个可行解就是一条从起始节点出发到目标状态集中任意一个结点的路径。特个图称为状态空间（state space），这样搜索称为状态空间搜索（Single-Agent Search），得到的遍历树称为解答数。 二、树形搜索 树形搜索是指在状态空间中搜索的过程。它可以分为两种：深度优先搜索（DFS）和宽度优先搜索（BFS）。 1. 深度优先搜索（DFS） 深度优先搜索的搜索策略是尽可能深地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探索到的边，就沿此边继续搜索下去。当结点 V 的所有边都已被探寻过时，搜索将回溯到发现结点 V 有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。 2. 宽度优先搜索（BFS） 宽度优先搜索的搜索策略是从源结点开始，把所有该结点的子结点都搜索完，在搜索每个结点的时候都把其子结点都放入一个队列的后面等待以后搜索，当把此层结点全部搜索完时，所有的下层结点也就进入了队列，继续这样的过程。 三、深度优先搜索算法 深度优先搜索算法是一种常用的搜索算法，它可以用递归或循环实现。下面是递归实现的程序框架： Procedure DepthFirstSearch(State:Statetype;depth:integer); Begin For Operand:=1 to Operandcount(State) do Begin NewState:=DoOperand(State,Operand); If Answer then PrintAnswer Else if depth<maxdepth then Search(NewState,depth); End; End; 这个框架只是最简单的，它有很多可以变形。 四、剪枝 剪枝是在搜索的过程中，在还没到达叶结点之前就可以判断以此结点为根的子树不可能包含可行解或者最优解，因此不需要扩展这颗树，就像拿一把剪刀把这颗子树剪去，称为剪枝。 五、其他搜索算法 还有一些搜索算法的概念没有给出，如分支限界搜索、迭代加深搜索、迭代加宽搜索、A*算法等。他们都各种有适应的范围，也是较为复杂的搜索。 六、专题 1：深度优先搜索 DFS 深度优先搜索有很多呈现形式，一般用递归解决，但也可循环等解决，不管用什么实现，其都会遵循深度优先思想。 结语： 搜索算法是计算机学院中非常重要的一部分，在ACM比赛中也非常常见。因此我们需要着重掌握各类搜索算法，才能面对各类即将到来的ACM大赛。