还剩14页未读,
继续阅读
所属成套资源:粤教版信息技术选修5人工智能初步课件PPT
成套系列资料,整套一键下载
- 4.1 重排九宫问题及其树的表示 课件 课件 0 次下载
- 4.2 基本搜索方法 课件 课件 0 次下载
- 4.3 启发式搜索 课件 课件 0 次下载
- 4.4 求解博弈问题 课件 课件 0 次下载
- 4.5 浅谈机器证明 课件 课件 0 次下载
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 广度优先搜索方法