人工智能2(北邮幻灯片)

《人工智能2(北邮幻灯片)》由会员分享，可在线阅读，更多相关《人工智能2(北邮幻灯片)（104页珍藏版）》请在金锄头文库上搜索。

1、1,第二章 知识表示方法,状态空间法 问题归约法 谓词逻辑法 语义网络法 框架表示法 剧本表示法 过程表示法,2,2.1 状态空间法,问题状态描述 状态图示法 状态空间表示举例,3,2.1.1 问题状态描述,1、状态（State）的基本概念 状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下： Q=q0,q1,qnT (2.1) 式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。 给定每个分量的一组值就得到一个具体的状态，如 Qk=qk,q1k,，qnkT (2.2),4,算符：使问题从一种状态变化为另一种状态的手段称为操作

2、符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。,5,问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。,6,2、状态空间的表示法 对一个问题的状态描述，必须确定3件事： (1) 该状态描述方式，特别是初始状态描述； (2) 操作符集合及其对状态描述的作用； (3) 目标状态描述的特性。,7,八数码问题的状态空间 S状态集。八数码的所有的摆法(9!) G指定的某个或某些八数码摆放状态。 操作算子数码的移动。 4

3、(方向) 8(数码)32个 将空格向上移Up 将空格向左移Left 将空格向下移Down 将空格向右移 Right,8,2.1 状态空间法,问题状态描述 状态图示法 状态空间表示举例,9,2.1.2 状态图示法,图的基本概念 图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图(directed graph)。 某个节点序列(ni1,ni2,nik)当j=2，3，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。 代价(cost) 是给各弧线指定数值以表示加在相应

4、算符上的代价。,10,图的显式说明 是指各节点及其具有代价的弧线由一张表明确给出。 图的隐式说明 是指各节点及其具有代价的弧线不能由一张表明确给出。 。,11,1 4 3 7 6 5 8 2,1 3 7 4 6 5 8 2,1 4 3 7 6 5 8 2,1 4 3 7 8 6 5 2,1 4 3 7 6 5 8 2,1 3 7 4 6 5 8 2,1 3 7 4 6 5 8 2,1 4 3 7 6 5 8 2,4 3 5 7 6 8 2,1 4 3 7 8 6 5 2,1 4 3 7 8 6 5 2,1 4 7 6 3 5 8 2,1 4 3 7 6 2 5 8,Up,Left,Down,R

5、ight,Up,Down,Down,Up,Right,Left,Left,Right,12,2.1 状态空间法,问题状态描述 状态图示法 状态空间表示举例,13,2.1.3 状态空间表示举例,1、产生式系统 一个产生式系统由下列3部分组成： 一个总数据库(global database)，它含有与具体任务有关的信息。 一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。 一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,14,2、状态空间表示举例,猴子与香蕉的问题

6、,a,c,b,15,状态空间表示 设系统的状态用四元数组描述： S=(w, x, y, z) 其中w:猴子所处水平位置 x:箱子所在水平位置 y:猴子是否在箱子上(y=1,在; y=0，不在) z:猴子是否能拿到香蕉(z=1,拿到; z=0,没有拿到),16,可能出现的状态如下： S0=(a,b,0,0) S1=(b,b,0,0) S2=(c,c,0,0) S3=(c,c,1,0) S4=(c,c,1,1) 其中S0为初始状态， S4为目标状态。,17,算符 F=(f1, f2, f3 , f4 ) 其中 f1 (u) 为猴子走到u处。(w, x, 0, z) (u, x, 0, z) f2

7、(u) 为猴子走到v处。(x, x, 0, 0 ) (v, v, 0, 0) f3 为猴子爬上台子。 (x, x, 0, z ) (x, x,1, z) f4 为猴子拿到香蕉。 (c, c, 1, 0) (c, c,1, 1 ),18,求解过程,19,旅行商问题（travelling salesman problem,TSP问题）,销售员到几个城市去推销商品，城市之间的距离是已知的，他现在从某一个城市出发，经过每个城市一次，最后又回到出发的城市。要求归划好一条最短路线。,7,7,10,10,10,13,6,5,6,A,B,E,D,C,20,第二章 知识表示方法,状态空间法 问题归约法 谓词逻辑

