信息技术粤教版第四章问题求解4.2 基本搜索方法优秀课件ppt

展开

这是一份信息技术粤教版第四章问题求解4.2 基本搜索方法优秀课件ppt，共16页。PPT课件主要包含了广度优先搜索方法，搜索路径，深度优先捜索方法等内容，欢迎下载使用。

广度优先搜索方法是什么？
广度优先搜索方法是：从根节点开始，在树中一层一层地查找，当找到目标节点时，搜索结束。
下图是重排九宫问题的广度优先搜索过程。
重排九宫问题状态树的广度优先搜索示意图
SO→B1→B2→B3→B4→C1→C2→C3→C4→C5→C6→C7→C8→D1→D2→D3→D4→D5→D6→D7→D8→E1→E2→E3→E4→Sg（如上图虚箭头所示）
广度优先搜索方法的主要特点是：
（1）沿着树的分支节点逐层横向搜索，若找到目标节点，则结束搜索。（2）能够找到目标节点。广度优先搜索方法是沿着树的分支节点横向搜索，若找不到目标节点，搜索不会停止，只要目标节点在树上，用广度优先搜索方法进行搜索，就一定能找到目标节点。（3）当树的节点增多且层次很多时，需要搜索的节点将增多，因此，搜索所需的时间会增加。
深度优先搜索方法是从树的根节点开始，对其分支逐个深入搜索。为了方便，通常从左分支开始，如果目标状态不在左分支上，则向右继续逐个分支进行搜索，直到找到目标为止。
下图画出了重排九宫问题的深度优先搜索过程。蓝色虚线表示搜索路径，洋红色虚线表示返回去寻找具有未被探索的分支节点的路径。
重排九宫问题状态树的深度优先搜索示意图
SO→Bl→Cl→D1→El→E2→C2→D2→E3→E4→B2→C3→D3→Sg
深度优先搜索方法的主要特点是：
（1）在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。（2）如果目标节点恰好在此分支上，则可较快地得到目标节点。（3）如果目标节点不在该分支上，而该分支又是有穷的，当搜索到叶节点后，则返回到最近的分支节点，从该节点未被探索的分支开始，重新纵向深入搜索。
重排九宫问题状态树的深度优先搜索特例
（1）分别用广度优先搜索方法和深度优先搜索方法搜索（左下图所示）的状态树A。图中SO是根节点，Sg是目标节点。将搜索路径填入（右下表中）。
根据上面的搜索结果，用_____方法搜索的状态树A，搜索速度更快。
（2）别用广度优先搜索方法和深度优先搜索方法搜索（左下图所示）的状态树B，图中SO是根节点，Sg是目标节点，将搜索路线填入（右下表中）中。