32盲目搜索 例子 八数码难题(8- puzzle problem) 283 12|3 4 8 4 765 765 (初始状态) (目标状态丿 規定:将牌移入空格的顺序为:从空格左边开始 顺时针旋转。不许斜向移动,也不返回先辈节点 从图可见,要扩畏26个节点,共生成46个节点 后才求得解(目标节点)。 6
6 ❖ 例子 八数码难题（8-puzzle problem） 1 2 8 3 4 7 6 5 1 2 3 8 4 7 6 5 （初始状态） （目标状态） 规定：将牌移入空格的顺序为：从空格左边开始 顺时针旋转。不许斜向移动，也不返回先辈节点。 从图可见，要扩展26个节点，共生成46个节点 之后才求得解（目标节点）。 3.2 盲目搜索
3.2盲目搜索 3 10 13 18 23 27 26 畾翩翻關 图34八数码难題的宽度优先搜索树
7 1 2 8 3 4 7 6 5 2 1 8 3 4 1 2 8 3 4 6 5 7 1 4 2 3 8 7 6 5 1 2 3 8 4 1 2 8 3 4 5 6 7 1 2 8 3 4 5 6 7 1 2 3 8 4 7 6 5 6 7 8 9 10 11 12 13 1 2 8 3 4 5 7 6 5 7 6 5 7 6 1 1 2 8 3 4 7 6 5 1 2 3 8 4 7 6 5 1 2 8 3 4 5 6 7 1 2 8 3 4 7 6 5 2 3 4 5 图3.4 八数码难题的宽度优先搜索树 1 3 4 6 5 1 2 8 3 4 7 6 5 1 2 8 3 4 6 5 7 1 2 8 3 4 6 5 7 1 2 3 8 4 6 5 7 1 2 3 8 4 7 6 5 23 24 25 26 27 2 1 3 7 6 8 22 2 1 8 3 4 7 6 5 1 2 8 3 4 6 5 7 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 8 3 4 5 6 7 1 2 8 3 5 4 6 7 1 2 3 8 4 7 6 5 14 15 16 17 18 19 20 21 1 2 8 3 4 5 7 6 3.2 盲目搜索
32盲目搜索 ■3.2.2深度优先搜索 ☆定义 首先扩展最新产生的(即最深的)节点。 令算法 防止搜索过程沿看无益的路径扩展下去 (往往给出一个节点扩展的最大深度——深度界 限 C与宽度优先搜索算法最根本的不同在于 将扩長的后继节点放在OPEN表的前端。(算 法框图见教材 8
8 3.2.2 深度优先搜索 ❖ 定义 首先扩展最新产生的(即最深的)节点。 ❖ 算法 防止搜索过程沿着无益的路径扩展下去， 往往给出一个节点扩展的最大深度——深度界 限。 与宽度优先搜索算法最根本的不同在于： 将扩展的后继节点放在OPEN表的前端。（算 法框图见教材） 3.2 盲目搜索
32盲目搜索 ■3.2.3等代价搜索 ☆定义 是宽度优先搜索的一种推广,不是沿看等长度 路径新层进行扩畏,而是沿看等代价路径断层进 行护展。 搜索树中每条连接孤线上的有关代价,表示时 间、距离等花费。 令算法 。若所有连接弧线具有相等代价,则简化为宽 度优先搜索算法
9 3.2.3 等代价搜索 ❖ 定义 是宽度优先搜索的一种推广，不是沿着等长度 路径断层进行扩展，而是沿着等代价路径断层进 行扩展。 搜索树中每条连接弧线上的有关代价,表示时 间、距离等花费。 ❖ 算法 若所有连接弧线具有相等代价，则简化为宽 度优先搜索算法。 3.2 盲目搜索
(开始) 3.2盲目搜索 把S放OPEN表 5否节点?是一成功) 图32等代价披索算法框图 ↓否 令g(s)=0 OPEN表为变表?是一〈失败 否 把具有最小9(1)值的节点从OPEN表移 至 CLOSED表 是否有后继节点 是 为目标节点? 成功 否 汁展,计算其后继节点的g(j), 并把后结节点效入OPN表 10
10 开始 把S放入OPEN表 OPEN表为空表？ 把具有最小g(i)值的节点i从OPEN表移 至CLOSED表 是否有后继节点 为目标节点？ 失败 成功 图3.2 等代价搜索算法框图 是 否 是 否 令g(s)=0 S是否目标节点？ 是 成功 扩展i，计算其后继节点j的g(j)， 并把后继节点放入OPEN表 否 3.2 盲目搜索