人工智能第二章

教学内容：本章讨论了知识表示和知识推理的一般方法。以逻辑为基础的各种知识表示方法在本章中得到应用和发展。图示法发展为图搜索策略；谓词演算是公式法的代表，发展为消解原理和消解反演过程；陈述式表示则发展为规则演绎系统和产生式系统等。 

教学重点：1．简单介绍知识表示的一般方法有哪些；

2．图搜索策略的定义以及几种搜索策略；

3．一般搜索与推理技术的简单介绍，主要讨论A*算法的定义及算法过程；

4．消解原理的介绍；

5．规则演绎系统的解题过程学习；

6.产生式系统的推理过程；

7.简要介绍系统组织技术

教学难点：

1．A*算法的过程；

2．消解原理的规则；

3．产生式系统的推理过程；

教学方法：课堂教学为主，充分利用网络课程中的多媒体素材来表示抽象概念。

教学要求：重点掌握知识搜索中A*算法、规则演绎系统和产生式系统。

2.1  知识表示的一般方法

教学内容：本小节主要介绍目前一般的知识表示方法及其定义。    

教学重点：知识表示方法的介绍，对简单问题采用何种知识表示方法。

教学难点：对复杂问题采用多种方法混合表示。

教学方法：课堂讲授为主。

教学要求：在掌握知识表示方法的基础上 对不同问题用不同的知识表示方法进行解决。

⏹一般计算机科学

⏹数据结构 + 算法

⏹人工智能

⏹(知识表示+搜索) + 推理

⏹问题求解技术主要是两个方面：

⏹问题的表示

⏹求解的方法

⏹状态空间法

⏹状态（state）

⏹算符（operator）

⏹状态空间方法

⏹问题规约法

⏹大问题化为若干小问题

⏹本原问题

⏹谓词逻辑法

⏹合式公式

⏹消解算法(归结)

⏹语义网络法

⏹结点表示概念

⏹弧表示关系

⏹框架法

⏹槽、侧面层次结构

⏹框架可以嵌套框架

⏹剧本

⏹场景

⏹角色

⏹事件

⏹过程

⏹问题求解的算法

2.2图搜索策略

教学内容：本小节主要介绍图搜索的一般过程以及无信息搜索和启发式搜索的区别。

教学重点：图搜索的一般过程。

教学难点：图搜索的一般过程，其中open表、closed表的定义及意义。

教学方法：课堂讲授为主。

教学要求：掌握图搜索的一般过程。

⏹图搜索控制策略

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

图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。

⏹图搜索过程图

2.3一般搜索与推理技术

教学内容：本小节主要介绍启发式搜索的分类以及启发式搜索和盲目搜索的区别。

教学重点：比较有效的搜索方法规则演绎系统和产生式系统。

教学难点：对有效搜索算法名称的理解。

教学方法：课堂讲授为主。

教学要求：掌握几种搜索方法的名称。

盲目搜索

⏹特点：不需重排OPEN表

⏹种类：宽度优先、深度优先、等代价搜索等。

启发式搜索

⏹特点：重排OPEN表，选择最有希望的节点加以扩展；估价函数

⏹种类：有序搜索、A*算法、 AO*算法等

2.4A*算法

教学内容：本小节主要介绍A*算法的定义和过程。    

教学重点：A*算法的过程。

教学难点：A*算法中几种表的定义及用途。

教学方法：课堂讲授为主。

教学要求：掌握A*算法的整个流程。

1、为什么需要启发式搜索

盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。

2、定义

进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。

3、启发式搜索策略

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

4、估价函数

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

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

建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。

⏹估价函数的定义：

对节点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*算法就变为等代价搜索算法。 

实验1   A*算法实验 

例子:八数码难题（8-puzzle problem） 

⏹实验内容：

⏹用A*算法求解8数码和15数码难题

⏹实验报考要求

⏹画出A*算法求解流程图，给出核心程序。

⏹画出8数码求解图

⏹分析估价函数对搜索算法的影响。

⏹分析A*算法的特点。

2.5 消解原理

教学内容：本小节主要介绍消解式的定义和消解推理过程。    

教学重点：消解推理的过程。

教学难点：含状态项的回答语句的获取。

教学方法：课堂讲授为主。

教学要求：掌握消解原理的整个推理过程。

回顾：

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

文字—一个原子公式及其否定    ～P(x),  R(x,y,z)

子句—由文字的析取组成的合适公式  P(x)∨~Q(x,y)

消解—对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。

2.5.1 子句集的求取

步骤：共9步。

例子: 将下列谓词演算公式化为一个子句集

(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}

开始：

(1) 消去蕴涵符号

只应用∨和～符号，以～A∨B替换AB。

(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}

(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)］｝｝

(4) 消去存在量词

以Skolem函数代替存在量词内的约束变量，然后消去存在量词

(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))］｝｝

（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) 消去连词符号∧

 用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取。

～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)］

2.5.2消解推理规则

消解式的定义：

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

消解式求法：    

取两个子句，进行析取，然后消去互补对。

1、假言推理

2、合并

3、重言式

4、矛盾

5、三段论

2.5.3含有变量的消解式

含有变量的子句之消解式

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

例2.1

例2.2

例2.3

2.5.4消解反演求解过程

消解反演：

给出{S}，L

否定L，得～L；

把～L添加到S中去；

把新产生的集合｛～L，S｝化成子句集；

应用消解原理，力图推导出一个表示矛盾的空子句

例子—储蓄问题

    前提：每个储蓄钱的人都获得利息。

    结论：如果没有利息，那么就没有人去储蓄钱

证明：

(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) 化为子句形

把前提化为子句形：

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

