人工智能第二章知识表示方法

第二章知识表示方法教学内容：本章讨论知识表示的各种方法，是人工智能课程三大内容（知识表示、知识推理、知识应用）之一，也是学习人工智能其他内容的基础。教学重点：状态空间法、问题归约法、谓词逻辑法、语义网络法。教学难点：状态描述与状态空间图示、问题归约机制、置换与合一。教学方法：课堂教学为主，同时结合《离散数学》等已学的内容实时提问、收集学生学习情况，充分利用网络课程中的多媒体素材来表示抽象概念。教学要求：重点掌握用状态空间法、问题归约法、谓词演算法、语义网络法来描述问题；解决问题；掌握几种主要方法之间的差别；并对其它几种表示方法有一般了解。2.1状态空间法教学内容：本节是通过状态空间法来求解问题，它是以状态和算符(operator)为基础来表示和求解问题的。教学重点：问题的状态描述，操作符。教学难点：选择一个好的状态描述与状态空间表示方案。教学方法：以课堂教学为主；充分利用网络课程中的多媒体素材来阐述抽象概念。教学要求：重点掌握对某个问题的状态空间描述，学会组织状态空间图，用搜索图来求解问题。2.1.1问题状态描述1、状态（State）的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=［q0,q1,…,qn］T(2.1)式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=［q０k,q1k,…，qnk］T(2.2)算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(statespace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。提问：1.列举已经学习过的“状态”概念，并比较之。2.列举算符。举例：列举几个日常生活中状态与算符的例子，如：棋局。讨论：每走一步后，棋局都变化了，以此来理解问题的状态空间。2、状态空间的表示法对一个问题的状态描述，必须确定3件事：(1)该状态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性。举例：讲解初始状态、算符、中间状态与目标状态之间的关系；讲解三数码难题的状态变化过程。2.1.2状态图示法图的基本概念图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图(directedgraph)。某个节点序列(ni1,ni2,…,nik)当j=2，3，…，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(cost)是给各弧线指定数值以表示加在相应算符上的代价。图的显式说明是指各节点及其具有代价的弧线由一张表明确给出。图的隐式说明是指各节点及其具有代价的弧线不能由一张表明确给出。提问：举已经学习过的“有向图”、“路径”及“代价”等的概念。举例：针对三数码难题的状态变化过程讲解图的几个基本概念。2.1.3状态空间表示举例1、产生式系统一个产生式系统由下列3部分组成：一个总数据库(globaldatabase)，它含有与具体任务有关的信息。一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2、状态空间表示举例猴子与香蕉的问题状态空间表示用四元组（W，x，y，z）其中：W-猴子的水平位置；x－当猴子在箱子顶上时取x=1；否则取x=0；Y－箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。算符(1)goto(U)猴子走到水平位置U；(2)pushbox(V)猴子把箱子推到水平位置V；(3)climbbox猴子爬上箱顶；(4)grasp猴子摘到香蕉。求解过程令初始状态为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图，如图所示。从图不难看出，把该初始状态变换为目标状态的操作序列为：｛goto(b),pushbox(c),climbbox,grasp｝举例：针对多媒体上的猴子与香蕉问题的状态空间图，讲解问题的状态空间表示和产生式规则的应用。2.2问题归约法教学内容：知识表示的归约法，即已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题的方法。教学重点：问题归约的基本思想，问题描述，问题变换的操作符，与或图表示。教学难点：如何把初始问题变换为子问题，与或图表示方法。教学方法：课堂教学为主，充分利用网络课程中的相关多媒体素材来表示抽象概念。教学要求：通过梵塔难题重点掌握问题归约法的机理和问题归约描述方法。学会用与或图表示归约问题。2.2.1问题归约描述1、问题归约法的概念已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。2、问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。3、示例：梵塔难题问题有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。归约过程（1）移动圆盘A和B至柱子2的双圆盘难题；（2）移动圆盘C至柱子3的单圆盘难题；（3）移动圆盘A和B至柱子3的双圆盘难题。由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。讲述：梵塔问题的来源。提问：一圆盘问题要走几步？两圆盘问题要走几步？三个、四个．．．等？4、归约描述问题归约方法是应用算符来把问题描述变换为子问题描述。可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题［（111）→(122)］，［(122)→(322)］以及［(322)→(333)］规定了最后解答路径将要通过的脚踏石状态(122)和(322)。问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。2.2.2与或图表示1、与或图的概念用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。举例：含有与图与或图的混合图。提问：对于一个与或图如何引入附加节点，使得后继问题的每个集合能够聚集在它们各自的父辈节点之下。2、与或图的有关术语父节点是一个初始问题或是可分解为子问题的问题节点；子节点是一个初始问题或是子问题分解的子问题节点；或节点只要解决某个问题就可解决其父辈问题的节点集合；与节点只有解决所有子问题，才能解决其父辈问题的节点集合；弧线是父辈节点指向子节点的圆弧连线；终叶节点是对应于原问题的本原节点。举例：对于一个与或图。提问：指出图中的父节点、子节点、或节点、与节点、弧线和终叶节点。3、与或图的有关定义可解节点与或图中一个可解节点的一般定义可以归纳如下：(1)终叶节点是可解节点(因为它们与本原问题相关连)。(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。举例：对于一个与或图。提问：指出图中的终叶节点、可解节点、不可解节点。不可解节点不可解节点的一般定义归纳于下：(1)没有后裔的非终叶节点为不可解节点。(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。举例：对于三圆盘梵塔难题根据构图规则画出其归约图。提问：指出图中的终叶节点、可解节点、不可解节点。课后作业：教材第二章习题2－2与2－54、与或图构图规则(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。2.3谓词逻辑法教学内容：本节主要讲述问题的谓词逻辑表示的基本方法。教学重点：谓词逻辑、谓词公式、谓词演算、置换与合一。教学难点：如何选择谓词，问题的谓词逻辑表示及运算。教学方法：课堂教学为主，充分利用网络课程中的示例程序。教学要求：重点掌握谓词逻辑表示的语言与方法，掌握谓词公式的性质及谓词演算，学会谓词公式的置换与合一，运用谓词推理来解决问题。2.3.1谓词演算1、语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值T(真)；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假)。2、连词和量词连词有∧(与)、∨(或)，全称量词(x)，存在量词(x)。原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合适公式。3、几个有关定义用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。用连词→连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。如果前项和后项都是合适公式，那么蕴涵也是合适公式。前面具有符号～的公式叫做否定。一个合适公式的否定也是合适公式。量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。在合适公式中，感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。2.3.2谓词公式1、谓词合适公式的定义在谓词演算中合适公式的递归定义如下：(1)原子谓词公式是合适公式。(2)若A为合适公式，则～A也是一个合适公式。(3)若A和B都是合适公式，则(A∧B)，(A∨B)，(A=B)和(A←→B)也都是合适公式。(4)若A是合适公式，x为A中的自由变元，则(x)A和(x)A都是合适公式。(5)只有按上述规则(1)至(4)求得的那些公式，才是合适公式。举例：试把下列命题表示为谓词公式：任何整数或者为正或者为负。提问：指出此例题谓词公式中的量词、连词及蕴涵符号。2、合适公式的性质(1)否定之否定～(～P)等价于P(2)P∨Q等价于～P→Q(3)狄