高级人工智能课件_1

上传人:F****n 文档编号:88061421 上传时间:2019-04-18 格式:PPT 页数:44 大小:392.50KB
返回 下载 相关 举报
高级人工智能课件_1_第1页
第1页 / 共44页
高级人工智能课件_1_第2页
第2页 / 共44页
高级人工智能课件_1_第3页
第3页 / 共44页
高级人工智能课件_1_第4页
第4页 / 共44页
高级人工智能课件_1_第5页
第5页 / 共44页
点击查看更多>>
资源描述

《高级人工智能课件_1》由会员分享,可在线阅读,更多相关《高级人工智能课件_1(44页珍藏版)》请在金锄头文库上搜索。

1、人工智能,Artificial Intelligence,主讲 樊建聪 信息科学与工程学院,第二章 知识表示与推理,2.1 知识表示的一般方法 2.2 图搜索策略 2.3 一般搜索与推理技术 2.4 A*算法 2.5 消解原理,2019/4/18,3,2.1 知识表示的一般方法,一般计算机科学 数据结构 + 算法 人工智能 (知识表示+搜索) + 推理,2019/4/18,4,2.1 知识表示的一般方法,问题求解技术主要是两个方面: 问题的表示 求解的方法 状态空间法 状态(state) 算符(operator) 状态空间方法,2019/4/18,5,2.1 知识表示的一般方法,问题规约法 大

2、问题化为若干小问题 本原问题 谓词逻辑法 合式公式 消解算法(归结),2019/4/18,6,2.1 知识表示的一般方法,语义网络法 结点表示概念 弧表示关系 框架法 槽、侧面层次结构 框架可以嵌套框架,2019/4/18,7,2.1 知识表示的一般方法,剧本 场景 角色 事件 过程 问题求解的算法,2019/4/18,8,2.2 图搜索策略,图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态,每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。 图搜索过

3、程图,2019/4/18,9,2.2 图搜索策略,2019/4/18,10,2.3 一般搜索与推理技术,盲目搜索 特点:不需重排OPEN表 种类:宽度优先、深度优先、等代价搜索等。,启发式搜索 特点:重排OPEN表,选择最有希望的节点加以扩展;估价函数 种类:有序搜索、A*算法、 AO*算法等,2019/4/18,11,2.4 A*算法,1、为什么需要启发式搜索 盲目搜索效率低,耗费过多的计算空间与时间,这是组合爆炸的一种表现形式。 2、定义 进行搜索技术一般需要某些有关具体问题领域的特性的信息,把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。,2019/4/18,12,2.

4、4 A*算法,3、启发式搜索策略 有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。 应用这种排序过程,需要某些估算节点“希望”的量度,这种量度叫做估价函数(evaluation function)。,2019/4/18,13,2.4 A*算法,4、估价函数 为获得某些节点“希望”的启发信息,提供一个评定侯选扩展节点的方法,以便确定哪个节点最有可能在通向目标的最佳路径上 。 f(n)表示节点n的估价函数值,2019/4/18,14,2.4 A*算法,估价函数的定义: 对节点n定义f*(n)=g*(n)+h*(n

5、) ,表示从S开始约束通过节点n的一条最佳路径的代价。 希望估价函数f 定义为: f(n)=g(n)+h(n) g是g*的估计 ,h是h*的估计,2019/4/18,15,2.4 A*算法,A*算法的定义: 定义1 在GRAPHSEARCH过程中,如果重排OPEN表是依据f(x)=g(x)+h(x)进行的,则称该过程为A算法。 定义2 在A算法中,如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界,它表示某种偏于保守的估计。 定义3 采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。当g=0时,A*算法就变为有序搜索算法;h=0时,A*算法就变为等代价搜索算法。,

6、2019/4/18,16,2.4 A*算法,2019/4/18,17,2.4 A*算法,2019/4/18,18,实验1 A*算法实验,例子:八数码难题(8-puzzle problem),规定:牌可以移入邻近的空格,不许斜向移动,也不返回先辈节点。,2019/4/18,19,实验1 A*算法实验,实验内容: 用A*算法求解8数码和15数码难题 实验报告要求 画出A*算法求解流程图,给出核心程序。 画出8数码求解图 分析估价函数对搜索算法的影响。 分析A*算法的特点。,2019/4/18,20,2.5 消解原理,回顾: 原子公式(atomic formulas) P(x), Q(x,y) 文字

