知识表示方法-状态空间法.ppt

1、知识表示方法 状态空间法,用计算机技术解决实际问题的一般思路:,实际 问题,问题表达 知识表达 数学建模,求解的方法 或者算法,结果的解释,例：求侧面积为150平方米的体积最大的长方体？,设长、宽、高分别为 x, y, z 侧面积为：2(xy + yz + xz) 体积为：xyz 数学模型 max xyz s.t. 2(xy + yz + xz)=150,x,y,z,利用最优化技术中的算法，可以得到结果： x = y = z = 5.0 解释：长、宽、高都等于5米时，体积最大,说明：在计算数学的课程中，主要关心求解的具体算法,在人工智能中，重点关注两个方面的内容： 问题的表示（知识的表示）：即

2、要找到问题的一种合适的表示方法 在人工智能中，我们要涉及到： 状态空间法 问题归约法 谓词逻辑法 样本向量法,问题的求解：从问题表示方法出发，找到一个合理的办法来求解 在人工智能中，常有的方法有： 搜索法 推理法 计算方法,状态空间法,在日常的一些智力游戏（八数码、走八卦阵、走迷宫等）中，我们采用的策略：试着向前走，如果走不通，则往后退，不停地试、试、试，直到成功,类似地，在人工智能中，一种最基本的求解方法就是试探搜索法，即，通过在某个可能的解空间（例如，所有可能的走法）中寻找一个解,这种基于解空间的问题表示和求解方法就是状态空间法，其基础是状态和算符（算子）,1. 问题状态描述,状态： 描述

3、某一类不同事物间的差别而引入的一组最少变量q0 ,q1 , qn的有序集合,例：描述在坐的同学 变量可以有: 年级 班级 姓名 性别 学号 ,根据要解决的问题、从中选择最少的一组变量,例： 区分哪一个班：年级、班级 区分哪一位同学：姓名、性别、学号,矢量形式： Q= q0, q1, , qn T,其中，元素 qi ( i=0, 1, n)为集合的分量，称为状态变量。,具体状态：给每一个状态变量一个具体的值（符号、数值等）。,矩阵形式,例：八数码问题,矢量形式的状态表示：,矩阵形式的状态表示：,算符（操作符）：使问题从一个状态变换到另一状态的手段。 例如：走步、规则、数学算子、运算符号等等。,例

4、：描述在坐的同学（续） 状态变量可以有： 年级 班级 姓名 性别 学号 ,操作符： 入学 正常升级 毕业,例：八数码问题,算符： 1、数字的上、下、左、右移动 2、空格的上、下、左、右移动,问题的状态空间：一个表示问题全部可能状态及其关系的图，它包含了三个集合： 所有可能的问题初始状态集合S 操作符集合F 目标状态集合G 状态空间记作三元状态：（S, F, G）,例：十五数码问题,初始状态：左图 目标状态：右图 操作符集合F空格的左移、上移、右移、下移,可能的求解过程,注：在程序和图示求解过程中，需要规定好操作符的使用顺序,要完成某一个具体问题的状态描述，必须完成三项工作： 如何描述状态，特别

5、是初始状态 操作符集合及其对状态描述的作用 如何描述目标状态 即定义好三元状态（S, F, G）中的三个成分,状态空间法： 从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止,状态空间法的问题： 寻找从初始状态到目标状态的某一个操作符序列 状态空间法的解： 从初始状态变换到目标状态的操作符序列,2. 状态图示法,图是由节点（不一定是有限个的节点）的集合构成的 注意：在图论中，图的定义中还包括边的集合,状态空间法（求解过程）的表示方法：用图来表示（借助于图论中某些技术）,有向图和无向图：,无向图：一对节点可能互为后裔，边用线段来表示,有向图：一对节点用弧线连接起

6、来，并且从一个节点指向另一个节点,父辈节点或祖先n i,后继节点或后裔nj,对于某一个节点序列 （ni0 , ni2 , nij , , nik） 如果每一个节点 nij-1 都有一个后继节点 nij 存在，则将这一序列称为从节点 ni0 到 nik 的长度为 k 的路径。,nik,ni0,如果从节点 ni 到 nj 存在一条路径，则称节点 nj 是从节点 ni 可到达的节点，或者称 nj 是 ni 的后裔节点、称 ni 是 nj 的祖先。,nj,ni,祖先,后裔,当用有向图来表示状态空间法时，对应关系： 图中的一个节点对应于某一个状态 图中的一个有向弧对应于某一个算符,注：有向弧的旁边可以标

7、以具体算符,状态,节点,操作符,有向弧,问题：寻找从初始状态到目标状态的某个操作符序列,问题：寻找图中初始节点（对应初始状态）到目标节点（对应于目标状态）的一条路径,转化为,c (ni , nj) 表示从节点 ni 指向节点 nj （相邻）的那一段弧的代价,n j,n i,在某些情况下，每个操作符作用、成本是不一样的，需要引入代价的概念,（不相邻的）两个节点间路径的代价等于连接该路径的各个节点的所有弧线的代价之和,nk,n0,c(n0,n1),c(nk-1,nk),引入代价的概念后，我们的问题可能是： 寻找初始节点到目标节点之间的代价最小的路径 对应的原始问题：寻找从初始状态到目标状态的操作符

