第3章囹搜索与问题求解 需说明的是,上述算法仅是搜索目标节点的算法,当搜索 成功后,如果需要路径,则还须由 CLOSED表再找出路径。找 路径的方法是:对于树式搜索,从 CLOSED表中序号最大的节 点起,根据返回指针追溯至初始节点S,所得的节点序列或边序 列即为所找路径;对于线式搜索, CLOSED表即是所找路径
第 3 章 图搜索与问题求解 需说明的是,上述算法仅是搜索目标节点的算法, 当搜索 成功后, 如果需要路径, 则还须由CLOSED表再找出路径。找 路径的方法是： 对于树式搜索, 从CLOSED表中序号最大的节 点起,根据返回指针追溯至初始节点So,所得的节点序列或边序 列即为所找路径；对于线式搜索, CLOSED表即是所找路径
第3章囹搜索与问题求解 3.1.3穷举式搜索 1.广度优先搜索 广度优先搜索就是始终先在同一级节点中考査,只有当同 级节点考査完之后,才考查下一级节点。或者说,是以初始 节点为根节点,向下逐级扩展搜索树。所以,广度优先策略的 搜索树是自顶向下一层一层逐渐生成的
第 3 章 图搜索与问题求解 3.1.3 穷举式搜索 1. 广度优先搜索就是始终先在同一级节点中考查, 只有当同 一级节点考查完之后, 才考查下一级节点。或者说,是以初始 节点为根节点, 向下逐级扩展搜索树。所以,广度优先策略的 搜索树是自顶向下一层一层逐渐生成的
第3章囹搜索与问题求解 例3.3用广度优先搜索策略解八数码难题。 由于把一个与空格相邻的数码移入空格,等价于把空格向 数码方向移动一位。所以,该题中给出的数码走步规则也可以 简化为:对空格可施行左移、移、上移和下移等四种操作 设初始节点S和目标节点S分别如图3-3的初始棋局和目标 棋局所示,我们用广度优先搜索策略,则可得到如图3-6所示的 搜索树
第 3 章 图搜索与问题求解 例 3.3 用广度优先搜索策略解八数码难题。 由于把一个与空格相邻的数码移入空格, 等价于把空格向 数码方向移动一位。所以,该题中给出的数码走步规则也可以 简化为： 对空格可施行左移、移、上移和下移等四种操作。 设初始节点So和目标节点Sg分别如图3-3的初始棋局和目标 棋局所示, 我们用广度优先搜索策略, 则可得到如图3-6所示的 搜索树
第3章囹搜索与问题求解 安电子大学出版 765 资, 4 83 83 64 765 910 8 283 3 84 65 6576576 16 1718 1920 283123 34 83283 8 765 22 6234 214 765265立求的立 图3-6八数码问题的广度优先搜索
第 3 章 图搜索与问题求解 图 3-6 八数码问题的广度优先搜索
第3章囹搜索与问题求解 广度优先搜索算法: 步1把初始节点S放入OPEN表中。 步2若OPE表为空,则搜索失败,退出。 步3取OPE表中前面第一个节点A放在 CLOSED表中,并冠 以顺序编号n。 步4若目标节点S=N,则搜索成功,结束。 步5若M可扩展,则转步2。 步6扩展N将其所有子节点配上指向N的指针依次放入 OPEN表尾部,转步2
第 3 章 图搜索与问题求解 广度优先搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败,退出。 步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠 以顺序编号n。 步4 若目标节点Sg=N,则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 将其所有子节点配上指向N的指针依次放入 OPEN表尾部, 转步2