7、一个原子公式及其否定。 P(x), R(x,y,z) 子句由文字的析取组成的合适公式。 P(x)Q(x,y) 消解对谓词演算公式进行分解和化简,消去一些符号,以求得导出子句。,2019/4/18,21,例子:,将下列谓词演算公式化为一个子句集 (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),开始: 消去蕴涵符号 只应用和符号,以AB替换AB。,(1) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),2019/4/18,22,(2) 减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上,并反复应用狄摩根定律。 (3) 对变量标准化 对哑元(虚构

8、变量)改名,以保证每个量词有其自己唯一的哑元。,(2) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),(3) (x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w),2019/4/18,23,(4) 消去存在量词 以Skolem函数代替存在量词内的约束变量,然后消去存在量词 化为前束形 把所有全称量词移到公式的左边,并使每个量词的辖域包括这个量词后面公式的整个部分。 前束形=前缀 母式 全称量词串 无量词公式,(4) (x)P(x)(y)P(y)P(f(x,y)Q(x,g(x))P(g(x) 式中,w=g(x)为一Skolem函数。,(5) (x)(y

9、)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x),2019/4/18,24,把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。 (7) 消去全称量词 所有余下的量词均被全称量词量化了。消去前缀,即消去明显出现的全称量词。,(6) (x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),(7) P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),2019/4/18,25,(8) 消去连词符号 用A,B代替(AB),消去符号。最后得到一个有限集,其中每个公式是文字的析取。 (9

10、) 更换变量名称 可以更换变量符号的名称,使一个变量符号不出现在一个以上的子句中。,(8) P(x)P(y)P(f(x,y) P(x)Q(x,g(x) P(x)P(g(x),(9) P(x1)P(y)Pf(x1,y) P(x2)Qx2,g(x2) P(x3)Pg(x3),2019/4/18,26,2.5.2 消解推理规则,消解式的定义 令L1,L2为两任意原子公式;L1和L2具有相同的谓词符号,但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一,那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。,消解式求法,取两个子句,进行析取,然后消去互补对。

11、,2019/4/18,27,2.5.2 消解推理规则,2019/4/18,28,2.5.3 含有变量的消解式,2019/4/18,29,2.5.3 含有变量的消解式,2019/4/18,30,2.5.4 消解反演求解过程,消解反演 给出S,L 否定L,得L; 把L添加到S中去; 把新产生的集合L,S化成子句集; 应用消解原理,力图推导出一个表示矛盾的空子句,例子储蓄问题 前提:每个储蓄钱的人都获得利息。 结论:如果没有利息,那么就没有人去储蓄钱,2019/4/18,31,2.5.4 消解反演求解过程,(1)规定原子公式: S(x,y) 表示 “x储蓄y” M(x) 表示 “x是钱” I(x)

12、表示 “x是利息” E(x,y) 表示 “x获得y”,(2)用谓词公式表示前提和结论: 前提: (x)(y)(S(x,y)M(y)(y)(I(y)E(x,y) 结论: (x)I(x) (x)(y)M(y) S(x,y),(3) 化为子句形,证明:,2019/4/18,32,把前提化为子句形: 1) S(x,y)M(y)I(f(x) 2) S(x,y)M(y)E(x,f(x),把结论化为子句形: 3) I(z) 4) S(a,b) 5) M(b),(4) 消解反演求NIL,图3.12 储蓄问题反演树,2019/4/18,33,反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添

13、加到目标公式否定之否定的子句中去。 按照反演树,执行和以前相同的消解,直至在根部得到某个子句止。 用根部的子句作为一个回答语句。 实质 把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。,2019/4/18,34,应用消解反演求解如下问题: 无论约翰(John)到哪里去,菲多(Fido)也就去那里,那么如果约翰在学校里,菲多在哪里呢?,x在y : AT(x,y) 用谓词公式表示前提和结论: 前提: (x)AT(JOHN,x)AT(FIDO,x) AT(JOHN,SCHOOL) 结论:(x)AT(FIDO,x) 结论的否定:AT(FIDO,x),2019/4/18,35,化为子句集

14、:AT(JOHN,x)AT(FIDO,x) AT(JOHN,SCHOOL) AT(FIDO,x),AT(JOHN,y)AT(FIDO,y),AT(FIDO,x),AT(JOHN,x),x/y,AT(JOHN,SCHOOL),NIL,SCHOOL/x,AT(JOHN,y)AT(FIDO,y),AT(FIDO,x)AT(FIDO,x),AT(JOHN,x)AT(FIDO,x),x/y,AT(JOHN,SCHOOL),AT(FIDO,SCHOOL),SCHOOL/x,2019/4/18,36,2.5.5 含状态项的回答语句的求取,猴子和香蕉问题,2019/4/18,37,2.5.5 含状态项的回答语

15、句的求取,ONBOX(S0),AT(box,b,S0), AT(monkey,a,S0),HB(S0),pushbox(x,S):在状态S下,猴子把箱子推到水平位置x climbbox(S):在状态S下,猴子爬上箱顶 grasp(S):在状态S下,猴子摘到香蕉,2019/4/18,38,2.5.5 含状态项的回答语句的求取,(x) (S) ONBOX(S) AT(box,x,pushbox(x,S) (S)ONBOX(climbbox(S) (S)ONBOX(S) AT(box,c,S) HB(grasp(S) (x) (S)AT(box,x,S) AT(box,x,climbbox(S) ONBOX(S0) (S) HB(S) 要证的结论,2019/4/18,39,2.5.5 含状态项的回答语句的求取,ONBOX(S) AT(box,x,pushbox(x,S) ONBOX(climbbox(S) ONBOX(S)AT(box

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > PPT模板库 > PPT素材/模板

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号