安徽大学高级人工智能说课

第二章知识表示与推理2.1知识表示的一般方法2.2图搜索策略2.3一般搜索与推理技术2.4A*算法2.5消解原理2.6规则演义系统2.7产生式系统2.8系统组织技术8/2/202312.1知识表示的一般方法一般计算机科学数据结构+算法人工智能(知识表示+搜索)+推理8/2/202322.1知识表示的一般方法问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）算符（operator）状态空间方法8/2/202332.1知识表示的一般方法问题规约法大问题化为若干小问题本原问题谓词逻辑法合式公式消解算法(归结)8/2/202342.1知识表示的一般方法语义网络法结点表示概念弧表示关系框架法槽、侧面层次结构框架可以嵌套框架8/2/202352.1知识表示的一般方法剧本场景角色事件过程问题求解的算法8/2/202362.2图搜索策略图搜索控制策略

一种在图中寻找路径的方法。

图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程图8/2/202372.2图搜索策略开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表中，提供返回节点n的指针修改指针方向重排OPEN表失败成功是是否否8/2/202382.3一般搜索与推理技术盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展；估价函数种类：有序搜索、A*算法、AO*算法等8/2/202392.4

A*算法1、为什么需要启发式搜索盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。2、定义进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。8/2/2023102.4

A*算法3、启发式搜索策略 有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalutionfunction)。8/2/2023112.4

A*算法4、估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上

。

f(n)——表示节点n的估价函数值

建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。8/2/2023122.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*算法。当g=0时，A*算法就变为有序搜索算法；h=0时，A*算法就变为等代价搜索算法。8/2/2023132.4

A*算法开始把S放入OPEN表，估价函数f=hOPEN=NIL？选取OPEN表中未设置过的、f值最小的节点BESTNODE放入CLOSED表BESTNODE为目标节点吗？计算g(SUC)=g(BES)+k(BES,SUC)失败成功是否是否扩展BESTNODE，产生后继节点SUCCESSOR建立从SUCCESSOR返回BESTNODE的指针AB

8/2/2023142.4

A*算法SUC∈

OPEN？SUC是OLD的复本,把OLD添加到BESTNODE的后继节点表中g(SUC)<g(OLD)？计算f值是否是否重新确定OLD的父辈节点为BESTNODE，并修正父辈节点的g值和f值，记下g(OLD)把SUCCESSOR放入OPEN表，并加入BESTNODE的后裔表ABSUC=CLOSED？A否是8/2/202315实验1A*算法实验

例子:八数码难题（8-puzzleproblem）1238456712384567（目标状态）规定：牌可以移入邻近的空格，不许斜向移动，也不返回先辈节点。12384567（初始状态）8/2/202316实验1A*算法实验

实验内容：用A*算法求解8数码和15数码难题实验报考要求画出A*算法求解流程图，给出核心程序。画出8数码求解图分析估价函数对搜索算法的影响。分析A*算法的特点。8/2/2023172.5消解原理回顾：

原子公式（atomicformulas）P(x),Q(x,y)

文字—一个原子公式及其否定。～P(x),R(x,y,z) 子句—由文字的析取组成的合适公式。P(x)∨~Q(x,y)

消解—对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。2.5.1子句集的求取步骤：共9步。8/2/202318例子:将下列谓词演算公式化为一个子句集(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}开始：消去蕴涵符号只应用∨和～符号，以～A∨B替换AB。(1)

(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}8/2/202319(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)］｝｝8/2/202320(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))］｝｝8/2/202321把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(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))］｝8/2/202322(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)］8/2/202323消解推理规则消解式的定义

令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。

消解式求法取两个子句，进行析取，然后消去互补对。8/2/202324消解推理规则P ~P∨QQ1、假言推理2、合并P∨Q ~P∨QQ3、重言式P∨Q ~P∨~QTP∨~P

Q∨~Q5、三段论~P∨Q ~Q

∨R~P∨R4、矛盾P ~PF8/2/202325

含有变量的消解式

要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。

含有变量的子句之消解式

例2.1B(x) ～B(x)∨C(x)C(x)8/2/202326

含有变量的消解式

例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.2

P(x)∨Q(x) ～Q[f(y)]

P[f(y)]σ={f(y)/x}8/2/202327

消解反演求解过程消解反演

给出{S}，L否定L，得～L；把～L添加到S中去；把新产生的集合｛～L，S｝化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句例子—储蓄问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱8/2/202328

消解反演求解过程(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)

化为子句形证明：8/2/202329把前提化为子句形：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)[~∨～S(x,y)]}(x)I(x)∧(x)(y)[M(y)∧S(x,y)]8/2/202330反演求解过程从反演树求取答案步骤把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质把一棵根部有NIL的反演树变换为根部带有回答语句的一棵证明树。8/2/202331应用消解反演求解如下问题：无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果约翰在学校里，菲多在哪里呢?x在y:

AT(x,y)用谓词公式表示前提和结论：前提：(x)[AT(JOHN,x)AT(FIDO,x)]AT(JOHN,SCHOOL)结论：(x)AT(FIDO,x)结论的否定：~AT(FIDO,x)8/2/202332化为子句集：~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}8/2/202333

含状态项的回答语句的求取猴子和香蕉问题8/2/202334

