《人工智能第2章(知识表示方法1-状态空间法)ppt课件》由会员分享，可在线阅读，更多相关《人工智能第2章(知识表示方法1-状态空间法)ppt课件（55页珍藏版）》请在金锄头文库上搜索。
1、2020/11/8,人 工 智 能 Artificial Intelligence (AI),许建华 南京师范大学计算机科学与技术学院 2011年秋季,2020/11/8,第2章 知识表示方法,2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法,2020/11/8,用计算机技术解决实际问题的一般思路:,实际 问题,问题表达 知识表达 数学建模,求解的方法 或者算法,结果的解释,2020/11/8,例：求侧面积为150平方米的体积最大的长方体？,设长、宽、高分别为 x, y, z 侧面积为：2(xy + yz + xz) 体积为：xyz 数学模型 max xyz s.t. 2(xy +
2、yz + xz)=150,x,y,z,2020/11/8,利用最优化技术中的算法，可以得到结果： x = y = z = 5.0 解释：长、宽、高都等于5米时，体积最大,说明：在计算数学的课程中，主要关心求解的具体算法,2020/11/8,在人工智能中，重点关注两个方面的内容： 问题的表示（知识的表示）：即要找到问题的一种合适的表示方法 在人工智能中，我们要涉及到： 状态空间法 问题归约法 谓词逻辑法 样本向量法,2020/11/8,问题的求解：从问题表示方法出发，找到一个合理的办法来求解 在人工智能中，常有的方法有： 搜索法 推理法 计算方法,2020/11/8,2.1 状态空间法,在日常的
3、一些智力游戏（八数码、走八卦阵、走迷宫等）中，我们采用的策略：试着向前走，如果走不通，则往后退，不停地试、试、试，直到成功,2020/11/8,类似地，在人工智能中，一种最基本的求解方法就是试探搜索法，即，通过在某个可能的解空间（例如，所有可能的走法）中寻找一个解,这种基于解空间的问题表示和求解方法就是状态空间法，其基础是状态和算符（算子）,2020/11/8,2.1.1 问题状态描述,状态： 描述某一类不同事物间的差别而引入的一组最少变量q0 ,q1 , qn的有序集合,2020/11/8,例：描述在坐的同学 变量可以有 年级 班级 姓名 性别 学号 ,根据要解决的问题、从中选择最少的一组变
4、量,例： 区分哪一个班：年级、班级 区分哪一位同学：姓名、性别、学号,2020/11/8,矢量形式： Q= q0, q1, , qn T,其中，元素 qi ( i=0, 1, n)为集合的分量，称为状态变量。,具体状态：给每一个状态变量一个具体的值（符号、数值等）。,2020/11/8,矩阵形式,2020/11/8,例：八数码问题,矢量形式的状态表示：,矩阵形式的状态表示：,2020/11/8,算符（操作符）：使问题从一个状态变换到另一状态的手段。 例如：走步、规则、数学算子、运算符号等等。,2020/11/8,例：描述在坐的同学（续） 状态变量可以有 年级 班级 姓名 性别 学号 ,操作符
5、入学 正常升级 毕业,2020/11/8,例：八数码问题,算符： 1、数字的上、下、左、右移动 2、空格的上、下、左、右移动,2020/11/8,问题的状态空间：一个表示问题全部可能状态及其关系的图，它包含了三个集合： 所有可能的问题初始状态集合S 操作符集合F 目标状态集合G 状态空间记作三元状态（S, F, G）,2020/11/8,例：十五数码问题,初始状态：左图 目标状态：右图 操作符集合F空格的左移、上移、右移、下移,2020/11/8,可能的求解过程,注：在程序和图示求解过程中，需要规定好操作符的使用顺序,2020/11/8,要完成某一个具体问题的状态描述，必须完成三项工作： 如何
6、描述状态，特别是初始状态 操作符集合及其对状态描述的作用 如何描述目标状态 即定义好三元状态（S, F, G）中的三个成分,2020/11/8,状态空间法： 从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止,2020/11/8,状态空间法的问题： 寻找从初始状态到目标状态的某一个操作符序列 状态空间法的解： 从初始状态变换到目标状态的操作符序列,左、下、上.,2020/11/8,2.1.2 状态图示法,图是由节点（不一定是有限个的节点）的集合构成的 注意：在图论中，图的定义中还包括边的集合,状态空间法（求解过程）的表示方法：用图来表示（借助于图论中某些技术）
7、,2020/11/8,有向图和无向图：,2020/11/8,无向图：一对节点可能互为后裔，边用线段来表示,2020/11/8,有向图：一对节点用弧线连接起来，并且从一个节点指向另一个节点,父辈节点或祖先n i,后继节点或后裔nj,2020/11/8,对于某一个节点序列 （ni0, ni2, nij, , nik） 如果每一个节点 nij-1 都有一个后继节点 nij 存在，则将这一序列称为从节点 ni0 到 nik 的长度为 k 的路径。,nik,ni0,2020/11/8,如果从节点 ni 到 nj 存在一条路径，则称节点 nj 是从节点 ni 可到达的节点，或者称 nj 是 ni 的后裔节
8、点、称 ni 是 nj 的祖先。,nj,ni,祖先,后裔,2020/11/8,当用有向图来表示状态空间法时，对应关系： 图中的一个节点对应于某一个状态 图中的一个有向弧对应于某一个算符,注：有向弧的旁边可以标以具体算符,2020/11/8,状态,节点,操作符,有向弧,2020/11/8,问题：寻找从初始状态到目标状态的某个操作符序列,问题：寻找图中初始节点（对应初始状态）到目标节点（对应于目标状态）的一条路径,转化为,2020/11/8,c (ni , nj) 表示从节点 ni 指向节点 nj （相邻）的那一段弧的代价,n j,n i,在某些情况下，每个操作符作用、成本是不一样的，需要引入代价
9、的概念,2020/11/8,（不相邻的）两个节点间路径的代价等于连接该路径的各个节点的所有弧线的代价之和,nk,n0,C(n0,n1),C(nk-1,nk),2020/11/8,引入代价的概念后，我们的问题可能是： 寻找初始节点到目标节点之间的代价最小的路径 对应的原始问题：寻找从初始状态到目标状态的操作符代价之和最小的操作符序列,2020/11/8,利用图论的技术，我们要解决两个问题： 第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列 第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列,202
10、0/11/8,2.1.3 例子,例1：八数码问题 八数码的任何一种摆法是一个状态，状态总数为9！。用一个长度为9的一维数组来描述状态：（q1, q2, ,q9） 其中，qi 取0, 1, , 8个数，0表示空格，且取值互不相同。 算符是空格的上、下、左、右移动,2020/11/8,如果记空格的位置为P，这时空格的移动规则是：,P,P-3,P+1,P+3,P-1,表示位置,1 2 3 4 5 6 7 8 9,P,2020/11/8,空格移动规则,表示位置,2020/11/8,初始状态：(2，0，3，1，8，4，5，6，7）,目标状态:（1，2，3，8，0，4，7，6，5）,部分状态空间图,202
11、0/11/8,注意： 事先规定操作符的前后顺序，便于编程 不要生成已有的状态（节点），防止进入死循环,2020/11/8,例2：迷宫问题,2020/11/8,给图上加一个坐标系，定义每一个分叉路口为一个状态。,2020/11/8,操作符为人的上、下、左、右走动,初始状态为（1，1）,目标状态为（4，4）,2020/11/8,部分状态空间图,2020/11/8,例3：梵塔问题（三个盘） 对于 n 个盘的问题，我们用 n 维向量 （a1 a2an） 表示问题的一个状态 其中ai = 1, 2, 3 表示第i个盘位于第一、二、三个柱子上，a1 an中盘的大小从大到小,2020/11/8,初始状态为（
12、11），目标状态为（33） 操作符m(i, j)：表示一个盘从 i 根柱子搬到第 j 根柱子。 T(k)：表示第 k 根柱子上（最上面）的盘的大小。 操作符集合为： O=m( i , j ) | T( i )T( j ),2020/11/8,部分状态空间图,2020/11/8,例4：猴子与香蕉问题,a c b,2020/11/8,用一个四元组（W，x, Y, z）来表示问题的状态 W：猴子的水平位置 x： 当猴子爬到箱子顶上取1，否则取0 Y： 箱子的水平位置 z： 当猴子摘到香蕉时取1，否则取0 初始状态是（a, 0, b, 0），目标状态是（c, 1, c, 1）,2020/11/8,操作
13、符： 猴子当前位置W走到水平位置U：goto(U)： （W, 0 , Y, z）(U, 0 , Y, z) 注：猴子必须不在箱子上 猴子将箱子从W位置推到水平位置V：pushbox(V)： （W, 0, W, z） (V, 0, V, z) 注：猴子与箱子必须在同一位置,2020/11/8,操作符： 猴子爬到箱子上：climbbox： （W, 0, W, z） (W，1, W, z) 猴子摘到香蕉：grasp： （c, 1, c, 0） (c, 1, c, 1),2020/11/8,a c b,部分状态空间图,初始状态,目标状态,pushbox,2020/11/8,例5：四皇后问题,状态：任意一种合法的摆法 操作符：摆下一个皇后，先摆第一行，每一行从左开始摆，并满足皇后不成线的规则,2020/11/8,思考题： 小结用状态空间法表示八数码问题的讲课内容，考虑如何在计算机上加以实现？,