8、代价之和最小的操作符序列,利用图论的技术，我们要解决两个问题： 第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列 第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列,3. 例子,例1：八数码问题 八数码的任何一种摆法是一个状态，状态总数为9！。用一个长度为9的一维数组来描述状态：（q1, q2, ,q9） 其中，qi 取0, 1, , 8个数，0表示空格，且取值互不相同。 算符是空格的上、下、左、右移动,如果记空格的位置为P，这时空格的移动规则是：,P,P-3,P+1,P+3,P-1,表示位置,

9、1 2 3 4 5 6 7 8 9,P,空格移动规则,表示位置,初始状态：(2，0，3，1，8，4，5，6，7）,目标状态:（1，2，3，8，0，4，5，6，7）,部分状态空间图,注意： 事先规定操作符的前后顺序，便于编程 不要生成已有的状态（节点），防止进入死循环,例2：迷宫问题,给图上加一个坐标系，定义每一个分叉路口为一个状态。,操作符为人的上、下、左、右走动,初始状态为（1，1）,目标状态为（4，4）,部分状态空间图,例3：梵塔问题（三个盘） 对于 n 个盘的问题，我们用 n 维向量 （a1 a2an） 表示问题的一个状态 其中ai = 1, 2, 3 表示第i个盘位于第一、二、三个柱子

10、上，a1 an中盘的大小从大到小,初始状态为（11），目标状态为（33） 操作符m(i, j)：表示一个盘从 i 根柱子搬到第 j 根柱子。 T(k)：表示第 k 根柱子上（最上面）的盘的大小。 操作符集合为： O=m( i , j ) | T( i )T( j ),部分状态空间图,例4：猴子与香蕉问题,a c b,用一个四元组（W，x, Y, z）来表示问题的状态 W：猴子的水平位置 x： 当猴子爬到箱子顶上取1，否则取0 Y： 箱子的水平位置 z： 当猴子摘到香蕉时取1，否则取0 初始状态是（a, 0, b, 0），目标状态是（c, 1, c, 1）,操作符： 猴子当前位置W走到水平位置U

11、：goto(U)： （W, 0 , Y, z）(U, 0 , Y, z) 注：猴子必须不在箱子上 猴子将箱子从W位置推到水平位置V：pushbox(V)： （W, 0, W, z） (V, 0, V, z) 注：猴子与箱子必须在同一位置,操作符： 猴子爬到箱子上：climbbox： （W, 0, W, z） (W，1, W, z) 猴子摘到香蕉：grasp： （c, 1, c, 0） (c, 1, c, 1),a c b,部分状态空间图,(a,0,b,0),(b,0,b,0),(c,0,c,0),(b,1,b,0),(c,1,c,0),(a,0,a,0),(c,1,c,1),初始状态 Goto

12、(b),Goto(b),Pushbox(c),Grasp,目标状态,猴子摘香蕉问题的状态空间图,解序列为： Goto(b), Pushbox(c), Climbbox, Grasp,Pushbox(c),Climbbox,Climbbox,Pushbox(c),Pushbox(a),Pushbox(a),例5 ：修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。 设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束： 一是修道士和野人都会划船，但每次船上至多可载两个人； 二是在河的任一岸，如果野人数目超过修道士

13、数，修道士会被野人吃掉。 如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。,解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态 S=(m, c, b) 其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。 右岸的状态可由下式确定： 右岸修道士数 m=3-m 右岸野人数 c=3-c 右岸船数 b=1-b 在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有442=32种状态。,这32种状态并非全有意义，除去

14、不合法状态和修道士被野人吃掉的状态，有意义的状态只有16种： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0) 有了这些状态，还需要考虑可进行的操作。,操作是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。 每

15、个操作都应当满足如下条件： 一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目； 二是每次操作船上人数不得超过2个； 三是操作应保证不产生非法状态。 因此，操作应由条件部分和动作部分： 条件：只有当其条件具备时才能使用 动作：刻划了应用此操作所产生的结果。,操作的表示： 用符号Pij表示从左岸到右岸的运人操作 用符号Qij表示从右岸到左岸的操作 其中： i表示船上的修道士人数 j表示船上的野人数,操作集 本问题有10种操作可供选择： F=P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20 下面以P01和Q01为例来说明这些操作的条件和动作。 操作符号 条件 动作 P01 b=1, m=0或3, c1 b=0, c=c-1 Q01 b=0, m=0或3，c2 b=1, c=c+1,渡河过程如下： 渡河方向：- 人数：野人2 - 传教士0此岸野人数3, 传教士