人工智能与专家系统第三章PPT课件.ppt

《人工智能与专家系统第三章PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一节知识推理的概念和类型第二节基本搜索策略第三节启发式搜索策略第四节与/或树图搜索第五节博弈树图搜索第三章知识的推理技术第一节知识推理的概念和类型一、知识推理的概念1、知识推理——运用知识求解问题2、知识推理技术——是问题从初始状态转移到目标状态的方法和途径3、知识推理技术的研究目标——寻找从初始状态沿着最优或最经济的途径转移到目标状态的智能操作序列，实现问题求解过程的计算机化二、知识推理的分类1、根据知识表达方式图搜索法——如广度优先法、深度优先法逻辑论证法——如王浩命题逻辑算法、鲁滨逊谓词逻辑算法2、根据推理过程的完备性推理算法——完备的推理过程，如广度优先法推理步骤——不完备的推理过

2、程，如深度优先法3、根据推理过程是否运用启发性知识启发推理——运用启发性知识，提高搜索效率，如全局择优法、局部择优法非启发推理——效率较低，如广度优先法第一节知识推理的概念和类型三、符号模式匹配1、概念符号模式——用于知识表达的各种符号表达式匹配——比较和选配符号模式匹配——将一个符号表达式与另一个符号表达式进行比较和选配，判断它们是否可以相互匹配事实模式目标模式——目标模式的各分量都可被事实模式匹配，称目标模式可匹配第一节知识推理的概念和类型2、示例例1——设有谓词公式P1:MARRIAGE(john,mary)∧MALE(john)∧FEMALE(mary)P2:MARRIAGE(joh

3、n,mary)∧MALE(john)检查P1、P2是否能够匹配例2——含有变量的谓词公式P1:FATHER(joe,john)∧MAN(joe)P2:FATHER(x,y)∧MAN(x)考察P1、P2的匹配过程第一节知识推理的概念和类型例3——设一个产生式系统包含一条如下规则IF((>animal)isa(>type))∧((child))THEN(

4、gisaparentofrex检查规则的前提部分能否被事实库匹配第一节知识推理的概念和类型四、图搜索的基本概念1、状态图搜索树巡回推销员问题——假设一个推销员要到4个城市去访问，然后回家，不走回头路。问题是寻找一条最短的路径，使得推销员访问过每个城市后回到出发地。ABCD47106105第一节知识推理的概念和类型AABACADABCABDACBACDADBADCABCDABDCACBDACDBADBCADCBABCDA26ABDCA25ACBDA33ACDBE25ADBCA33ADCBA2646107107510555101077106104462、存储方式显式存储——存储全部状态空间隐式存

5、储——只存储与问题有关的部分知识3、隐式图搜索方法运用叙述性知识，给出问题的部分状态描述运用过程性知识，给出生成器函数G(x)——父节点生成子节点的规则运用控制性知识，给出评价函数E(x)——评价新生成的节点，控制继续搜索的方向第一节知识推理的概念和类型4、隐式图搜索的基本过程（1）给定初始状态S0（2）用生成器函数G(x)，由S0出发生成其子节点，检查是否出现目标状态Sg，若出现，则成功（3）若未出现，继续搜索，用评价E(x)对各子节点进行评价，选取最有希望的节点，再用G(x)生成其子节点，再检查是否出现Sg（4）如此逐步搜索，直到找到Sg为止第一节知识推理的概念和类型5、搜索过程的完备性

6、搜索过程是完备的——给定一类可解的状态空间和一个搜索过程A，如对任一S0∈S，搜索过程A总可以发现一条从S0到达Sg∈G的通路，则称搜索过程A对问题类是完备的。搜索过程是可采纳的——若A找到的总是最佳解，则称它是可采纳的，记为A*6、启发式与非启发式搜索过程如果在估计函数E(x)中包含有关于待求解问题的某些先验知识，如解的特性、解的分布规律等，那么搜索过程就能有选择地朝目标节点有效地推进，这时就称该搜索过程A为关于问题类的启发式搜索过程，反之称为非启发式搜索过程第一节知识推理的概念和类型第二节基本搜索策略一、广度优先搜索法1、概念由上到下，逐级生成从

7、左到右，横扫各个节点评价函数E(x)=d(x)——节点x的深度是搜索算法，并且是可采纳的第二节基本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否3、示例——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下