4.2.1 广度优先搜索方法 课件

广 度 优 先 搜 索 方 法 假设重排九宫问题的棋盘初始状态是S0，如图1，棋盘目标状态如图2所示，我们用Sg表示。从S0开始，到达棋盘目标状态Sg，并把移动过程中的棋盘状态记录下来 。九宫格问题。图1图2S0第0层 S0第0层 第1层 S0B1B2B3B4第0层 第1层 第2层 C1C2C3C4C5C6C7C8S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8第0层 第1层 第2层 第3层 第4层 S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2第0层 第1层 第2层 第3层 第4层 S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4第0层 第1层 第2层 第3层 第4层 S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6第0层 第1层 第2层 第3层 第4层 S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6第0层 第1层 第2层 第3层 第4层 ……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 从根节点开始，在树中一层一层地查找，当找到目标节点时，搜索结束。广度优先搜索方法：……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 ……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 ……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 ……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 ……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 3、当树的节点增多且层次很多时，需要搜索的节点将增多，因此，搜索所需的时间会增加。广度优先搜索方法的主要特点：1、如何搜索，搜索到什么状态结束2、是否一定能够找到目标3、搜索所用的时间1、沿着树的分支节点逐层横向搜索，若找到目标节点，则结束搜索。2、能够找到目标节点。……S0B1B2B3B4C1C2C3C4C5C6C7C8D1D2D3D4D5D6D7D8E1E2E3E4E5E6E7第0层 第1层 第2层 第3层 第4层 如图是一个迷宫，S0是入口，Sg是出口，我们把入口作为初始节点，出口作为目标节点，通道作为分支，画出从入口S0出发，寻找出口Sg的迷宫问题的状态树。迷宫问题。入口 S0出口 Sg知识拓展旅顺汽车站旅顺中学文体中心广度优先搜索方法： 从根节点开始，在树中一层一层地查找，当找到目标节 点时，搜索结束。广度优先搜索方法的主要特点： 1、沿着树的分支节点逐层横向搜索，若找到目标节点，则结束搜索。 2、能够找到目标节点。 3、当树的节点增多且层次很多时，需要搜索的节点将增多，因此，搜索所需的时间会增加。4.2.1 广度优先搜索方法