文档介绍：第四章知识利用(Knowledge Utilization)
知识处理( Knowledge Inference)
搜索推理技术
•引言
•盲目搜索法
•启发式搜索法
•推理机制
•小结
f
引言
•知识表达解决了把各种知识以计算能理解的语言存入了知识
库(有规则和事实),而ES,KE的最终目的是要利用这些知识
去解决实际的问题,产生经济效益,本章即讨论如何运用知
识,解决知识的处理和应用。
• :对网络或树结构进行搜索的方法。
盲目搜索(无知识搜索):不考虑给定问题的特定知识,
预先确定搜索规则,无信息引导。
启发式搜索(有知识搜索):考虑给定问题的可应用知
识,动态地确定搜索规则,优先调用较合适的规则。
• :前提到结论。
ÿ
盲目搜索法
图搜索策略
深度优先搜索法
宽度优先搜索法
ÿ
一、图搜索(Graph-Search)
•图:由节点组成,节点与节点以弧连接,从起始节点到目标
节点。
•有向图:弧线是由一个节点ni指向另一个节点nj的图。ni是
nj的父节点,nj是ni子节点
•费用:C(ni,nj)表示从ni指向nj的那段弧线的费用。
•树:每个节点只有一个父节点
根节点:没有父节点的节点
叶节点(梢节点):没有子节点的节点
路径:节点的序列
•图搜索:图搜索策略看作一种在图中寻找路径的方法
ÿ
一、图搜索策略
•图搜索控制策略
一种在图中寻找路径的方法。
图中每个节点对应一个状态,每条连线对应一个
操作符。这些节点和连线(即状态与操作符)又分
别由产生式系统的数据库和规则来标记。求得把
一个数据库变换为另一数据库的规则序列问题就
等价于求得图中的一条路径问题。
•图搜索过程图
ÿ
例:旅行线路问题,有五个城市,分别为S、A、B、
C、F,已知它们间的路径和距离,求以S城为起点,以
G城为终点的最短旅行路径。
网络网络
3030
4141 AA F
S
2222 1414
3232 5151
ÿ ÿ
先将旅行路线问题化为有向树结构来讨论各种搜索方式
f
二、深度优先搜索法(Depth First Search)
•也叫纵向搜索法
从根节点出发,只要有可能,向下
位的子节点搜索直至叶节点。若不
是目标,则返回上一个父节点(作
为当前节点)。即:
(1)在当前节点还有子节点存在
时,总是按某种约定顺序搜索一个
子节点(下一层、下位的某一节
点)直到搜索到叶节点。
(2)在当前节点已无未经搜索的子
节点时,回溯到其父节点,把父节
点当作当前节点。
ÿ
二、深度优先搜索法(Depth First Search)
v 定义
首先扩展最新产生的(即最深的)节点。
v 算法
防止搜索过程沿着无益的路径扩展下去,往
往给出一个节点扩展的最大深度——深度界
限。
f
二、深度优先搜索法(Depth First Search)
•
是一个冒失的方法,很容易滑过出现G节点的层次,而穷尽
下面各层的搜索,浪费很多时间,容易实现,但对层次较多
的树结构所得路径可能最坏。
当层次少,分叉多时使用
•有界深度优先搜索:通过限制搜索深度的方法来部分地避免
搜索的盲目性。
事先确定一个“最大的搜索深度”,当系统搜索到规定的
深度时,不再盲目地向纵深发展,而是返回到它的回溯点,
然后横向地继续向下搜索。
•随机深度优先搜索:不再按向左或向右顺序往纵深搜索,而
是随机地选择其中一条分支向下搜索。
f