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

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