深度优先搜索(补充教案)

《深度优先搜索(补充教案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深度优先搜索（补充教案）一、搜索过程深度优先搜索的搜索过程类似树的先序遍历，也叫回溯法。搜索过程如下：从源节点开始发现有一节点v，如果v还有未探测到的边，就沿此边继续探测下去，当节点v的所有边都被探测过，搜索过程将回溯到最初发现v点的源节点。这一过程一直进行到已发现从源节点可达的所有节点为止。这显然是一个递归过程。为了在遍历过程中区分顶点是否被访问，往往可以引入一个数组，如以mark[1..n]作为标记。数组的元素取0和1，初值为0。当节点被访问时，与节点相应得数组元素为1，每次访问节点时，都得先检查它的标记值，找0值得节点访问，并深度继续。深度大的先得到扩展，具有

2、“后产生先扩展”的特点，因此在数据结构上采用堆栈来存储（新节点入栈，节点不能扩展时，栈定出栈）。二、搜索特点1、由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。2、深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。3、由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。4、深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。5、适用范围：适用于求

3、解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。三、算法描述1、算法数据结构描述：深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN表，直到搜索到目标结点或OPEN栈空为止。具体算法如下：①把起始结点S放

4、到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。②如果OPEN为一空表，则搜索失败退出。③取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。④如果结点ｎ的深度等于最大深度，则转向２。⑤否则，扩展结点ｎ，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向ｎ的返回指针；如果没有后裔，则转向２。⑥如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向２。第11页共11页2、算法程序描述：①递归　　递归过程为：　　ProcedureDEF-GO(step)　　　fori:=

5、1tomaxdo　　　　if子结点符合条件then　　　　　产生新的子结点入栈；　　　　　　if子结点是目标结点then输出　　　　　　　elseDEF-GO(step+1)；　　　　　　栈顶结点出栈；　　　　　endif；　　　　enddo；　　主程序为：　　ProgramDFS；　　　初始状态入栈；　　　DEF-GO(1)；②非递归　　ProgramDEF(step)；　　step:=0；　　repeat　　step:=step+1；　　j:=0；p:=false　　　repeat　　　　j:=j+1；　　　　if结点符合条件then　　　　　产生子结点入栈；　

6、　　　　　if子结点是目标结点then输出　　　　　　　elsep:=true；　　　　　else　　　　　　ifj>=maxthen回溯p:=false；　　　　endif；　　　untilp=true；　　untilstep=0；　　回溯过程如下：　　ProcedureBACK；　　　step:=step-1；　　　ifstep>0then栈顶结点出栈　　　　elsep:=true；第11页共11页例如　八数码难题--已知８个数的起始状态如图1（ａ），要得到目标状态为图1(ｂ）。　　　　　　　２　８　３　　　　　　　　　　　　　１　２　３　　　　　　　１　６　４

7、　　　　　　　　　　　　　８　■　４　　　　　　　７　■　５　　　　　　　　　　　　７　６　５　　　　　　　　（ａ）　　　　　　　　　　　　　　　（ｂ）图1求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图2的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为５。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。　图2四、关于深度优先搜索的下界对于许多问题，深度优先搜索查找的解答树