知识表示方法-状态空间法PPT课件

.,1,知识表示方法状态空间法,.,2,用计算机技术解决实际问题的一般思路:,实际问题,问题表达知识表达数学建模,求解的方法或者算法,结果的解释,.,3,例：求侧面积为150平方米的体积最大的长方体？,设长、宽、高分别为x,y,z侧面积为：2(xy+yz+xz)体积为：xyz数学模型maxxyzs.t.2(xy+yz+xz)=150,x,y,z,.,4,利用最优化技术中的算法，可以得到结果：x=y=z=5.0解释：长、宽、高都等于5米时，体积最大,说明：在计算数学的课程中，主要关心求解的具体算法,.,5,在人工智能中，重点关注两个方面的内容：问题的表示（知识的表示）：即要找到问题的一种合适的表示方法在人工智能中，我们要涉及到：状态空间法问题归约法谓词逻辑法样本向量法,.,6,问题的求解：从问题表示方法出发，找到一个合理的办法来求解在人工智能中，常有的方法有：搜索法推理法计算方法,.,7,状态空间法,在日常的一些智力游戏（八数码、走八卦阵、走迷宫等）中，我们采用的策略：试着向前走，如果走不通，则往后退，不停地试、试、试，直到成功,.,8,类似地，在人工智能中，一种最基本的求解方法就是试探搜索法，即，通过在某个可能的解空间（例如，所有可能的走法）中寻找一个解,这种基于解空间的问题表示和求解方法就是状态空间法，其基础是状态和算符（算子）,.,9,1.问题状态描述,状态：描述某一类不同事物间的差别而引入的一组最少变量q0,q1,qn的有序集合,.,10,例：描述在坐的同学变量可以有:年级班级姓名性别学号,根据要解决的问题、从中选择最少的一组变量,例：区分哪一个班：年级、班级区分哪一位同学：姓名、性别、学号,.,11,矢量形式：Q=q0,q1,qnT,其中，元素qi(i=0,1,n)为集合的分量，称为状态变量。,具体状态：给每一个状态变量一个具体的值（符号、数值等）。,.,12,矩阵形式,.,13,例：八数码问题,矢量形式的状态表示：,矩阵形式的状态表示：,.,14,算符（操作符）：使问题从一个状态变换到另一状态的手段。例如：走步、规则、数学算子、运算符号等等。,.,15,例：描述在坐的同学（续）状态变量可以有：年级班级姓名性别学号,操作符：入学正常升级毕业,.,16,例：八数码问题,算符：1、数字的上、下、左、右移动2、空格的上、下、左、右移动,.,17,问题的状态空间：一个表示问题全部可能状态及其关系的图，它包含了三个集合：所有可能的问题初始状态集合S操作符集合F目标状态集合G状态空间记作三元状态：（S,F,G）,.,18,例：十五数码问题,初始状态：左图目标状态：右图操作符集合F空格的左移、上移、右移、下移,.,19,可能的求解过程,注：在程序和图示求解过程中，需要规定好操作符的使用顺序,.,20,要完成某一个具体问题的状态描述，必须完成三项工作：如何描述状态，特别是初始状态操作符集合及其对状态描述的作用如何描述目标状态即定义好三元状态（S,F,G）中的三个成分,.,21,状态空间法：从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止,.,22,状态空间法的问题：寻找从初始状态到目标状态的某一个操作符序列状态空间法的解：从初始状态变换到目标状态的操作符序列,.,23,2.状态图示法,图是由节点（不一定是有限个的节点）的集合构成的注意：在图论中，图的定义中还包括边的集合,状态空间法（求解过程）的表示方法：用图来表示（借助于图论中某些技术）,.,24,有向图和无向图：,.,25,无向图：一对节点可能互为后裔，边用线段来表示,.,26,有向图：一对节点用弧线连接起来，并且从一个节点指向另一个节点,父辈节点或祖先ni,后继节点或后裔nj,.,27,对于某一个节点序列（ni0,ni2,nij,nik）如果每一个节点nij-1都有一个后继节点nij存在，则将这一序列称为从节点ni0到nik的长度为k的路径。,nik,ni0,.,28,如果从节点ni到nj存在一条路径，则称节点nj是从节点ni可到达的节点，或者称nj是ni的后裔节点、称ni是nj的祖先。,nj,ni,祖先,后裔,.,29,当用有向图来表示状态空间法时，对应关系：图中的一个节点对应于某一个状态图中的一个有向弧对应于某一个算符,注：有向弧的旁边可以标以具体算符,.,30,状态,节点,操作符,有向弧,.,31,问题：寻找从初始状态到目标状态的某个操作符序列,问题：寻找图中初始节点（对应初始状态）到目标节点（对应于目标状态）的一条路径,转化为,.,32,c(ni,nj)表示从节点ni指向节点nj（相邻）的那一段弧的代价,nj,ni,在某些情况下，每个操作符作用、成本是不一样的，需要引入代价的概念,.,33,（不相邻的）两个节点间路径的代价等于连接该路径的各个节点的所有弧线的代价之和,nk,n0,c(n0,n1),c(nk-1,nk),.,34,引入代价的概念后，我们的问题可能是：寻找初始节点到目标节点之间的代价最小的路径对应的原始问题：寻找从初始状态到目标状态的操作符代价之和最小的操作符序列,.,35,利用图论的技术，我们要解决两个问题：第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列,.,36,3.例子,例1：八数码问题八数码的任何一种摆法是一个状态，状态总数为9！。用一个长度为9的一维数组来描述状态：（q1,q2,q9）其中，qi取0,1,8个数，0表示空格，且取值互不相同。算符是空格的上、下、左、右移动,.,37,如果记空格的位置为P，这时空格的移动规则是：,P,P-3,P+1,P+3,P-1,表示位置,123456789,P,.,38,空格移动规则,表示位置,.,39,初始状态：(2，0，3，1，8，4，5，6，7）,目标状态:（1，2，3，8，0，4，5，6，7）,部分状态空间图,.,40,注意：事先规定操作符的前后顺序，便于编程不要生成已有的状态（节点），防止进入死循环,.,41,例2：迷宫问题,.,42,给图上加一个坐标系，定义每一个分叉路口为一个状态。,.,43,操作符为人的上、下、左、右走动,初始状态为（1，1）,目标状态为（4，4）,.,44,部分状态空间图,.,45,例3：梵塔问题（三个盘）对于n个盘的问题，我们用n维向量（a1a2an）表示问题的一个状态其中ai=1,2,3表示第i个盘位于第一、二、三个柱子上，a1an中盘的大小从大到小,.,46,初始状态为（11），目标状态为（33）操作符m(i,j)：表示一个盘从i根柱子搬到第j根柱子。T(k)：表示第k根柱子上（最上面）的盘的大小。操作符集合为：O=m(i,j)|T(i)人数：野人2-传教士0此岸野人数3,传教士数3渡河方向：人数：野人2-传教士0此岸野人数2,传教士数3渡河方向：人数：野人0-传教士2此岸野人数1,传教士数3渡河方向：人数：野人0-传教士2此岸野人数2,传