安徽大学高级人工智能

1、人工智能Artificial Intelligence9/4/20221安徽大学 计算机科学与技术学院第二章 知识表示与推理2.1 知识表示的一般方法2.2 图搜索策略2.3 一般搜索与推理技术2.4 A*算法2.5 消解原理2.6 规则演义系统2.7 产生式系统2.8 系统组织技术9/4/20222安徽大学 计算机科学与技术学院2.1 知识表示的一般方法一般计算机科学数据结构 + 算法人工智能(知识表示+搜索) + 推理9/4/20223安徽大学 计算机科学与技术学院2.1 知识表示的一般方法问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）算符（operator）

2、状态空间方法9/4/20224安徽大学 计算机科学与技术学院2.1 知识表示的一般方法问题规约法大问题化为若干小问题本原问题谓词逻辑法合式公式消解算法(归结)9/4/20225安徽大学 计算机科学与技术学院2.1 知识表示的一般方法语义网络法结点表示概念弧表示关系框架法槽、侧面层次结构框架可以嵌套框架9/4/20226安徽大学 计算机科学与技术学院2.1 知识表示的一般方法剧本场景角色事件过程问题求解的算法9/4/20227安徽大学 计算机科学与技术学院2.2 图搜索策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又

3、分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程图9/4/20228安徽大学 计算机科学与技术学院2.2 图搜索策略开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表中，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否9/4/20229安徽大学 计算机科学与技术学院2.3 一般搜索与推理技术盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展；估

4、价函数种类：有序搜索、A*算法、 AO*算法等9/4/202210安徽大学 计算机科学与技术学院2.4 A*算法1、为什么需要启发式搜索 盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。2、定义 进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。9/4/202211安徽大学 计算机科学与技术学院2.4 A*算法3、启发式搜索策略 有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被

5、认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。9/4/202212安徽大学 计算机科学与技术学院2.4 A*算法4、估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。 f(n)表示节点n的估价函数值 建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。9

6、/4/202213安徽大学 计算机科学与技术学院2.4 A*算法估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n) g是g*的估计 ，h是h*的估计A*算法的定义：定义1 在GRAPHSEARCH过程中，如果第8步的重排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*算法。当

7、g=0时，A*算法就变为有序搜索算法；h=0时，A*算法就变为等代价搜索算法。 9/4/202214安徽大学 计算机科学与技术学院2.4 A*算法开始把S放入OPEN表，估价函数 f =hOPEN=NIL？选取OPEN表中未设置过的、f值最小的节点BESTNODE放入CLOSED表BESTNODE为目标节点吗？计算g(SUC)=g(BES)+k(BES,SUC)失败成功是否是否扩展BESTNODE ，产生后继节点SUCCESSOR建立从SUCCESSOR返回BESTNODE的指针AB 9/4/202215安徽大学 计算机科学与技术学院2.4 A*算法SUC OPEN？SUC是OLD的复本,把O

8、LD添加到BESTNODE的后继节点表中g(SUC)g(OLD)？计算f值是否是否重新确定OLD的父辈节点为BESTNODE ，并修正父辈节点的g值和f值，记下g(OLD)把SUCCESSOR放入OPEN表，并加入BESTNODE的后裔表ABSUC=CLOSED？A否是9/4/202216安徽大学 计算机科学与技术学院实验1 A*算法实验 例子:八数码难题（8-puzzle problem） 1238456712384567（目标状态）规定：牌可以移入邻近的空格，不许斜向移动，也不返回先辈节点。12384567（初始状态）9/4/202217安徽大学 计算机科学与技术学院实验1 A*算法实验

9、实验内容：用A*算法求解8数码和15数码难题实验报考要求画出A*算法求解流程图，给出核心程序。画出8数码求解图分析估价函数对搜索算法的影响。分析A*算法的特点。9/4/202218安徽大学 计算机科学与技术学院2.5 消解原理回顾：原子公式（atomic formulas） P(x), Q(x,y)文字一个原子公式及其否定。 P(x), R(x,y,z)子句由文字的析取组成的合适公式。 P(x)Q(x,y)消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。2.5.1 子句集的求取 步骤：共9步。9/4/202219安徽大学 计算机科学与技术学院 例子: 将下列谓词演算公式化为一个

