文档介绍：搜索
搜索算法是人工智能中的一种基本方法,利用计算机的高性能来有目的、有方法地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。
在建立搜索算法时,首先需要关注的问题是以什么作为状态,这些状态之间有什么样的联系。其实,在这样的思考过程中,我们已经不知不觉地将一个具体的问题抽象成一个图论的模型—树,即搜索算法的使用第一步在于搜索树的建立。
由上图可以知道,这样形成的一棵树叫搜索树。初始状态对应着根结点,目标状态对应着目标结点。排在前的结点叫父结点,其后的结点叫子结点,同一层中的结点是兄弟结点,由父结点产生的子结点叫扩展。
完成搜索的过程就是找到一条从根结点到目标结点的路径,找出一个最优的解。
这种搜索算法的实现类似于图或树的遍历,通常可以有两种不同的实现方法:深度优先搜索(DFS)和广度优先搜索(BFS)。
深度优先搜索(DFS)
一、DFS的含义
深度优先搜索(DFS,Depth First Search)是一种常见的搜索方法。常用来求一解、全部解或者是最优解。
它所遵循的搜索策略是尽可能“深”的搜索,在搜索树的每一层始终先只扩展一个子结点,不断地向纵深前进直到不能再前进(到达叶子结点或受到深度限制)时,才从当前结点返回到父亲结点,沿另一个方向又继续前进,如此反复,直到求得最优解。
这种方法的搜索树是从树根开始,一枝一枝逐渐形成的,即在搜索的过程中产生搜索树。
在深度优先搜索过程中,常用作标记的方法记录访问过的状态,这种处理方法使得深度优先搜索法与回溯没什么区别了,DFS与回溯成为同一算法的两个不同的名称。
在下面搜索树中,搜索顺序如下:
深度优先搜索顺序如下: A→B→D→H→I→E→J→C→F→G
二、DFS算法的程序
深度优先搜索算法可以简单地表述为“能深则深,不能深则回”的策略,具体表现在以下三个方面:
——能深则深
如果扩展到当前i阶段的一个k方案(树中的结点)符合条件,则扩展(用入栈)表示,并继续按纵深方向向下一个结点扩展(符合递归的思路),表示阶段号的参数i表现为从小到大的变化趋势。
——不能深则回
如果当前要扩展的结点不符合条件,则立即放弃此后的结点扩展(此处的扩展即为搜素,用出栈表示,阶段号i则体现为由大变小这样一种变化),换另一种方案扩展。回的时候常会遇见两种情况:
1)一种情况是i阶段的所有方案已经试探过,此时只能回到i-1阶段,在i-1阶段换一种方案试探,i-1阶段的搜索方式依次类推;
2)另一种情况是i阶段还有试探方案,则在i阶段换另一种方案,在程序中常用穷举i阶段的方案来实现。
常用栈来保存搜索过程中的状态和路径,所需空间大小为搜索所需最长路径的长度。
根据以上描述,每个阶段的扩展方式是一样的,常用递归程序描述扩展第i阶段:
procedure DFS (i:integer); { 对第i阶段进行扩展试探}
begin
for r:=1 to maxr do { 穷举当前阶段所有可能的决策k(方案、结点)}
if 子结点符合条件 then
begin
扩展子结点(入栈)
if 子结点是目标结点 then 输出结果
else 调用DFS (i+1)
栈顶元素出栈{ 回溯}
end;
e