人工智能ArtificialIntelligence(AI)第2章知识表示方法用计算机技术解决实际问题的一般思路:例：求侧面积为150平方米的体积最大的长方体？利用最优化技术中的算法，可以得到结果：x=y=z=5.0解释：长、宽、高都等于5米时，体积最大在人工智能中，重点关注两个方面的内容：①问题的表示（知识的表示）：即要找到问题的一种合适的表示方法在人工智能中，我们要涉及到：状态空间法问题归约法谓词逻辑法样本向量法②问题的求解：从问题表示方法出发，找到一个合理的办法来求解在人工智能中，常有的方法有：搜索法推理法计算方法2.1状态空间法类似地，在人工智能中，一种最基本的求解方法就是试探搜索法，即，通过在某个可能的解空间（例如，所有可能的走法）中寻找一个解2.1.1问题状态描述例：描述在坐的同学变量可以有年级班级姓名性别学号……矢量形式：Q=[q0,q1,…,qn]T矩阵形式例：八数码问题算符（操作符）：使问题从一个状态变换到另一状态的手段。例如：走步、规则、数学算子、运算符号等等。例：描述在坐的同学（续）状态变量可以有年级班级姓名性别学号……例：八数码问题问题的状态空间：一个表示问题全部可能状态及其关系的图，它包含了三个集合：所有可能的问题初始状态集合S操作符集合F目标状态集合G状态空间记作三元状态（S,F,G）例：十五数码问题可能的求解过程要完成某一个具体问题的状态描述，必须完成三项工作：①如何描述状态，特别是初始状态②操作符集合及其对状态描述的作用③如何描述目标状态即定义好三元状态（S,F,G）中的三个成分状态空间法：从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止状态空间法的问题：寻找从初始状态到目标状态的某一个操作符序列状态空间法的解：从初始状态变换到目标状态的操作符序列2.1.2状态图示法有向图和无向图：无向图：一对节点可能互为后裔，边用线段来表示有向图：一对节点用弧线连接起来，并且从一个节点指向另一个节点对于某一个节点序列（ni0,ni2,…nij,…,nik）如果每一个节点nij-1都有一个后继节点nij存在，则将这一序列称为从节点ni0到nik的长度为k的路径。如果从节点ni到nj存在一条路径，则称节点nj是从节点ni可到达的节点，或者称nj是ni的后裔节点、称ni是nj的祖先。当用有向图来表示状态空间法时，对应关系：图中的一个节点对应于某一个状态图中的一个有向弧对应于某一个算符状态问题：寻找从初始状态到目标状态的某个操作符序列c(ni,nj)表示从节点ni指向节点nj（相邻）的那一段弧的代价（不相邻的）两个节点间路径的代价等于连接该路径的各个节点的所有弧线的代价之和引入代价的概念后，我们的问题可能是：寻找初始节点到目标节点之间的代价最小的路径对应的原始问题：寻找从初始状态到目标状态的操作符代价之和最小的操作符序列利用图论的技术，我们要解决两个问题：第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列2.1.3例子初始状态：(2，0，3，1，8，4，5，6，7）注意：事先规定操作符的前后顺序，便于编程不要生成已有的状态（节点），防止进入死循环例2：迷宫问题给图上加一个坐标系，定义每一个分叉路口为一个状态。操作符为人的上、下、左、右走动部分状态空间图例3：梵塔问题（三个盘）对于n个盘的问题，我们用n维向量（a1a2…an）表示问题的一个状态其中ai=1,2,3表示第i个盘位于第一、二、三个柱子上，a1an中盘的大小从大到小初始状态为（1…1），目标状态为（3…3）操作符m(i,j)：表示一个盘从i根柱子搬到第j根柱子。T(k)：表示第k根柱子上（最上面）的盘的大小。操作符集合为：O={m(i,j)|T(i)<T(j)}部分状态空间图例4：猴子与香蕉问题用一个四元组（W，x,Y,z）来表示问题的状态W：猴子的水平位置x：当猴子爬到箱子顶上取1，否则取0Y：箱子的水平位置z：当猴子摘到香蕉时取1，否则取0初始状态是（a,0,b,0），目标状态是（c,1,c,1）操作符：①猴子当前位置W走到水平位置U：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)④猴子摘到香蕉