人工智能基础-高济-25282第二章

第二章问题求解的基本方法,开发人工智能技术的一个主要目的解决非平凡问题：难以用常规（数值计算、数据库应用等）技术直接解决，求解依赖于问题本身的描述和应用领域的相关知识。按所需的领域特有知识的多寡，问题求解系统可以划分为两大类：知识贫乏系统依靠搜索技术去解决问题，但因知识贫乏而缺乏针对性，效率往往低下。知识丰富系统借助于作试探性推理的识别技术，通过基于领域知识的匹配检查去识别解答，直接了当。大多数KB（KnowledgeBased）系统均采用包括推理的识别技术。二大类搜索技术：一般图搜索、基于问题归约的与或图搜索。二种经典的逻辑推理技术：基于归结的谓词演算、基于规则的演绎推理。,2.1一般图搜索,搜索技术是人工智能研究的早期成果：其最适合于设计基于一个操作算子集的问题求解任务，每个操作算子的执行均可使问题求解更接近于目标状态，搜索路径将由实际选用的操作算子的序列构成。主要内容：状态空间及其搜索的表示一般图搜索策略启发式搜索算法A实现启发式搜索的若干关键因素回溯策略和爬山法状态空间抽象和生成-测试法启发式搜索的适用性,1状态空间及其搜索的表示,1）状态空间的表示状态空间以SP指示，其可表示为一个二元组：SP=（S,O）S在问题求解（即搜索）过程中所有可达的合法状态构成的集合；O操作算子的集合，操作算子的执行导致状态的变迁。状态空间又可描述为一个有向图：节点：指示状态，节点间的有向弧：表示状态变迁，弧上的标签：指示导致状态变迁的操作算子。状态可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。,1状态空间及其搜索的表示,2）状态空间表示的经典例传教士和野人问题N个传教士带领N个野人划船渡河，安全约束：1）船上人数不得超过载重限量，设为K个人，2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士。特例：N=3，K=2；变量m传教士在左岸或船上的实际人数，变量c野人在左岸或船上的实际人数，变量b指示船是否在左岸（1、0）。上述约束条件转变为m+c2,mc。左岸状态描述为一个三元组：（m,c,b）考虑到在这个渡河问题中，左岸的状态描述（m,c,b）可以决定右岸的状态，所以整个问题状态就可以左岸的状态来描述，以简化问题的表示。设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以三元组（m,c,b）表示。,2）状态空间表示的经典例传教士和野人问题,问题求解任务可描述为：（3，3，1）（0，0，0）该简单问题的状态空间：可能的状态总数为442=32，只有20个状态是合法的（遵守安全约束），不合法状态，（1，0，1），（1，2，1），（2，3，1）不可达的合法状态（4个），（0，0，1），（0，3，0）。总共只有16个可达的合法状态。2类操作算子：L(m,c)指示从左岸到右岸的划船操作，R(m,c)指示从右岸回到左岸的划船操作，m和c取值的可能组合只有5个：10，20，11，01，02。总共有10个操作算子。,2）状态空间表示的经典例传教士和野人问题,渡河问题状态空间的有向图：参见图2.1,1状态空间及其搜索的表示,3）状态空间的搜索状态空间的搜索以SE指示，其可表示为1个五元组：SE=(S,O,E,I,G)E搜索引擎；I问题的初始状态，IS;G问题的目标状态集，GS。基本思想通过搜索引擎寻找一个操作算子的调用序列，使问题从初始状态变迁到目标状态之一。解答路径初-目变迁过程中产生的状态序列或相应的操作算子调用序列。搜索引擎可以设计为任意实现搜索算法的控制系统。状态空间的解答路径有多条，由于一个状态可以有多个可供选择的操作算子：渡河问题就有无数条解答路径（因为划船操作可逆），但只有4条是最短的，都包含11个操作算子的调用。状态空间一般都表示为或图也称一般图操作算子的可选（渡河问题的初始状态节点就有3个），在逻辑上称为“或”关系，意指只要其中有一条路径通往目标状态，就能获得成功解答。除了少数像渡河这样的简单问题外，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图。搜索图在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。,1状态空间及其搜索的表示,4）一般图搜索例八数码游戏33九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。求解的问题给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局（参见图2.2）。解答路径就是一个合法的走步序列。用一般图搜索方法解决该问题：为问题状态的表示建立数据结构：33的一个矩阵，*矩阵元素Sij0,1,8；其中1i,j3，*数字0指示空格，*数字1-8指示相应棋牌。103123图2.2中的八数码问题就可表示为：724804685765,4）一般图搜索例八数码游戏,制定操作算子集：*直观方法为每个棋牌制定一套可能的走步：左、上、右、下四种移动，这样就需32个操作算子。*简易方法仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。*空格移动的唯一约束是不能移出棋盘。八数码问题的搜索图：参见图2.3棋盘布局（问题状态）总共9!=362880个，但搜索图小得多。,1状态空间及其搜索的表示,5）状态空间、搜索图和解答路径之间的关系：对于状态空间很大的问题:设计搜索策略的关键考虑是解决组合爆炸问题。解决组合爆炸问题的方法实际上就是选用好的搜索策略，使得只要搜索状态空间的很小部分就能找到解答。,2一般图搜索策略,1）搜索术语（引自图论）：节点深度搜索图是一种有根图，根节点指示初始状态，令其节点深度为0，则搜索图中的其它节点的深度dn就可递归地定义为其父节点深度dn-1加1：dn=dn-1+1.路径从节点ni到nk的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。节点扩展应用操作算子将上一状态（节点ni）变迁到下一状态（节点nj），ni指示被扩展节点，nj即是由ni扩展出的子节点。路径代价相邻节点ni和nj间路径的代价记为C(ni,nj),由两部分组成：路径本身代价操作算子的执行代价。路径搜索代价又分为二部分：*路径建立代价从节点ni扩展出节点nj所付出的代价；*路径选择代价选择这条路径作为搜索方向（即选择nj作为下一步搜索起点）所付出的代价。作为简化处理，令任意相邻节点间的路径代价相同，并以路径长度1指示。记目标状态相应的节点为ng，则从ni到ng的路径代价可递归地定义为：C(ni,ng)=C(ni,nj)+C(nj,ng)。,2一般图搜索策略,2）一般图搜索算法：w参数s指示初始状态节点；G指示搜索图；OPEN作为存放待扩展节点的表；CLOSE作为存放已被扩展节点的表；SNS指示子节点集合；w操作MOVE-FIRST(OPEN)取OPEN表首的节点作为当前要被扩展的节点n，同时将节点n移至CLOSE表；w算法的执行划分为二个阶段：初始化建立只包括初始状态节点的搜索图，并设置OPEN和CLOSE表；搜索循环取出OPEN表首的节点加以扩展，将扩展出的子节点插入搜索图和OPEN表，并做适当的指针标记和修改工作，最后排序OPEN表。,2）一般图搜索算法：,w算法1）G:=s；/算法开始时搜索图只包括初始状态节点s；2）OPEN:=(s),CLOSE:=()；/OPEN表只包含作为待扩展节点，而CLOSE表为空；3）若OPEN是空表，则算法以失败结束；/因为此时未搜索到解答（目标状态），空表又使算法无法继续搜索；4）n:=MOVE-FIRST(OPEN)；5）若n是目标状态节点，则搜索成功结束，并给出解答路径；6）扩展节点n，将非节点n祖先的子节点置于子节点集合SNS中，并插入搜索图G中；7）标记和修改子节点指向父节点n的指针：8）按某种原则重新排序OPEN表中的节点；9）返回语句3）；,2）一般图搜索算法：,w通过循环地执行该算法，搜索图会因不断有新节点加入而逐步长大，直到搜索到目标节点。w扩展过程中某时刻的搜索图：参见图2.5。wOPEN表中的节点都是该搜索图的叶子节点，它们联合起来作用为一个多路开关。,2）一般图搜索算法：,w标记和修改指针：把SNS中的子节点分为三类：（1）全新节点，（2）已出现于OPEN表的节点，（3）已出现于CLOSE表的节点；/后二类子节点实际上意味着具有新、老二个父节点；加第1类子节点于OPEN表，并建立从子节点到父节点n的指针；比较第2类子节点经由新、老父节点到达初始状态节点s的路径代价，若经由新父节点的代价较小，则移走子节点指向老父节点的指针，改为指向新父节点n；对于第3类子节点作与第2类同样的处理，并把这些子节点从CLOSE表中移出，重新加入OPEN表；,2）一般图搜索算法：,w在搜索图中标记从子节点到父节点的指针，目的在于当搜索到目标状态时，能快速返回解答路径：自初始状态s到目标状态的一个节点序列。w搜索过程中的指针修改例(参见右图)：当前被扩展的节点为ni，它扩展出第1类子节点n1和n2,第2类子节点n4和第3类子节点n3。建立从子节点n1和n2到父节点ni的指针。节点n3和n4原指向父节点nj的指针都移走，改为指向节点ni。节点n3放回到OPEN表，而不是修改其子节点指针，起到了推迟修改的作用。,2一般图搜索策略,3）盲目搜索提高搜索效率的关键优化OPEN表中节点的排序方式。简单的排序策略按预先确定的顺序或随机地排序新加入到OPEN表中的节点。常用的简单方式：深度优先扩展当前节点后生成的子节点总是置于OPEN表的前端，即OPEN表作为栈表使用，后进先出，使搜索优先向纵深方向发展（图2.7（a）。宽度优先扩展当前节点后生成的子节点总是置于OPEN表的后端，即OPEN表作为排队表使用，先进先出，使搜索优先向横广方向发展（图2.7（b）。,3）盲目搜索,适用场合：深度优先当一个问题有多个解答或多条解答路径，且只须找到其中一个时；往往应对搜索深度加以限制。宽度优先确保搜索到最短的解答路径。共同优缺点：可直接应用一般图搜索算法实现，不需要设计特别的节点排序方法，从而简单易行，适合于许多复杂度不高的问题求解任务。节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态节点后才碰到解答，所以也称为盲目搜索。（参见图2.7）引入与应用领域相关的启发式知识来指导OPEN表中节点的排序，使最有希望出现在较短解答路径上的节点优先考察，就能显著提高搜索的有效性。用启发式知识指导排序可划分为二种方式:局部排序这是对于上述深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展。全局排序对OPEN表中的所有节点排序，使最有希望的节点排在表首。,3启发式搜索算法A,1）启发式搜索搜索是一种试探性的查寻过程，引入启发式知识可以减少搜索的盲目性，增加试探的准确性。应用启发式知识的搜索是启发式搜索。启发式知识对于搜索的指导作用可归纳为三方面：选择下一个要被扩展的节点，排序OPEN表中的待扩展节点是一种常用的方法。在扩展一个节点时，仅仅有选择性地生成部分有用的节点，而非所有可能的子节点。修剪掉某些估计不可能导致成功的子节点。,3启发式搜索算法A,2）算法A为应用第一方面的启发式知识设计体现启发式知识的所谓评价函数。计算每个节点的得分用于排列它们在OPEN表中的位置。评价函数f设计为：f(n)=g(n)+h(n)n搜索图中的某个当前被扩展的节点；f(n)从初始状态节点s,经由节点n到达目标节点ng，估计的最小路径代价（参见图2.8）；g(n)从s到n,估计的最小路径代价；h(n)从n到ng,估计的最小路径代价。算法A应用这种评价函数来实现启发式搜索的典型：g(n)值取至今已发现的自s到n的最短路径；h(n)值依赖于启发式知识来加以估算，h(n)称为启发式函数。,2）算法A,算法A的设计与前述一般图算法类同，主要的不同：算法第（6）句中增加了子节点函数f的计算，第（7）句中依赖于f值确定子节点指向父节点指针的修改，第（8）句中按f值从小到大排序OPEN表中的节点。算法A第（6）和第（7）句的修改：如上图所示。最佳优先(best-first)搜索策略f(n)值最小者排在首位，优先扩展。八数码游戏例f(n)=d(n)+w(n)d(n)当前被考察的节点n在搜索图中的节点深度，作为g(n)；w(n)其值是节点n与目标状态节点ng相比较，错位的棋牌个数，作为h(n),2）算法A,应用算法A的八数码问题（图2.2）搜索图:参见图2.9。OPEN和CLOSE表中的节点变化：参见表2.1。,4实现启发式搜索的关键因素,鉴于启发式搜索在提高搜索效率和解决组合爆炸问题中的作用，相关的研究成为人工智能形成和成长期的重要议题之一，也产生了许多成熟的研究成果，并且至今启发式搜索仍是一个活跃的研究领域。1）搜索算法的可采纳性(Admissibility)定义：在搜索图存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索算法总能找到最短（代价最小）的解答路径，则称算法具有可采纳性。宽度优先的搜索算法就是可采纳的，只是其搜索效率不高。评价函数f*(n)=g*(n)+h*(n)f*(n)当经由节点n的最短（代价最小）解答路径找到时实际的路经代价（长度）。g*(n)该路径前段（自初始状态节点到节点n）代价。h*(n)该路径后段（自节点n到目标状态节点）代价。在存在多个目标状态的情况下，h*(n)取h*(n，ngi)中最小者。评价函数f与f*相比较f(n)、g(n)和h(n)分别是f*(n)、g*(n)和h*(n)的近似值。,1）搜索算法的可采纳性(Admissibility),理想的情况：g(n)=g*(n),h(n)=h*(n),搜索过程中,每次都正确选择，不扩展任何无关的节点。g*(n)和h*(n)在最短解答路径找到前是未知的，故而几乎不可能设计出这种理想的评价函数；而且对于复杂的应用领域，即便是要设计接近于f*的f往往也是困难的。一般来讲，g(n)的值容易从迄今已生成的搜索树中计算出来，不必专门定义计算公式。例如就以节点深度d(n)作为g(n),并有g(n)g*(n)。然而，h(n)的设计依赖于启发式知识的应用。如何挖掘贴切的启发式知识是设计评价函数乃至算法A的关键。w(n)不够贴切，错误选用节点d加以扩展。p(n)更接近于h*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。p(n)比w(n)更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数）。应用启发式函数p(n)(而非w(n)的八数码问题搜索图：参见图2.10。算法A的可采纳性确保h(n)h*(n)的情况下，A可采纳，称为A*。宽度优先算法h(n)0h*(n)，确保搜索到最短路径。八数码游戏采用w(n)和p(n)作为启发式函数时，算法A都是可采纳的。,4实现启发式搜索的关键因素,2）启发式函数的强弱及其影响h(n)接近h*(n)的程度衡量启发式函数的强弱。h(n)h*(n)，差距较大时，h(n)过弱，OPEN表中节点排序的误差较大，产生较大的搜索图；h(n)h*(n),h(n)过强，算法A失去可纳性，不能确保找到最短解答路径。恒等于h*(n)的h(n)最理想，但无法设计。设计接近、又总是h*(n)的h(n)应用A*算法搜索问题解答的关键。算法A1和A2，若总有h1(n)h2(n)h*(n)，则t(A2)t(A1)。w(n)p(n)h*(n),采用p(n)扩展出的节点总数t(w(n)。宽度优先法解决八数码问题，h(n)0，搜索树庞大得多。3）设计h(n)的实用考虑设计接近、又总是h*(n)的h(n)的问题：随着问题求解任务复杂程度的增加,设计变得更困难，往往会导致在h(n)上的繁重计算工作量。搜索代价高居不下路径选择代价随h(n)的计算开销而大增。,3）设计h(n)的实用考虑,删除h(n)h*(n)的约束，使h(n)易于设计，但丢失可采纳性：在许多实用场合，人们并不要求找到最优解答（最短解答路径）；通过牺牲可纳性来换取h(n)设计的简化和减少计算h(n)的工作量。对评价函数f(n)=g(n)+h(n)作分析：h(n)0倾向于先进入OPEN表的节点会优先被考察和扩展，先进入的节点n往往具有较小的g(n)值，接近于宽度优先的搜索策略；g(n)0,倾向于后进入OPEN表的节点会优先被考察和扩展，后进入的节点n往往更接近于目标状态，即h(n)值较小，接近于深度优先的搜索策略。评价函数f(n)=g(n)+wh(n)，w用作加权：搜索图的浅层（上部）让w取较大值，使g(n)所占比例很小，突出启发式函数的作用，加速向纵深方向搜索；搜索到较深的层次让w取较小值，以使g(n)所占比例很大，并确保wh(n)h*(n),搜索向横广方向发展，寻找到较短的解答路径。,5回溯策略和爬山法,简单的搜索策略：g(n)0,f(n)=h(n),局部排序只排序新扩展出来的子节点；简单易行，适用于不要求最优解答的问题求解任务。1）爬山法实现启发式搜索的最简单方法。类似于人爬山只要好爬，总是选取最陡处，以求快速登顶。求函数极大值问题非数值解法，依赖于启发式知识，试探性地逐步向顶峰逼近。适用于能逐步求精的问题。爬山法特点：只能向上，不准后退，从而简化了搜索算法；体现在：从当前状态节点扩展出的子节点中，将h(n)最小的子节点（对应于到顶峰最近的上爬路径）作为下一次考察和扩展的节点，其余子节点全部丢弃。不需设置OPEN和CLOSE表，因为没有必要保存任何待扩展节点；爬山法对于单一极值问题（登单一山峰）十分有效而又简便，对于具有多极值的问题无能为力会错登上次高峰：不能到达最高峰。,5回溯策略和爬山法,2）回溯策略可以有效地克服爬山法面临的困难保存了每次扩展出的子节点，并按h(n)值从小到大排列。相当于爬山的过程中记住了途经的岔路口路径搜索失败时回溯（后退），向另一路径方向搜索（参看图2.11）。递归过程实现回溯策略的有效方式：算法就取名为BACKTRACK(n),参数n为当前被扩展的节点，初次调用时n即为初始状态节点s；分二个部分：*判断当前节点n的状态，*作搜索工作扩展节点n，递归调用该算法，处理返回结果。三种失败状态：不合法状态（如传教士和野人问题中所述的那样），旧状态重现（如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环），状态节点深度超过预定限度（例如八数码游戏中，指示解答路径不超过6步）。,2）回溯策略,回溯条件搜索进入“死胡同”，由该算法的第(4)句定义。失败状态，由算法第（2）句指示，第（7）句执行回溯。解答路径的生成从相应于目标状态节点的空表开始，递归返回PATH。,2）回溯策略,影响回溯算法效率的关键因素回溯次数：回溯搜索到失败状态时的一种弥补行为，准确选择下一步搜索考察的节点大幅度减少甚至避免回溯。设计好的启发式函数h(n)是至关重要的。四皇后问题例：国际象棋棋盘的一个44区域放置四个皇后棋子，并满足约束：每行、每列和对角线上只允许出现一个皇后，以避免皇后间发生冲突。问题状态用列表L指示，L的元素就是皇后在棋盘中的位置ij(1i，j4).为简化解答的搜索，限定按自上而下的次序在棋盘的4行中放置皇后。空表L指示初始状态；当表L包含4个满足约束的皇后位置时，到达目标状态；当皇后位置发生冲突时，意味着进入不合法状态（失败状态）。设计D(n)作为启发式函数h(n)其值为状态n下最新一个皇后位置（棋盘格子）所在的长对角线的长度（对角线上格子的个数）。四皇后问题搜索图：参见图2.12和图2.13。,2）回溯策略,减少回溯次数：应用D(n)二次回溯，深度优先每次将新产生的子节点按随机次序或固定顺序（按格子在同一行中的先后顺序）排序，这种盲目搜索面临多得多的回溯。,6状态空间抽象和生成-测试法,支持大型状态空间的有效搜索。1）状态空间抽象减少搜索量的重要技术，适合寻找令人满意的解答，将状态空间按子问题进行划分子问题构成抽象空间。抽象空间中的搜索步与实际状态空间的对应关系：参见图2.14前者中的一个搜索步(一个子问题)对应于后者中的许多步，因而抽象空间小得多，使搜索大幅度加快。驾驶汽车长途旅行例：决定大致的行走路线通过全国交通图，决定每一段大致路线的详细行程通过沿途城市的交通详图。状态空间抽象的本质将搜索的注意力集中于问题求解的重要因素。复杂的问题可采用多级抽象。,6状态空间抽象和生成-测试法,2）生成测试法搜索过程由两个部件合作完成：可能解的生成器，修剪不正确解答的测试器；生成器的性能取决于完备性和无冗余性，即能生成所有可能解并只生成一次。生成器和测试器的工作往往需交替进行。关键问题在生成器和测试器之间分配知识。知识丰富的生成器会导致较高的搜索效率。分层的生成-测试法：参见图2.15整个问题求解过程可视为不断搜索部分解答的过程，每一层的生成测试法服务于搜索一个部分解答，解答分类，分类树；分层的目的在于设计强有力的测试器，尽量早期地(在搜索树上层)删除不合适的候选解，大幅度减少搜索量。,7启发式搜索的适用性讨论,启发式搜索的评价函数均可设计为全局或局部的评价器。启发式搜索已较少用于作为人工智能系统的顶层控制结构。启发式搜索技术的应用面临三个关键选择：确定性或非确定性搜索方式；搜索目标状态本身还是达到目标状态的解答路径(往往表示为状态或操作算子序列)；搜索一个还是全部或最优解答。无论是最佳优先或深度优先加回溯，都是十分低效率的。避免回溯成为人工智能研究的重要课题，研究明显地向确定性方式倾斜。,22问题归约,问题归约是人求解问题常用的策略：把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解：只有当这些子问题全部解决时，问题才算解决，问题的解答由子问题的解答联合构成。问题归约可以递归地进行，直到把问题变换为本原问题的集合。本原问题不可或不需再通过变换化简的“原子”问题。主要内容：问题归约的描述与或图搜索与或图的启发式搜索,2.2.1问题归约的描述,广义的状态空间搜索技术，状态空间同样可表示为二元组：SP=(S,O)问题状态可以通过子问题状态的联合加以表示，操作算子的执行导致问题的变换,三种情况：状态变迁导致问题从上一状态变迁到下一状态,问题分解分解问题为需同时处理的子问题，但不改变问题状态。基于状态变迁的问题分解先导致状态变迁，再实现问题分解，实际上就是前二个操作的联合执行。字母重写问题例：初始状态为字母列表（ABC），目标状态为只包含字母x、y、z的字母列表，提供二类操作算子：面向问题分解Split(n),面向状态变迁字母列表的重写规则。,2.2.1问题归约的描述,与或图应用问题归约策略得到的状态空间图：参见图2.16逻辑“与”关系用园弧将几条节点间关联弧连接在一起，指示问题分解为子问题，子问题全部解决才会导致问题的解决，子问题的状态描述联合起来构成问题状态的描述。逻辑“或”关系：问题的分解可以有多种方式，对应于问题（子问题）可能激活多条重写规则；只要有一种分解方式或激活的规则能导致最终的解答成功即可；导致多个可能的解答。,2.2.1问题归约的描述,面向状态变迁的操作和面向问题分解的操作合并：基于状态变迁的问题分解操作，获得更为紧凑的问题归约描述，参见图2.17。子问题求解的排序:子问题相互独立，可按任意次序进行;复杂问题，子问题仅相对独立，排序是重要的。更多的例子（原理简单，方法有效，应用广泛）：梵塔问题（图2.18）符号积分问题（SAINT）分子结构识别问题（DENDRAL）,2.2.1问题归约的描述,123123,ABC,2.2.2与或图搜索,与或图视为对一般图(或图)的扩展；与或图也有根节点，用于指示初始状态；同父子节点间可以存在“与”关系，父、子节点间不能简单地以弧线关联，需要引入超连接概念；解答路径往往不复存在，代之以广义的解路径解图。与或图搜索的基本概念：参见图2.19K-连接表示从父节点到子节点间的连接：也称为父节点的外向连接，以园弧指示同父子节点间的“与”关系，K为这些子节点的个数，K1时成为超连接，一个父节点可以有多个外向的K-连接。当所有超连接的K都等于1时，与或图蜕化为一般图。,2.2.2与或图搜索,根、叶、终节点无父节点的节点根节点，用于指示问题的初始状态；无子节点的节点叶节点。用于联合表示目标状态的节点终节点，终节点必定是叶节点，反之不然；解图的生成自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。解图纯粹是一种“与”图；搜索到多个解图（图2.20），由于与或图中存在“或”关系；解图应无环，即任何节点的外向连接均不得指向自己或自己的先辈，否则会使搜索陷入死循环。,2.2.2与或图搜索,2.2.3与或图的启发式搜索,需求分析引入应用领域的启发式知识去引导搜索过程，与或图中搜索的是解图，估算评价函数f(n)的第1分量g(n)没有意义，只须估算第2分量h(n)，h(n)是对最小解图代价的估计，会同时出现多个候选的待扩展局部解图，选择一个可能代价最小的用于下一步搜索。解图代价的递归方式估算，父节点n的由外向K-连接指向的子节点：n1，n2，nkf(n)=K+h(n1)+h(n2)+h(nk)比直接基于h(n)估算而得出的f(n)值更为准确。如此，可以计算出更为准确的f(n0),即整个局部解图的可能代价。,2.2.3与或图的启发式搜索1与或图的启发式搜索算法AO*,w参数G指示搜索图，G指示被选中的待扩展局部解图，LGS指示候选的待扩展局部解图集，n0指示根节点，即初始状态节点，n指示被选中的待扩展节点，fi(n0)是第i个候选的待扩展局部解图的可能代价。w算法的执行划分为二个阶段：初始化建立只包括初始状态节点的搜索图；搜索循环选择和扩展局部解图，精化解图代价的估计，传递节点的能解性。,1与或图的启发式搜索算法AO*,w算法（1）G:=n0，LGS为空集；（2）若n0是终节点，则标记n0为能解节点；否则计算f(n0)=h(n0),并把G作为0号候选局部解图加进LGS；（3）n0标记为能解节点，则算法成功返回；（4）若LGS为空集，则搜索失败返回；否则从LGS选择fi(n0)最小的待扩展局部解图作为G；（5）G中选择一个非终节点的外端节点（尚未用于扩展出子节点的节点）作为n；（6）扩展n，生成其子节点集，并从中删去导致有环的子节点以及和它们有“与”关系的子节点；若子节点集为空，则n是不能解节点，从LGS删去G(因为G不可能再扩展为解图)；否则，计算每个子节点ni的f(ni),并通过建立外向K-连接将所有子节点加到G中；（7）若存在j个（j1）外向K-连接,则从LGS删去G，并将j个新局部解图加进LGS；（8）G中或在取代G的j个新局部解图中用公式f(n)=K+h(n1)+h(n2)+h(nk)的计算结果取代原先的f(n)，并传递这种精化的作用到fi(n0)（i=1,2,j）；同时将作为终节点的子节点标记为能解节点，并传递节点的能解性。（9）返回语句（3）。,与或图的启发式搜索算法AO*,2.2.3与或图的启发式搜索2算法应用的若干问题,从局部解图中选择加以扩展的节点与或图搜索的是解图而非解路径，选择f(n)=h(n)的值最小的节点加以扩展并不一定会加速搜索过程，应选择导致解图代价发生较大变化的节点优先加以扩展，使搜索的注意力快速地聚焦到实际代价较小的候选解图上。简单情况下，可随机选择加以扩展的节点。AO*算法的可采纳性AO*算法是可采纳的当某与或图存在解图时，应用AO*算法一定能找出代价最小的解图。AO*算法的应用要求遵从的约束：总能满足h(n)h*(n),h*(n)是实际的代价最小解图找到时解图的代价，确保h(n)满足单调限制条件:h(n)K+h(n1)+h(n2)+h(nk)，粗略的估计总是不超过细致的计算。,2算法应用的若干问题,算法AO*与A*的比较解图解答路径，估算代价最小的局部解图加以优先扩展解答路径，只考虑评价函数f(n)的分量h(n)同时计算分量g(n)和h(n)，应用LGS存放候选的待扩展局部解图，并依据fi(n0)值排序应用OPEN表和CLOSE表分别存放待扩展节点和已扩展节点，并依据f(n)值排序。解图代价的重复计算某些子节点可能会有多个父节点，这种子节点到终节点集合解图的代价在计算自根节点n0出发的解图时被重复累计。,2.3基于归结的演绎推理,人的问题求解行为更像是一个解答识别过程而非解答搜索过程：识别解答或部分解答依赖于应用领域特有的知识，符号推理则成为基于知识来求解问题的主要手段。符号推理的重要方式是演绎推理：它的基础为谓词演算一种形式语言，将各种陈述性（说明性）的描述以形式化的方式表示，以便对它们作处理。谓词演算人工智能系统最常用的知识表示方法：广泛地应用于各种人工智能系统的设计，谓词演算（或更广义地，形式逻辑）是人工智能研究的重要基础之一。主要内容：谓词演算H域和海伯伦定理归结原理归结反演,2.3基于归结的演绎推理1谓词演算,1）一阶谓词演算的基本概念符号和符号结构符号符号结构的组成成分物理符号系统，纽厄尔和西蒙可将符号表示为字符串，作为事物的标识符号结构描述事物间的相关方式Inroom(Robot,R1)谓词公式形如Inroom(Robot，R1)的符号结构称为谓词公式。谓词公式的一般形式是：P(x1,x2,xn)P谓词符号（简称谓词），xi(i=1,2,n)参数项（简称项），项可以是常量、变量或函数。P(x1,x2,xn)表示了一个n元谓词公式Inroom(Robot，R1)Married(father(L1),x),1谓词演算1）一阶谓词演算的基本概念,为避免混淆和增加表示的清晰性，规定：谓词和常量以首字母大写的形式来表示，函数和变量以小写字母的形式表示。变量值均取定时，每个谓词公式均有一个确定的真值：T或F。谓词公式是谓词演算的基本单元，也称为原子公式。连词和量词通过引入连词和量词，可以把原子公式组合为复合谓词公式。复合谓词公式称为逻辑语句，谓词演算也称为谓词逻辑。连词（非）、（与）、（或）、（蕴涵，）、（等价，）。连词例：Inroom(Robot,R2)Isa(Liming,Student)Lives(Liming,House-1)Color(House-1,White)Isa(Wang,Teacher)Isa(Wang,Officer)At(Liming,School)At(Wang,School)At(Liming,School)At(Wang,School),1）一阶谓词演算的基本概念,连词相关的术语：否定也叫做取反，谓词公式前面加连词；合取用连词连接谓词公式，产生的逻辑语句称为合取式，其每个成份称为合取项；析取用连词连接谓词公式，产生的逻辑语句称为析取式，其每个成份称为析取项；蕴涵式用连词连接谓词公式而产生，连词左部称为前项，右部称为后项；等价式用连词连接二个谓词公式而产生，视为正、逆向二个蕴涵式的合取。,1）一阶谓词演算的基本概念,命题不包含变量的谓词公式和逻辑语句命题演算基于命题的谓词演算，谓词演算的子集缺乏有效的表达能力去表示一般性概念，如“条条大路通罗马”。为扩大命题演算能力，就需要引入变量和有关的表示方式。量词表示对变量的处理：全称量词以符号（x）P(x)来表示对于某个论域中的所有（任意一个）个体x,都有P(x)真值为T。存在量词以符号（x）P(x)来表示某个论域中至少存在一个个体x，使P(x)真值为T。P(x)是任意逻辑语句，也称作量词的管辖范围（简称辖域，使用括号界定）。量词例：,1）一阶谓词演算的基本概念,（x）Robot(x)Color(x,Gray),所有机器人都是灰色的；（x）Road(x)Lead(x,Roma),条条大路通罗马；（x）Isa(x,Robot)Inroom(x,R1),至少有一个机器人在房间R1中；（x）（y）Person(x)Book(y)Give(Mary,x,y)，Mary给每个人一本书。（x）Person(x)Give（Mary,x,y）,Mary给每人某个同样的东西。量词的约束变量（或称变元），其取值仅在量词的辖域内有效；不同辖域内的同名约束变量相互独立。自由变量，相对性：（y）P(y)（x）Q(x,y)一阶谓词演算若限定不允许对谓词、连词、量词和函数名进行量化处理，且参数项不能是谓词公式，则这样的谓词演算是一阶的。一阶谓词演算不允许在谓词、连词、量词和函数名的出现位置上使用变量。（P）P(A)、Married(y(L1),Mary)、P(x,Q(y)本书中所用到的谓词演算均是一阶的。,1谓词演算2）合适公式,合适公式的定义递归方式的定义：1)单一谓词公式（即原子公式）是合适公式；2)若A是合适公式，则A也都是合适公式；3）若A和B都是合适公式，则AB、AB、AB和AB也都是合适公式；4）若A是合适公式，x是约束变量，则（x)A和（x)A也都是合适公式;5）只有按上述规则（1）至（4）求得的公式，才是合适公式。连词优先级别是，、，、，但可通过括号改变优先级。形式化表示符号推理所需的知识所有人都喜欢一种游戏（x）（y）Person(x)Game(y)Like(x,y)合适公式的解释命题解释给命题中包含的各个原子公式指派真值（T或F）。求出命题的真值（T或F）依据连接原子公式的连词的作用。,2）合适公式,谓词逻辑涉及变量和函数，不可能直接给原子公式指派真值：定义一个拟观察个体的可能论域，确定原子公式中变量项和函数项在论域中的取值，给原子公式指派真值。例子合适公式（x）（y）P(x)Q(f(x),y)的一个解释随意设定一个论域：D=1，2对于x的每个取值，可以指派f(1)=2,f(2)=2,P(1)=T,P(2)=T；对于f(x)和y的每个取值组合（只有2个：2，1；2，2）指派Q(2,1)=T,Q(2,2)=F。这些指派就确定了该合适公式的一个解释。在这个解释下，合适公式有真值T。,2）合适公式,合适公式的永真性和可满足性1）合适公式的永真性若某合适公式P对于某论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域上均永真，则称P是永真的。2）合适公式的可满足性对于合适公式P，若在论域D上至少可以建立一个解释，使P有真值T，则称P在D上是可满足的；若至少有一个论域使P可满足，则称P是可满足的。3）合适公式的永假性若某合适公式P对于论域D上的所有可能的解释都有真值F，则称P在D上是永假的(即不可满足的)；若P在每个可能的非空论域上均永假，则称P是永假的。论域个数较多，每个论域较大，且解释的个数有限时，可以判定；解释的个数无限时，不能确保可以判定，或者不能确保在有限的时间内判定。,2）合适公式合适公式的性质：十个常用性质,1谓词演算3）合适公式的标准化,标准化需求常见的基于谓词演算的推理有归结反演和规则演绎。要求以所谓的量词前束范式来表示合适公式，（Q1x1）（Q2x2）（Qkxk）MM称为母式，不包括任何量词，量词前束，Qi可以是量词符号或，xi是量词的约束变量。归结反演要求母式M标准化为合取范式：M=W1W2WnWi=Li1Li2Lim(i=1,2,n)Lij=Pij|Pij(j=1,2,m)/Lij称为文字析取范式（与合取范式对偶）：M=W1W2WnWi=Li1Li2Lim(i=1,2,n)Lij=Pij|Pij(j=1,2,m),3）合适公式的标准化,合取范式的标准化过程应用合适公式性质将公式逐步转化对转化过程步骤的顺序并无严格的规定，遵从一个合理顺序可以降低化简的困难和减少差错。一个较合理的化简过程，分8个步骤：例子：,2H域和海伯伦定理,定理的自动证明一般表示形式为：F1,F2,Fn|=WF1,F2,Fn都是合适公式，公式间隐含合取关系，构成一个公式集（也称公理集或事实集），W是待证明的一个合适公式（也称为定理或目标公式）。证明的方法可分二大类：演绎法直接证明F1F2FnW为永真；从而，当公式集为真时，定理W成立。反证法间接证明(F1F2FnW)为永假。即证明F1F2FnW的永假性，即F1,F2,FnW是一个矛盾集。海伯伦提出的H域（海伯伦域）和海伯伦定理为自动定理证明奠定了理论基础：将合适公式标准化为子句集，引入H域（即海伯伦域），从理论上给出了证明子句集(从而合适公式)永假(即不可满足)的可行性及方法。鲁宾逊提出的归结原理使机器定理证明成为可能。,2H域和海伯伦定理1）子句和子句集,子句仅由文字的析取构成的合适公式（文字：原子谓词公式或其取反）。合取范式子句的合取。子句集指示合取范式，子句间隐含合取关系。例子：变量换名P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z)P(A)，P(y)Q(A,z)P(z,g(z)，P(f(A,y)Q(A,z)P(z,g(z)P(A)，P(y1)Q(A,z1)P(z1,g(z1)，P(f(A,y2)Q(A,2)P(z2,g(z2)重要性质一个合适公式F化简为标准化的子句集S时，S的不可满足成为F永假的充分必要条件。F和S并非等价F的化简过程中，为消除存在量词而引入了Sklem函数，使子句集S只是F的一个特例。可以证明F和S在永假性上等价建立海伯伦定理的重要基础。,2H域和海伯伦定理2）H域(海伯伦域）,H域的迭代构造：（S：子句集，D：S的某个论域）(1)令H0是S中出现的所有常量的集合，若S中未出现常量，就任取常量aD,并令H0=a。(2)令Hi+1=Hi出现于S中的函数在Hi上的所有实例,i=1,2,；形如f(x1,x2,xn)的函数的实例通过让xj=kjHi来形成（j=1,2,n）。Hi可以迭代扩展到H，称为海伯伦域，简称H域（一个可数无穷集）。例子,2）H域(海伯伦域）,2）H域(海伯伦域）,H域上的原子谓词公式实例集A（为研究子句集的永假性）:A=所有出现于S中原子谓词公式的实例。命题（不包含变量）其实例就是其本身；P(t1,t2,tm)其实例通过让ti=kiH(即H)来形成；例子：子句集S=P(x)R(f(x),Q(y,g(y)A=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a),；H=a，f(a),g(a),f(g(a),g(f(a),f(f(a),g(g(a),基原子A中的元素，是原子命题；A称为基原子集。,2）H域(海伯伦域）,I*子句集在H域上的一个解释，通过基原子集来建立：给集中的每个基原子指派一个真值（T或F）。以基原子自身指示取真值T，前面加取反符号指示取真值F,例子：（子句集S=P(x)R(f(x),Q(y,g(y)）I1*=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a)I2*=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a)I3*=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a)A=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a),；定理对于子句集S的任一可能论域D上的任一解释I,总能在S的H域上构造一个相应的解释I*,使子句集具有相同的真值。子句集不可满足确定子句集S在H域上的所有解释都不满足。,2H域和海伯伦定理3）H域上解释的语义树,用语义树来形象地描述子句集在H域上的可能解释命题集基原子集是有限集:每个基原子只可能有二个真值（T或F)，容易画出完整的语义树。例子只包含原子命题公式P、Q和R的子句集：基原子集A=P、Q、R，语义树。从树根节点n0到叶子节点n的路径指示一个解释记为I(n)，表示为路径上标记的集合，每个标记是一个文字。I(n32)=P,Q,R从树根节点n0到叶子节点n32的路径。一般的子句集，H是可数无穷集，语义树可能成为一棵无穷树。,3）H域上解释的语义树,封闭语义树子句集不可满足时，语义树有穷，语义树上的所有路径都分别对应一个导致子句集不满足的解释。例子：子句集S=P(x)Q(f(x),P(a),Q(y)H=a,f(a),f(f(a),A=P(a),Q(a),P(f(a)，Q(f(a),3）H域上解释的语义树,基子句变量用H域中元素取代后的子句，即基文字（基原子或其取反）或基文字的析取。当x=a时，从子句P(x)Q(f(x)生成基子句P(a)Q(f(a)。语义树中每一导致子句集S不满足的路径（相应于H域上一解释）都至少引起一个基子句真值为F。I(n42)=P(a),Q(a),P(f(a),Q(f(a)就引起了基子句P(a)Q(f(a)真值为F。当建立起一棵封闭语义树时，实际上也建立了一个由有限个不可同时满足的基子句构成的集合SS=P(a)Q(f(a),P(a),Q(a),Q(f(a)4）海伯伦定理子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S。子句集S不可满足封闭语义树有限的不可满足的基子句集S。基于海伯伦定理法的自动定理证明面临的主要困难：子句集的不可满足性是不可判的，计算量往往很大。,3归结原理,动机尽管海伯伦提出的H域（即海伯伦域）和海伯伦定理，为自动定理证明奠定了理论基础；但并未提供有效的操作化方法。为提高判定子句集不可满足的有效性，鲁宾逊于1965年提出了归结(Resolution)原