8、法 语义网络法 框架表示法 剧本表示法 过程表示法,21,2.2 问题归约法,问题归约描述 与或图表示,22,2.2.1 问题归约描述,1、问题归约法的概念 已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。 该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。,23,2、问题归约法的组成部分 （1）一个初始问题描述； （2）一套把问题变换为子问题的操作符； （3）一套本原问题描述。,24,3、示例：梵塔难题 问题 有3个柱子(1，2，3)

9、和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。,25,1,3,2,C,1,2,3,A,B,A,B,C,26,归约过程： （1）移动圆盘A和B至柱子2的双圆盘难题； （2）移动圆盘C至柱子3的单圆盘难题； （3）移动圆盘A和B至柱子3的双圆盘难题。,27,1,3,2,C,1,2,3,A,B,A,B,C,28,1,2,3,A,B,C,1,2,3,A,B,C,29,

10、1,2,3,A,B,C,1,2,3,A,B,C,30,4、归约描述 问题归约方法是应用算符来把问题描述变换为子问题描述。 可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题（111）(122)，(122)(322)以及(322)(333)规定了最后解答路径将要通过的脚踏石状态(122)和(322)。 问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。,31,(1,1,1)(3,3,3),(1,1,1)(1,2,2),(1,2,2)(3,2,2),(3,2,2)(3,3,3),(1,1,1)(1,1,3),(1,2

11、,3)(1,2,2),(1,1,3)(1,2,3),(3,2,2)(3,3,3),(3,2,2)(3,2,1),(3,3,1)(3,3,3),32,2.2 问题归约法,问题归约描述 与或图表示,33,2.2.2 与或图表示,1、与或图的概念 用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。 例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。,34,35,2、与或图的有关术语 父节点 是一个初始问题或是可分解为子问题的问题节点； 子节点 是一个初始问题或是子问题分解的

12、子问题节点； 或节点 只要解决某个问题就可解决其父辈问题的节点集合； 与节点 只有解决所有子问题，才能解决其父辈问题的节点集合； 弧线 是父辈节点指向子节点的圆弧连线； 终叶节点 是对应于原问题的本原节点。,36,3、与或图的有关定义 可解节点 与或图中一个可解节点的一般定义可以归纳如下： (1) 终叶节点是可解节点(因为它们与本原问题相关连)。 (2) 如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。 (3) 如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。,37,不可解节点 不可解节点的一般定义

13、归纳于下： (1) 没有后裔的非终叶节点为不可解节点。 (2) 如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。 (3) 如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。,38,4、与或图构图规则 代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。 (2) 对应于本原问题的节点，叫做终叶节点，它没有后裔。 (3) 对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。 (4) 一般对于代表两个或两个以上子问题集合的每个节

14、点，有向弧线从此节点指向此子问题集合中的各个节点。 (5) 在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。,39,第二章 知识表示方法,状态空间法 问题归约法 谓词逻辑法 语义网络法 框架表示法 剧本表示法 过程表示法,40,2.3 谓词逻辑法,谓词演算 谓词公式 置换与合一,41,2.3.1 谓词演算,1、语法和语义 谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。 原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为

15、真时，才具有值T(真)；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假)。,42,2、连词和量词 连词有(与)、(或)，全称量词(x)，存在量词(x)。 原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合适公式。,43,3、几个有关定义 用连词把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。 用连词把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。 用连词连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。如果前项和后项都是合适公式，那么蕴涵也是合适公式。,44,前面具有符号的公式叫做否定。一个合适公式的否定也是合适公式。 量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。在合适公式中，感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。,45,2.3 谓词逻辑法,谓词演算 谓词公式 置换与合一,46,2.3.2 谓词公式,1、谓词合适公式的定义 在谓词演算中合适公式的递归定义如下： (1) 原子谓词公式