中南大学：《人工智能》第三章 搜索推理技术

Artificial Intelligence 第三章搜索推理技术 一 3.1图搜索策略3,6产生式糸统 32盲目搜索 3.7糸统组织技术 3.3启发式搜索3.8不确定性推理 3.4消解原理 39非单调推理 35规则演绎糸统3.10小结

第三章 搜索推理技术 3.6 产生式系统 3.7 系统组织技术 3.8 不确定性推理 3.9 非单调推理 3.10 小结 3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 消解原理 3.5 规则演绎系统

3.1图搜索策略 C图搜索控制策略 种在图中寻找路径的方法 图中每个节点对应一个状态,每条连线对应 个操作符。这些节点和连线(即状态与操j (作符)又分别由产生式系统的数据库和规则 来标记。求得把一个数据庠变换为另一数据 庳的规则序列问題就等价于求得图中的一条 路径问题 令图搜索过程图

2 3.1 图搜索策略 ❖图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应 一个操作符。这些节点和连线(即状态与操 作符)又分别由产生式系统的数据库和规则 来标记。求得把一个数据库变换为另一数据 库的规则序列问题就等价于求得图中的一条 路径问题。 ❖图搜索过程图

3.1图搜索策略 开始 「把S放入OPEN表 是 OPEN表为空表? 失败 ↓否 把第一个节点(m)从OPEN表移至 CLOSED表」 n为目标节点吗? 成功 否 把n的后继节点放入OPEN表的 末端,提供返回节点∏的指针 修改指针方向 重排OPEN表 图31图搜索过程框图 3

3 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 n为目标节点吗？ 把n的后继节点放入OPEN表的 末端，提供返回节点n的指针 修改指针方向 重排OPEN表 失败 成功 图3.1 图搜索过程框图 是 是 否 否 3.1 图搜索策略

32盲目搜索 特点:不需重排OPEN表 种类:宽度优先、深度优先、等代价搜索等。 32.1宽度优先搜索 令定义 以接近起始节点的程度逐层扩畏节点的搜索方法。 ◇特点 一种高代价搜索,但若有解存在,则必能找到它。 算法

4 3.2 盲目搜索 ❖特点：不需重排OPEN表 ❖种类：宽度优先、深度优先、等代价搜索等。 3.2.1 宽度优先搜索 ❖ 定义 以接近起始节点的程度逐层扩展节点的搜索方法。 ❖ 特点： 一种高代价搜索，但若有解存在，则必能找到它。 ❖ 算法

32盲目搜索 开始 把S放入OPEN表 <OPEN表为空表? 是 失败 把第一个节点()从OPEN表移至 CLOSED表 扩畏n,把n的后继节点放入OPEN 表的末端,提供返回节点n的指针 是否有后继节点 是 为目标节点? 成功 否 图32宽度优先算法框图 5

5 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 是否有后继节点 为目标节点？ 扩展n，把n的后继节点放入OPEN 表的末端，提供返回节点n的指针 失败 成功 图3.2 宽度优先算法框图 是 否 是 否 3.2 盲目搜索

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 盲目搜索