用深度优先搜索和宽度优先搜索分别求图5．10所示的迷宫出路。
在这个迷宫中S是源节点F是目标节点ABCDE是5个具有二又分支的节点在每个节点处都可能会出现两种路线要么向左拐要么向右拐我们在每个二叉节点处设立两个虚节点以表示到该节点后的走向向右拐为第一个虚节点用下标1表示向左拐为第二个虚节点用下标2表示。例如A节点处向右拐的虚节点用A1表示向左拐的虚节点用A2表示。可以将该迷宫转换成一个有向图如图5．15所示。图中除F节点是目标节点外其余没有后继节点的虚节点都说明走入了死胡同。利用深度优先搜索其搜索树如图5．16所示图中节点旁所标数字为节点扩展次序。所得到的解路径为：S→A→A1→B→B1→C→C1→F也就是说从S出发在A节点处不能左拐而是直行到B节点处右拐到C节点也右拐即可到达出口F。利用宽度优先搜索其搜索树如图5．17所示图中节点旁所标数字为节点扩展次序。所得到的解路径也为：S→A→A1→B→B1→C→C1→F由搜索过程可以看出宽度优先搜索的效率低于深度优先搜索。在这个迷宫中,S是源节点,F是目标节点,A,B,C,D,E是5个具有二又分支的节点,在每个节点处,都可能会出现两种路线,要么向左拐要么向右拐,我们在每个二叉节点处设立两个虚节点,以表示到该节点后的走向,向右拐为第一个虚节点,用下标1表示,向左拐为第二个虚节点,用下标2表示。例如,A节点处向右拐的虚节点用A1表示,向左拐的虚节点用A2表示。可以将该迷宫转换成一个有向图如图5．15所示。图中,除F节点是目标节点外,其余没有后继节点的虚节点都说明走入了死胡同。利用深度优先搜索,其搜索树如图5．16所示,图中节点旁所标数字为节点扩展次序。所得到的解路径为：S→A→A1→B→B1→C→C1→F也就是说,从S出发,在A节点处不能左拐,而是直行,到B节点处右拐,到C节点也右拐,即可到达出口F。利用宽度优先搜索,其搜索树如图5．17所示,图中节点旁所标数字为节点扩展次序。所得到的解路径也为：S→A→A1→B→B1→C→C1→F由搜索过程可以看出,宽度优先搜索的效率低于深度优先搜索。
举一反三
内容
- 0
深度优先和宽度优先是两种图搜索。
- 1
中国大学MOOC: 深度优先搜索和宽度优先搜索都属于盲目搜索。
- 2
深度优先搜索和宽度优先搜索都属于盲目搜索。 A: 正确 B: 错误
- 3
盲目搜索策略主要包括（） A: 高度优先搜索 B: 宽度优先搜索 C: 深度优先搜索 D: 相似优先搜索
- 4
深度优先搜索与宽度优先搜索的区别是什么？