人工智能2(北邮课件).ppt

第二章 知识表示方法 2.1 状态空间法 问题状态描述 状态图示法 状态空间表示举例 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)　 算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。 　问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。 2、状态空间的表示法 对一个问题的状态描述，必须确定3件事： 　　(1) 该状态描述方式，特别是初始状态描述；　　(2) 操作符集合及其对状态描述的作用；　　(3) 目标状态描述的特性。 2.1.2 状态图示法 图的基本概念 　　图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图(directed graph)。　　某个节点序列(ni1,ni2,…,nik)当j=2，3，…，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。　　代价(cost) 是给各弧线指定数值以表示加在相应算符上的代价。 图的显式说明 是指各节点及其具有代价的弧线由一张表明确给出。 图的隐式说明 是指各节点及其具有代价的弧线不能由一张表明确给出。。 2.1.3 状态空间表示举例 1、产生式系统 一个产生式系统由下列3部分组成： 一个总数据库(global database)，它含有与具体任务有关的信息。 一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。 一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。 2、状态空间表示举例　　  状态空间表示 设系统的状态用四元数组描述： S=(w, x, y, z) 其中w:猴子所处水平位置 x:箱子所在水平位置 y:猴子是否在箱子上(y=1,在; y=0，不在) z:猴子是否能拿到香蕉(z=1,拿到; z=0,没有拿到) 可能出现的状态如下： 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为目标状态。 算符 F=(f1, f2, f3 , f4 ) 其中 f1 (u) 为猴子走到u处。(w, x, 0, z)→ (u, x, 0, z) f2 (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 ) 求解过程 2.2 问题归约法 问题归约描述 与或图表示 2.2.1 问题归约描述 1、问题归约法的概念 　　已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。　该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。 2、问题归约法的组成部分 　 （1）一个初始问题描述；　　（2）一套把问题变换为子问题的操作符；　　（3）一套本原问题描述。 3、示例：梵塔难题 　　问题 有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较