10、子句集(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)9/4/202220安徽大学 计算机科学与技术学院(2) 减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3) 对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。(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)9/4/202221安

11、徽大学 计算机科学与技术学院(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)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)9/4/202222安徽大学 计算机科学与技术学院把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7

12、) 消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。(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)9/4/202223安徽大学 计算机科学与技术学院(8) 消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9) 更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。(8) P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9) P(

13、x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)9/4/202224安徽大学 计算机科学与技术学院2.5.2 消解推理规则消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。 消解式求法取两个子句，进行析取，然后消去互补对。9/4/202225安徽大学 计算机科学与技术学院2.5.2 消解推理规则PP QQ1、假言推理2、合并P Q P QQ3、重言式P Q P QTP P QQ5、三段论 P

14、Q Q RP R4、矛盾PP F9/4/202226安徽大学 计算机科学与技术学院2.5.3 含有变量的消解式 要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。 含有变量的子句之消解式 例2.1 B(x) B(x)C(x) C(x)9/4/202227安徽大学 计算机科学与技术学院2.5.3 含有变量的消解式 例2.3Px,f(y)Q(x)Rf(a),y Pf (f(a),zR(z,w)Q f (f(a) R(f(a),y) R(f(y),w) =f(f(a)/x,f(y)/z 例2.2 P(x)Q(x) Qf(y) P f (y) =f(y)/

15、x9/4/202228安徽大学 计算机科学与技术学院2.5.4 消解反演求解过程消解反演 给出S，L否定L，得L；把L添加到S中去；把新产生的集合L，S化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句 例子储蓄问题 前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱9/4/202229安徽大学 计算机科学与技术学院2.5.4 消解反演求解过程(1）规定原子公式： S(x,y) 表示 “x储蓄y” M(x) 表示 “x是钱” I(x) 表示 “x是利息” E(x，y) 表示 “x获得y”(2）用谓词公式表示前提和结论：前提：(x)(y)(S(x,y)M(y)(y)

16、(I(y)E(x,y)结论：(x)I(x) (x)(y)M(y) S(x,y)(3) 化为子句形证明：9/4/202230安徽大学 计算机科学与技术学院把前提化为子句形：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 储蓄问题反演树子句（1）子句（3）f (x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句（6）(x)I(x) (x)(y)M(y)S(x,y)(x)I(x)(x)(y)M(y)S(x,y)否定： ( x)I(

17、x)(x)(y)S(x,y)(x)I(x) (x)(y)M(y)S(x,y)9/4/202231安徽大学 计算机科学与技术学院反演求解过程从反演树求取答案步骤把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。9/4/202232安徽大学 计算机科学与技术学院应用消解反演求解如下问题：无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果约翰在学校里，菲多在哪里呢?x在y : AT(x,y)用谓词公式表示前提和

18、结论：前提：(x)AT(JOHN,x)AT(FIDO,x)AT(JOHN,SCHOOL)结论：(x)AT(FIDO,x)结论的否定：AT(FIDO,x)9/4/202233安徽大学 计算机科学与技术学院化为子句集：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/yAT(JOHN,SCHOOL)NILSCHOOL/xAT(JOHN,y)AT(FIDO,y)AT(FIDO,x)AT(FIDO,x)AT(JOHN,x)AT(FIDO,x)x/yAT(JOHN,SCHOOL)A

19、T(FIDO,SCHOOL)SCHOOL/x9/4/202234安徽大学 计算机科学与技术学院2.5.5 含状态项的回答语句的求取猴子和香蕉问题9/4/202235安徽大学 计算机科学与技术学院2.5.5 含状态项的回答语句的求取ONBOX(S0)，AT(box,b,S0)， AT(monkey,a,S0)，HB(S0)pushbox(x,S)：在状态S下，猴子把箱子推到水平位置xclimbbox(S)：在状态S下，猴子爬上箱顶grasp(S)：在状态S下，猴子摘到香蕉9/4/202236安徽大学 计算机科学与技术学院2.5.5 含状态项的回答语句的求取(x) (S) ONBOX(S) AT(

20、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) 要证的结论9/4/202237安徽大学 计算机科学与技术学院2.5.5 含状态项的回答语句的求取ONBOX(S) AT(box,x,pushbox(x,S)ONBOX(climbbox(S)ONBOX(S)AT(box,c,S)HB(grasp(S) AT(box,x,S)AT(box,x,climbbox(S) ONBOX(S0)

21、目标的非：HB(S)9/4/202238安徽大学 计算机科学与技术学院2.5.5 含状态项的回答语句的求取ONBOX(S1) AT(box,x,pushbox(x,S1)ONBOX(climbbox(S2)ONBOX(S3)AT(box,c,S3)HB(grasp(S3) AT(box,x,S4)AT(box,x,climbbox(S4) ONBOX(S0)目标的非：HB(S5)9/4/202239安徽大学 计算机科学与技术学院HB(S5)ONBOX(S3)AT(box,c,S3)HB(grasp(S3)ONBOX(S3)AT(box,c,S3)grasp(S3)/S5ONBOX(climbb

22、ox(S2)climbbox(S2) /S3AT(box,c, climbbox(S2)AT(box,x,S4)AT(box,x,climbbox(S4)S4/S2,c/xONBOX(S0)AT(box,c,S4)ONBOX(S1) AT(box,x,pushbox(x,S1)pushbox(x,S1)/S4,c/xONBOX(S1)S0/S1NIL9/4/202240安徽大学 计算机科学与技术学院HB(S5) HB(S5) ONBOX(S3)AT(box,c,S3)HB(grasp(S3)HB(grasp(S3)ONBOX(S3)AT(box,c,S3)grasp(S3)/S5ONBOX(c

23、limbbox(S2)climbbox(S2) /S3HB(grasp(climbbox(S2) )AT(box,c, climbbox(S2)AT(box,x,S4)AT(box,x,climbbox(S4)S4/S2,c/xONBOX(S0)HB(grasp(climbbox(S4) AT(box,c,S4)ONBOX(S1) AT(box,x,pushbox(x,S1)pushbox(x,S1)/S4,c/xHB(grasp(climbbox(pushbox(c,S1) ONBOX(S1)S0/S1HB(grasp(climbbox(pushbox(c,S0)9/4/202241安徽大学

24、 计算机科学与技术学院实验2 子句消解实验 一、实验目的：理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进行任意两个子句的消解，了解消解推理的某些常用规则。二、实验原理：对子句集进行消解推理，得到相应的结论。为了对含有变量的子句使用消解规则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。消解两个子句时，可能有一个以上的消解式 。三、实验条件 硬件：微型计算机。任选一种流行语言。 9/4/202242安徽大学 计算机科学与技术学院实验2 子句消解实验 四、实验内容： 编写消解程序。 输入子句，检查消解结果。 根据消解过程理解消解原理和常用规则。 五、实验步骤(2-3

25、人一组)：1.语法分析程序，产生文字集合；2.两个文字集合进行消解，结果为新的文字集合；3. 用户界面设计；4. 分析消解过程，写消解实验报告。（每人）9/4/202243安徽大学 计算机科学与技术学院2.6 规则演绎系统 定义 基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存(黑板)，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。 9/4/202244安徽大学 计算机科学与技术学院2.6.1 规则正向

26、演绎系统定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。 求解过程事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。9/4/202245安徽大学 计算机科学与技术学院1. 事实表达式的与或形变换例如：(u) (v) Q(v,u) (R(v) P(v) S(A,v)表示为非蕴涵形式的与或形：A/uQ(v,A)R(v)P(v)S(A,v)2.6.1 规则正向演绎系统9/4/202246安徽大学 计算机科学与技术学院2. 事实表达式的与或图表示Q(v,A)R(v)P(v)S

27、(A,v)Q(v,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)图2.8 一个事实表达式的与或树表示子句集：Q(v,A)R(v)S(A,v)P(v)S(A,v)换名：Q(w,A)R(v)S(A,v)P(x)S(A,x)9/4/202247安徽大学 计算机科学与技术学院与或图的F规则变换 这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式： L W 式中：L是单文字；W为与或形的唯一公式。下面的证明限定：目标是可以证明的，目标是析取关系2.6.1 规则正向演绎系统9/4/202248安徽大学 计算机科学与技术学

28、院例如： (x)(y)(z)P(x,y,z) (u) Q(x,u)1)暂时消去蕴涵符号： (x)(y)(z)P(x,y,z) (u) Q(x,u)2)减小否定符号的辖域： (x) (y)(z) P(x,y,z) (u) Q(x,u)3)进行Skolem标准化： (x) (y) P(x,y,f(x,y) (u) Q(x,u)4)换名并消去全称量词： P(x,y,f(x,y) Q(x,u)5)恢复蕴涵式： P(x,y,f(x,y) Q(x,u)9/4/202249安徽大学 计算机科学与技术学院(PQ)R S(TU)PQ(PQ)RTUPQRS(TU)STU图2.9 不含变量的与或图9/4/20225

29、0安徽大学 计算机科学与技术学院(PQ)R S(TU)PQ(PQ)RTUPQRS(TU)STU图2.10 应用L W规则得到的与或图SXYZXYP Q X ZP Q Y ZR X ZR Y Z9/4/202251安徽大学 计算机科学与技术学院(AB)事实: AB 规则:A CD, B EG 目标: CG(析取)CDCAABBEGGACCGBGABABBNIL结论：以目标节点作为终止解图时，系统成功终止。9/4/202252安徽大学 计算机科学与技术学院2.6.2 规则逆向演绎系统定义 逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。 求解过程目标表达式的

30、与或形式与或图的B规则变换, WL,L是单文字；W为与或形的公式作为终止条件的事实节点的一致解图9/4/202253安徽大学 计算机科学与技术学院2.6.2 规则逆向演绎系统例如： (y)(x)P(x)Q(x,y) P(x) S(y)化成与或形：P(f(y) Q(f(y),y) P(f(y) S(y)P(f(y) Q(f(y),y) P(f(y)S(y)Q(f(y),y) P(f(y) S(y)P(f(y)P(f(y)S(y)Q(f(y),y)S(y)P(f(y)目标子句是文字的合取：P(f(z)Q(f(y),y) P(f(y)Q(f(x),x) S(x)9/4/202254安徽大学 计算机科

31、学与技术学院例： F1: DOG(FIDO)；狗的名字叫FidoF2: BARKS(FIDO)；Fido不叫的F3: WAGS-TAIL (FIDO)；Fido摇尾巴F4: MEOWS(MYRTLE) ；猫咪的名字叫MyrtleR1: WAGS-TAIL(x1)DOG(x1)FRIENDLY(x1)；摇尾巴的狗是温顺的狗R2: FRIENDLY(x2)BARKS(x2)AFRAID(y2,x2)；温顺而不叫的东西是不值得害怕的R3: DOG(x3) ANIMAL(x3)；狗是动物R4: CAT(x4) ANIMAL(x4)；猫是动物R5: MEOWS(x5) CAT(x5)；猫咪是猫问题：是否

32、存在一只猫和一条狗，使得这只猫不怕这条狗（找到一只不怕狗的猫）？(x) (y)CAT(x)DOG(y)AFRAID(x,y)9/4/202255安徽大学 计算机科学与技术学院CAT(x)DOG(y)AFRAID(x,y)CAT(x)DOG(y)AFRAID(x,y)WAGS-TAIL (FIDO)DOG(FIDO)DOG(y)AFRAID(y2,x2)FRIENDLY(y)AFRAID(x,y)WAGS-TAIL (y)FIDO/yFIDO/yBARKS(FIDO)MEOWS(MYRTLE)y/x1FIDO/yMYRTLE/xR1DOG(FIDO)FIDO/yBARKS(y)x/y2,y/x2R2MEOWS(x)CAT(x5)x/x5R59/4/202256安徽大学 计算机科学与技术学院 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统