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