第3章图搜索与问题求解 需说明的是，上述算法仅是搜索目标节点的算法，当搜索 成功后，如果需要路径，则还须由CLOSED表再找出路径。找 路径的方法是：对于树式搜索，从CLOSED表中序号最大的节 点起，根据返回指针追溯至初始节点S。,所得的节点序列或边序 列即为所找路径；对于线式搜索，CLOSED表即是所找路径
第 3 章 图搜索与问题求解 需说明的是,上述算法仅是搜索目标节点的算法, 当搜索 成功后, 如果需要路径, 则还须由CLOSED表再找出路径。找 路径的方法是： 对于树式搜索, 从CLOSED表中序号最大的节 点起,根据返回指针追溯至初始节点So,所得的节点序列或边序 列即为所找路径；对于线式搜索, CLOSED表即是所找路径
第3章图搜索与问题求解 3.1.3穷举式搜索 1.广度优先搜索 广度优先搜索就是始终先在同一级节点中考查，只有当同 一级节点考查完之后，才考查下一级节点。或者说，是以初始 节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的 搜索树是自项向下一层一层逐渐生成的
第 3 章 图搜索与问题求解 3.1.3 穷举式搜索 1. 广度优先搜索就是始终先在同一级节点中考查, 只有当同 一级节点考查完之后, 才考查下一级节点。或者说,是以初始 节点为根节点, 向下逐级扩展搜索树。所以,广度优先策略的 搜索树是自顶向下一层一层逐渐生成的
第3章图搜索与问题求解 例3.3用广度优先搜索策略解八数码难题。 由于把一个与空格相邻的数码移入空格，等价于把空格向 数码方向移动一位。所以，该题中给出的数码走步规则也可以 简化为：对空格可施行左移、移、上移和下移等四种操作。 设初始节点S,和目标节点$.分别如图3-3的初始棋局和目标 棋局所示，我们用广度优先搜索策略，则可得到如图3-6所示的 搜索树
第 3 章 图搜索与问题求解 例 3.3 用广度优先搜索策略解八数码难题。 由于把一个与空格相邻的数码移入空格, 等价于把空格向 数码方向移动一位。所以,该题中给出的数码走步规则也可以 简化为： 对空格可施行左移、移、上移和下移等四种操作。 设初始节点So和目标节点Sg分别如图3-3的初始棋局和目标 棋局所示, 我们用广度优先搜索策略, 则可得到如图3-6所示的 搜索树
第3章图搜索与问题求解 场姿电子科发大学常版程 堂子科技大学成藏烈 2 83 4 > 6 3 28 3 8 4 1 76 76 5 765 7 6 9 10 11 12 13 8 3 2 3 2 8 3 2 8 2 3 2 1 8 4 6 7 6 5 6 5 6 6 6 5 14 5 16 17 18 19 20 2 3 3 3 3 2 3 8 4 8 6 5 6 5 6 22 23 8 3 8 3 2 4 765 765 路动% 高盛山军这之必业房妇 图3-6八数码问题的广度优先搜索
第 3 章 图搜索与问题求解 图 3-6 八数码问题的广度优先搜索
第3章图搜索与问题求解 广度优先搜索算法： 步1把初始节点S,放入OPEN表中。 步2若OPE表为空，则搜索失败，退出。 步3取OPE表中前面第一个节点W放在CLOSED表中，并冠 以顺序编号n。 步4若目标节点S。N,则搜索成功，结束。 步5若不可扩展，则转步2。 步6扩展N,将其所有子节点配上指向W的指针依次放入 OPEN表尾部，转步2
第 3 章 图搜索与问题求解 广度优先搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败,退出。 步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠 以顺序编号n。 步4 若目标节点Sg=N,则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 将其所有子节点配上指向N的指针依次放入 OPEN表尾部, 转步2