树式搜索算法 步1把初始节点So放入OPEN表中。 步2若OPEN表为空，则搜索失败，退出。 步3移出OPEN表中第一个节点N放入CLOSED表中， 并冠以顺序编号n。 步4若目标节点Sg=N,则搜索成功，结束。 步5若N不可扩展，则转步2。 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 树式搜索算法 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。 步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2
树式搜索算法（2) 步6扩展N,生成一组子节点，对这组子节点做如下处理： ·删除N的父节点。 ·对于已存在于OPEN表的节点（如果有的话）；比较其返回初始节点的新路径 与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针， 使其沿新路返回；否则删除。 Hang2 hou Dianzi University杭州电子科技大学 School of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 树式搜索算法（2） 步6 扩展N, 生成一组子节点, 对这组子节点做如下处理： •删除N的父节点。 •对于已存在于OPEN表的节点(如果有的话)；比较其返回初始节点的新路径 与原路径,如果新路径“短”, 则修改这些节点在OPEN表中的原返回指针, 使其沿新路返回；否则删除
树式搜索算法(3) ·对已存在于CLOSED表的节点（如果有的话），做与(2)同样的处 理，并且再将其移出CLOSED表，放入OPEN表重新扩展（为了重 新计算代价)。 ·对其余子节点配上指向N的返回指针后放入OPEN表中某处， 或对OPEN表进行重新排序，转步2。 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 树式搜索算法（3） •对已存在于CLOSED表的节点(如果有的话), 做与(2)同样的处 理, 并且再将其移出CLOSED表, 放入OPEN表重新扩展(为了重 新计算代价)。 •对其余子节点配上指向N的返回指针后放入OPEN表中某处, 或对OPEN表进行重新排序,转步2
广度优先搜索策略解八数码 学版 电子科放大房出版程 83 765 283 83 八数码问题等效于 765 65 765 对空格可施行上下 右移动等四种操作。 65 6 14 16 22 23 765 7265 出止登业%注 高感山军测是止必业据是 Hangzhou Dianzi University杭州电子科技大学 Schoof of Computer Science and Tecfinology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 广度优先搜索策略解八数码 八数码问题等效于 对空格可施行上下 右移动等四种操作
广度优先搜索策略解八数码 65 第一步：0pen:1 ”子技大星业我园 电子明发大度成脱 283 Closed:空 第二步： 6 6 65 0pen:2,3,4,5 Closed:1 民子种收大雪欢版羽 76 排列到Open表最后 第 8 83 /8 765 0pen:3,4,5,6,7 Closed:1,2 6 65 Hangzhou Dianzi University杭州电子科技大学 School of Computer Science and Tecfmnology计算机学院周文晖
Hangzhou Dianzi University 杭州电子科技大学 School of Computer Science and Technology 计算机学院 周文晖 广度优先搜索策略解八数码 第一步：Open: 1 Closed: 空 第二步： Open: 2, 3, 4, 5 Closed: 1 第三步： Open：3, 4, 5, 6, 7 Closed: 1, 2 排列到Open表最后