安徽大学高级人工智能课件2

人工智能ArtificialIntelligence第二章知识表示与推理2.1知识表示的一般方法2.2图搜索策略2.3一般搜索与推理技术2.4A*算法2.5消解原理2.6规则演义系统2.7产生式系统2.8系统组织技术2019/8/1安徽大学计算机科学与技术学院32.1知识表示的一般方法一般计算机科学数据结构+算法人工智能(知识表示+搜索)+推理2019/8/1安徽大学计算机科学与技术学院42.1知识表示的一般方法问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）算符（operator）状态空间方法2019/8/1安徽大学计算机科学与技术学院52.1知识表示的一般方法问题规约法大问题化为若干小问题本原问题谓词逻辑法合式公式消解算法(归结)2019/8/1安徽大学计算机科学与技术学院62.1知识表示的一般方法语义网络法结点表示概念弧表示关系框架法槽、侧面层次结构框架可以嵌套框架2019/8/1安徽大学计算机科学与技术学院72.1知识表示的一般方法剧本场景角色事件过程问题求解的算法2019/8/1安徽大学计算机科学与技术学院82.2图搜索策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程图2019/8/1安徽大学计算机科学与技术学院92.2图搜索策略开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表中，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否2019/8/1安徽大学计算机科学与技术学院102.3一般搜索与推理技术盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展；估价函数种类：有序搜索、A*算法、AO*算法等2019/8/1安徽大学计算机科学与技术学院112.4A*算法1、为什么需要启发式搜索盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。2、定义进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。2019/8/1安徽大学计算机科学与技术学院122.4A*算法3、启发式搜索策略有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalutionfunction)。2019/8/1安徽大学计算机科学与技术学院132.4A*算法4、估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。2019/8/1安徽大学计算机科学与技术学院142.4A*算法估价函数的定义：对节点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*算法。当g=0时，A*算法就变为有序搜索算法；h=0时，A*算法就变为等代价搜索算法。2019/8/1安徽大学计算机科学与技术学院152.4A*算法开始把S放入OPEN表，估价函数f=hOPEN=NIL？选取OPEN表中未设置过的、f值最小的节点BESTNODE放入CLOSED表BESTNODE为目标节点吗？计算g(SUC)=g(BES)+k(BES,SUC)失败成功是否是否扩展BESTNODE，产生后继节点SUCCESSOR建立从SUCCESSOR返回BESTNODE的指针AB2019/8/1安徽大学计算机科学与技术学院162.4A*算法SUC∈OPEN？SUC是OLD的复本,把OLD添加到BESTNODE的后继节点表中g(SUC)g(OLD)？计算f值是否是否重新确定OLD的父辈节点为BESTNODE，并修正父辈节点的g值和f值，记下g(OLD)把SUCCESSOR放入OPEN表，并加入BESTNODE的后裔表ABSUC=CLOSED？A否是2019/8/1安徽大学计算机科学与技术学院17实验1A*算法实验例子:八数码难题（8-puzzleproblem）1238456712384567（目标状态）规定：牌可以移入邻近的空格，不许斜向移动，也不返回先辈节点。12384567（初始状态）2019/8/1安徽大学计算机科学与技术学院18实验1A*算法实验实验内容：用A*算法求解8数码和15数码难题实验报考要求画出A*算法求解流程图，给出核心程序。画出8数码求解图分析估价函数对搜索算法的影响。分析A*算法的特点。2019/8/1安徽大学计算机科学与技术学院192.5消解原理回顾：原子公式（atomicformulas）P(x),Q(x,y)文字—一个原子公式及其否定。～P(x),R(x,y,z)子句—由文字的析取组成的合适公式。P(x)∨~Q(x,y)消解—对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。2.5.1子句集的求取步骤：共9步。2019/8/1安徽大学计算机科学与技术学院20例子:将下列谓词演算公式化为一个子句集(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}开始：(1)消去蕴涵符号只应用∨和～符号，以～A∨B替换AB。(1)(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}2019/8/1安徽大学计算机科学与技术学院21(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)］｝｝2019/8/1安徽大学计算机科学与技术学院22(4)消去存在量词以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形={前缀}{母式}全称量词串无量词公式(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))］｝｝2019/8/1安徽大学计算机科学与技术学院23(6)把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(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/8/1安徽大学计算机科学与技术学院24(8)消去连词符号∧用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。(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)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］2019/8/1安徽大学计算机科学与技术学院252.5.2消解推理规则消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。消解式求法取两个子句，进行析取，然后消去互补对。2019/8/1安徽大学计算机科学与技术学院262.5.2消解推理规则P~P∨QQ1、假言推理2、合并P∨Q~P∨QQ3、重言式P∨Q~P∨~QTP∨~PQ∨~Q5、三段论~P∨Q~Q∨R~P∨R4、矛盾P~PF2019/8/1安徽大学计算机科学与技术学院272.5.3含有变量的消解式要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。含有变量的子句之消解式例2.1B(x)～B(x)∨C(x)C(x)2019/8/1安徽大学计算机科学与技术学院282.5.3含有变量的消解式例2.3P[x,f(y)]∨Q(x)∨R[f(a),y]～P[f(f(a)),z]∨R(z,w)Q[f(f(a))]∨R(f(a),y)∨R(f(y),w)σ={f(f(a))/x,f(y)/z}例2.2P(x)∨Q(x)～Q[f(y)]P[f(y)]σ={f(y)/x}2019/8/1安徽大学计算机科学与技术学院292.5.4消解反演求解过程消解反演给出{S}，L否定L，得～L；把～L添加到S中去；把新产生的集合｛～L，S｝化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句例子—储蓄问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱2019/8/1安徽大学计算机科学与技术学院302.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)(I(y)∧E(x,y))]结论：～(x)I(x)(x)(y)[M(y)～S(x,y)](3)化为子句形证明：2019/8/1安徽大学计算机科学与技术学院31把前提化为子句形：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)/z～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}～S(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(x)∨(x)(y)