～(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)]

反演求解过程

1)从反演树求取答案步骤

2)把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。

3)按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。

4)用根部的子句作为一个回答语句。

实质

把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。

应用消解反演求解如下问题：

无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果约翰在学校里，菲多在哪里呢?

x在y : AT(x,y)

用谓词公式表示前提和结论：

前提：(x)[AT(JOHN,x)AT(FIDO,x)]

AT(JOHN,SCHOOL)

结论：(x)AT(FIDO,x)

结论的否定：~AT(FIDO,x)

化为子句集：~AT(JOHN,x)∨AT(FIDO,x)   AT(JOHN,SCHOOL)     ~AT(FIDO,x)

~AT(JOHN,y)∨AT(FIDO,y)

~AT(FIDO,x)

2.5.5含状态项的回答语句的求取

猴子和香蕉问题

{~ONBOX(S0)，AT(box,b,S0)， AT(monkey,a,S0)，~HB(S0)}

pushbox(x,S)：在状态S下，猴子把箱子推到水平位置x

climbbox(S)：在状态S下，猴子爬上箱顶

grasp(S)：在状态S下，猴子摘到香蕉

(1)(x) (S) {~ ONBOX(S)  AT(box,x,pushbox(x,S))}

(2)(S){ONBOX(climbbox(S))}

(3)(S){ONBOX(S) ∧ AT(box,c,S)  HB(grasp(S)) }

(4)(x) (S){AT(box,x,S)  AT(box,x,climbbox(S))}

(5) ~ONBOX(S0)

(6)(S) HB(S)   要证的结论

(1)ONBOX(S1) ∨ AT(box,x,pushbox(x,S1))

(2)ONBOX(climbbox(S2))

(3)~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3)) 

(4)~AT(box,x,S4)∨AT(box,x,climbbox(S4))

(5) ~ONBOX(S0)

(6)目标的非：~HB(S5)

(1)ONBOX(S) ∨ AT(box,x,pushbox(x,S))

(2)ONBOX(climbbox(S))

(3)~ONBOX(S)∨~AT(box,c,S)∨HB(grasp(S)) 

(4)~AT(box,x,S)∨AT(box,x,climbbox(S))

(5) ~ONBOX(S0)

(6)NIL

目标的非：~HB(S)

~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3))

实验2 子句消解实验 

一、实验目的：

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

二、实验原理：

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

三、实验条件

硬件：微型计算机。

任选一种流行语言。 

四、实验内容：

编写消解程序。

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

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

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

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

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

3.  用户界面设计；

4.  分析消解过程，写消解实验报告。（每人）

2.6 规则演绎系统

教学内容：本小节主要介绍规则演绎系统的定义和推理过程。    

教学重点：规则演绎系统的推理过程。

教学难点：规则演绎系统的推理过程。

教学方法：课堂讲授为主。

教学要求：掌握规则演绎系统的整个推理过程。

定义：

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

2.6.1 规则正向演绎系统

定义：

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

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

在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。

1. 事实表达式的与或形变换

例如：

(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. 事实表达式的与或图表示

图2.8 一个事实表达式的与或树表示

子句集：

Q(v,A)

~R(v)∨~S(A,v)

~P(v)∨~S(A,v)

与或图的F规则变换：

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

  L  W          

式中：L是单文字；W为与或形的唯一公式。

下面的证明限定：目标是可以证明的，目标是析取关系

例如： (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)

P ∨ Q ∨ X ∨ Z

P ∨ Q ∨ Y ∨ Z

R∨ X ∨ Z

R∨ Y ∨ Z

事实: A∨B        规则:A  C∧D,  B E∧G      目标: C∨G(析取)

结论：以目标节点作为终止解图时，系统成功终止

2.6.2 规则逆向演绎系统

定义：

逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。 

求解过程

⏹目标表达式的与或形式

⏹与或图的B规则变换, WL,L是单文字；W为与或形的公式

⏹作为终止条件的事实节点的一致解图

例如： (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(z))

Q(f(y),y) ∧ ~P(f(y))

Q(f(x),x) ∧ ~S(x)

例：

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)]

2.6.3 规则双向演绎系统

正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。

2.7 产生式系统

教学内容：本小节主要介绍产生式系统的定义和推理过程。    

教学重点：产生式系统推理的过程。

教学难点：产生式系统推理的过程。

教学方法：课堂讲授为主。

教学要求：掌握产生式系统的整个推理过程。

2.7.1 产生式系统的组成

定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。

实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。

一个产生式系统由下列3部分组成：

一个总数据库(global database)，它含有与具体任务有关的信息。

一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。

一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。 

选择规则到执行操作的步骤：

1 匹配

  把当前数据库与规则的条件部分相匹配。

2 冲突

  当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。

3 操作

操作就是执行规则的操作部分。

2.7.2 产生式系统的推理 

正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。 

逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。 

双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。

实验3 产生式系统实验 

一、实验目的：

    熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。 

二、实验原理：

    产生式系统用来描述若干个不同的以一个基本概念为基础的系统，这个基本概念就是产生式规则或产生式条件和操作对。在产生式系统中，论域的知识分为两部分：用事实表示静态知识；用产生式规则表示推理过程和行为。

三、实验条件

    硬件：微型计算机。

    任选一种流行语言。 

四、实验内容：

    自己建造产生式系统（包括规则库和事实库），然后进行推理，即可以自己输入任何的规则和事实，并基于这种规则和事实进行推理。

    建造动物识别系统。

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

1. 知识库设计和实现，包括规则库和总数据库；

2. 控制策略设计和实现；

3.  用户界面设计和实现；

4.  分析推理过程，写实验报告。（每人）