4.2.1广度优先搜索方法

4 2基本搜索方法 4 2 1广度优先搜索方法 假设重排九宫问题的棋盘初始状态是S0 如图1 棋盘目标状态如图2所示 我们用Sg表示 从S0开始 到达棋盘目标状态Sg 并把移动过程中的棋盘状态记录下来 九宫格问题 图1 图2 S0 第0层 S0 第0层 第1层 S0 B1 B2 B3 B4 第0层 第1层 第2层 C1 C2 C3 C4 C5 C6 C7 C8 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 从根节点开始 在树中一层一层地查找 当找到目标节点时 搜索结束 广度优先搜索方法 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 3 当树的节点增多且层次很多时 需要搜索的节点将增多 因此 搜索所需的时间会增加 广度优先搜索方法的主要特点 1 如何搜索 搜索到什么状态结束2 是否一定能够找到目标3 搜索所用的时间 1 沿着树的分支节点逐层横向搜索 若找到目标节点 则结束搜索 2 能够找到目标节点 S0 B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 E1 E2 E3 E4 E5 E6 E7 第0层 第1层 第2层 第3层 第4层 如图是一个迷宫 S0是入口 Sg是出口 我们把入口作为初始节点 出口作为目标节点 通道作为分支 画出从入口S0出发 寻找出口Sg的迷宫问题的状态树 迷宫问题 入口S0 出口Sg 知识拓展 旅顺汽车站 旅顺中学 文体中心 广度优先搜索方法 从根节点开始 在树中一层一层地查找 当找到目标节点时 搜索结束 广度优先搜索方法的主要特点 1 沿着树的