广度优先搜索 先遍历同级所有节点，再遍历下级节点。 以初始节点为根节点，向下逐级扩展搜索树。 搜索树是自顶向下一层一层逐渐生成的。 So S4 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 广度优先搜索 先遍历同级所有节点,再遍历下级节点。 以初始节点为根节点, 向下逐级扩展搜索树。 搜索树是自顶向下一层一层逐渐生成的
深度优先搜索 搜索树每次只扩展每一层中的一个子节点： 直到不能再纵深扩展（到达叶子节点或受到深度限制）时，从当前节点 返回到上一级节点，沿另一方向又继续纵深扩展。 这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 如线式搜索过程 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 深度优先搜索 搜索树每次只扩展每一层中的一个子节点； 直到不能再纵深扩展(到达叶子节点或受到深度限制)时, 从当前节点 返回到上一级节点, 沿另一方向又继续纵深扩展。 这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 如线式搜索过程
搜索的具体实现问题 搜索树中有两类节点： ·已搜索的节点 ·待搜索的节点 用一动态数据结构记录已搜索的节点，称CLOSED表。 用另一动态数据结构登记当前待搜索的节点。称OPEN表。 OPEN表 CLOSED表 节点 父节点编号 编号 节点 父节点编号 西安电 科技大学此 堂此菠烈 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfmology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 搜索的具体实现问题 搜索树中有两类节点： •已搜索的节点 •待搜索的节点 用一动态数据结构记录已搜索的节点，称CLOSED表。 用另一动态数据结构登记当前待搜索的节点。称OPEN表
Open表/Closed表的一些概念 节点在Open表中，表明该节点还有子节点未被扩张（或未被搜索到）。 节点在Closed:表中，表明该节点的所有子节点都已搜索过（或已扩张）。 Open表为空，表明该图的所有节点都已搜索过。 Closed表用于回溯寻找最终路径。 Hangzhou Dianzi University杭州电子科技大学 Schoolo时Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 Open表/Closed表的一些概念 节点在Open表中，表明该节点还有子节点未被扩张（或未被搜索到）。 节点在Closed表中，表明该节点的所有子节点都已搜索过（或已扩张）。 Open表为空，表明该图的所有节点都已搜索过。 Closed表用于回溯寻找最终路径
Open表/Closed表的一些概念 Open表中节点排序规则决定搜索策略： •新增节点排在Open表末尾，为宽度优先搜索策略。 •新增节点排在Open表开头，为深度优先搜索策略。 ·当有新增节点时，Open表中所有节点按某先验信息排序， 为全局择优搜索策略。 ·当有新增节点时，Open表中仅新增节点按某先验信息排序， 为局部择优搜索策略。 Hangzhou Dianzi University杭州电子科技大学 Schoofo时Computer Science and Tecfnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 Open表/Closed表的一些概念 Open表中节点排序规则决定搜索策略： •新增节点排在Open表末尾，为宽度优先搜索策略。 •新增节点排在Open表开头，为深度优先搜索策略。 •当有新增节点时，Open表中所有节点按某先验信息排序， 为全局择优搜索策略。 •当有新增节点时，Open表中仅新增节点按某先验信息排序， 为局部择优搜索策略