含状态项的回答语句的求取{~ONBOX(S0)，AT(box,b,S0)，AT(monkey,a,S0)，~HB(S0)}pushbox(x,S)：在状态S下，猴子把箱子推到水平位置xclimbbox(S)：在状态S下，猴子爬上箱顶grasp(S)：在状态S下，猴子摘到香蕉8/2/202335

含状态项的回答语句的求取(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)要证的结论8/2/202336

含状态项的回答语句的求取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)目标的非：~HB(S)8/2/202337

含状态项的回答语句的求取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)8/2/202338~HB(S5)~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3))~ONBOX(S3)∨~AT(box,c,S3){grasp(S3)/S5}ONBOX(climbbox(S2)){climbbox(S2)/S3}~AT(box,c,climbbox(S2))~AT(box,x,S4)∨AT(box,x,climbbox(S4)){S4/S2,c/x}~ONBOX(S0)~AT(box,c,S4)ONBOX(S1)∨AT(box,x,pushbox(x,S1)){pushbox(x,S1)/S4,c/x}ONBOX(S1){S0/S1}NIL8/2/202339~HB(S5)∨HB(S5)

~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3))HB(grasp(S3))∨~ONBOX(S3)∨~AT(box,c,S3){grasp(S3)/S5}ONBOX(climbbox(S2)){climbbox(S2)/S3}HB(grasp(climbbox(S2)

))∨~AT(box,c,climbbox(S2))~AT(box,x,S4)∨AT(box,x,climbbox(S4)){S4/S2,c/x}~ONBOX(S0)HB(grasp(climbbox(S4)))∨~AT(box,c,S4)ONBOX(S1)∨AT(box,x,pushbox(x,S1)){pushbox(x,S1)/S4,c/x}HB(grasp(climbbox(pushbox(c,S1))))∨

ONBOX(S1){S0/S1}HB(grasp(climbbox(pushbox(c,S0))))8/2/202340实验2子句消解实验

一、实验目的： 理解含有变量的子句如何使用消解规则，掌握子句消解的原理和规则，能熟练进行任意两个子句的消解，了解消解推理的某些常用规则。

二、实验原理： 对子句集进行消解推理，得到相应的结论。为了对含有变量的子句使用消解规则，我们必须找到一个置换，作用于父辈子句使其含有互补文字。消解两个子句时，可能有一个以上的消解式。三、实验条件

硬件：微型计算机。 任选一种流行语言。

8/2/202341实验2子句消解实验

四、实验内容：

编写消解程序。

输入子句，检查消解结果。

根据消解过程理解消解原理和常用规则。

五、实验步骤(2-3人一组)： 1.

语法分析程序，产生文字集合； 2.

两个文字集合进行消解，结果为新的文字集合； 3.

用户界面设计； 4.

分析消解过程，写消解实验报告。（每人）8/2/2023422.6规则演绎系统

定义

基于规则的问题求解系统运用If→Then规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存(黑板)，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。8/2/2023432.6.1规则正向演绎系统定义

正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。

求解过程事实表达式的与或形变换

在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。8/2/2023441.事实表达式的与或形变换例如：(u)(v){Q(v,u)∧~[(R(v)∨P(v))∧S(A,v)]}表示为非蕴涵形式的与或形：{A/u}Q(v,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}2.6.1规则正向演绎系统8/2/2023452.事实表达式的与或图表示Q(v,A)∧{[~R(v)∧~P(v)]∨~S(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)8/2/202346与或图的F规则变换

这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：

LW

式中：L是单文字；W为与或形的唯一公式。下面的证明限定：目标是可以证明的，目标是析取关系2.6.1规则正向演绎系统8/2/202347例如：

(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)8/2/202348[(P∨Q)∧R]∨[S∧(T∨U)]P∨Q(P∨Q)∧RT∨UPQRS∧(T∨U)STU图2.9不含变量的与或图8/2/202349[(P∨Q)∧R]∨[S∧(T∨U)]P∨Q(P∨Q)∧RT∨UPQRS∧(T∨U)STU图2.10应用LW规则得到的与或图SX∧YZXYP∨Q∨X∨ZP∨Q∨Y∨ZR∨X∨ZR∨Y∨Z8/2/202350(A∨B)事实:A∨B规则:AC∧D,BE∧G目标:C∨G(析取)CDCAABBEGG~A∨C~C~G~B∨GA∨B~A~B~BNIL结论：以目标节点作为终止解图时，系统成功终止。8/2/2023512.6.2规则逆向演绎系统定义逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。

求解过程目标表达式的与或形式与或图的B规则变换,WL,L是单文字；W为与或形的公式作为终止条件的事实节点的一致解图8/2/2023522.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)8/2/202353例：

F1:DOG(FIDO)；狗的名字叫Fido F2:~BARKS(FIDO)；Fido不叫的 F3:WAGS-TAIL(FIDO)；Fido摇尾巴 F4:MEOWS(MYRTLE)；猫咪的名字叫Myrtle R1:[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)；猫咪是猫问题：是否存在一只猫和一条狗，使得这只猫不怕这条狗（找到一只不怕狗的猫）？

(x)(y)[CAT(x)∧DOG(y)∧~AFRAID(x,y)]8/2/202354CAT(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/y}{FIDO/y}~BARKS(FIDO)MEOWS(MYRTLE){y/x