我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 语义树 >

人工智能基础(第2版)-高济-第二章ppt

归档日期:06-15       文本归类:语义树      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第二章 问题求解的基本方法 ? 开发人工智能技术的一个主要目的——解决非平凡问题: ? 难以用常规(数值计算、数据库应用等)技术直接解决, ? 求解依赖于问题本身的描述和应用领域的相关知识。 ? 按所需的领域特有知识的多寡,问题求解系统可以划分为两大类: ? 知识贫乏系统——依靠搜索技术去解决问题,但因知识贫乏而缺乏针对性,效率往往低下。 ? 知识丰富系统——借助于作试探性推理的识别技术,通过基于领域知识的匹配检查去识别解答,直接了当。 ? 大多数KB(Knowledge Based)系统均采用包括推理的识别技术。 ? 二大类搜索技术:一般图搜索、基于问题归约的与或图搜索。 ? 二种经典的逻辑推理技术:基于归结的谓词演算、基于规则的演绎推理。 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 + c ≦2, m ≧ c。 ? 左岸状态描述为一个三元组: (m, c, b) ? 考虑到在这个渡河问题中,左岸的状态描述(m, c, b)可以决定右岸的状态,所以整个问题状态就可以左岸的状态来描述,以简化问题的表示。 ? 设初始状态下传教士、野人和船都在左岸,目标状态下这三者均在右岸,问题状态以三元组(m,c,b)表示。 2)状态空间表示的经典例——传教士和野人问题 ? 问题求解任务可描述为: (3,3,1) → (0,0,0) ? 该简单问题的状态空间: ? 可能的状态总数为4×4×2 = 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——问题的初始状态,I ∈ S; ? G——问题的目标状态集,G ? S。 ? 基本思想——通过搜索引擎寻找一个操作算子的调用序列,使问题从初始状态变迁到目标状态之一。 ? 解答路径——初-目变迁过程中产生的状态序列或相应的操作算子调用序列。 ? 搜索引擎——可以设计为任意实现搜索算法的控制系统。 ? 状态空间的解答路径有多条,由于一个状态可以有多个可供选择的操作算子: 渡河问题就有无数条解答路径(因为划船操作可逆),但只有4条是最短的,都包含11个操作算子的调用。 ? 状态空间一般都表示为或图——也称一般图 操作算子的可选(渡河问题的初始状态节点就有3个),在逻辑上称为“或”关系,意指只要其中有一条路径通往目标状态,就能获得成功解答。除了少数像渡河这样的简单问题外,描述状态空间的一般图都很大,无法直观地画出,只能将其视为隐含图。 ? 搜索图——在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线,构成所谓的搜索图。 1 状态空间及其搜索的表示 4)一般图搜索例——八数码游戏 ? 3×3九宫棋盘,放置数码为1 - 8的8个棋牌,剩下一个空格,只能通过棋牌向空格的移动来改变棋盘的布局。 ? 求解的问题——给定初始布局(即初始状态) 和目标布局(即目标状态),如何移动棋牌才 能从初始布局到达目标布局(参见图2.2)。 ? 解答路径——就是一个合法的走步序列。 ? 用一般图搜索方法解决该问题: ? 为问题状态的表示建立数据结构:3×3的一个矩阵, * 矩阵元素S ij∈{0,1,…,8};其中1≤i,j≤3, * 数字0指示空格, * 数字1 - 8指示相应棋牌。 1 0 3 1 2 3 ? 图2.2中的八数码问题就可表示为: 7 2 4 ? 8 0 4 6 8 5 7 6 5 4)一般图搜索例——八数码游戏 ? 制定操作算子集: * 直观方法——为每个棋牌制定一套可能的走步: 左、上、右、下四种移动, 这样就需32个操作算子。 * 简易方法——仅为空格制定这4种走步, 因为只有紧靠空格的棋牌才能移动。 * 空格移动的唯一约束是不能移出棋盘。 ? 八数码问题的搜索图: 参见图2.3 ? 棋盘布局(问题状态)总共9!=362880个, 但搜索图小得多。 1 状态空间及其搜索的表示 5)状态空间、搜索图和 解答路径之间的关系: ? 对于状态空间很大的问题: ?设计搜索策略的关键考虑 是解决组合爆炸问题。 ? 解决组合爆炸问题的方法 ?实际上就是选用好的搜索策 略,使得只要搜索状态空间 的很小部分就能找到解答。 2? 一般图搜索策略 1)搜索术语(引自图论): ? 节点深度——搜索图是一种有根图,根节点指示初始状态,令其节点深度 为0,则搜索图中的其它节点的深度d n就可递归地定义为其父节点深度d n-1加1: dn = d n-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表只包含s作为待扩展节点, 而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。 w OPEN表中的节点都是该搜索图的叶子节点,它们联合起来作用为一个多路开关。 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) ≡ 0 < h*(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)是至关重要的。 四皇后问题例: 国际象棋棋盘的一个4×4区域放置四个皇后棋子,并满足约束:每行、每列和对角线上只允许出现一个皇后,以避免皇后间发生冲突。 问题状态——用列表L指示,L的元素就是皇后在棋盘中的位置ij(1≤i,j≤4). 为简化解答的搜索,限定按自上而下的次序在棋盘的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 启发式搜索的适用性讨论 启发式搜索的评价函数均可设计为全局或局部的评价器。 启发式搜索已较少用于作为人工智能系统的顶层控制结构。 启发式搜索技术的应用面临三个关键选择: 确定性或非确定性搜索方式; 搜索目标状态本身还是达到目标状态的解答路径(往往表示为状态或操作算子序列); 搜索一个还是全部或最优解答。 无论是最佳优先或深度优先加回溯,都是十分低效率的。 避免回溯成为人工智能研究的重要课题,研究明显地向确定性方式倾斜。 2.2 问题归约 问题归约是人求解问题常用的策略: 把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解: 只有当这些子问题全部解决时,问题才算解决, 问题的解答由子问题的解答联合构成。 问题归约可以递归地进行,直到把问题变换为本原问题的集合。 本原问题——不可或不需再通过变换化简的“原子”问题。 主要内容: 问题归约的描述 与或图搜索 与或图的启发式搜索 2.2.1 问题归约的描述 广义的状态空间搜索技术, 状态空间同样可表示为二元组: SP = ( S, O ) 问题状态可以通过子问题状态的联合加以表示, 操作算子的执行导致问题的变换,三种情况: 状态变迁——导致问题从上一状态变迁到下一状态, 问题分解——分解问题为需同时处理的子问题,但不改变问题状态。 基于状态变迁的问题分解——先导致状态变迁,再实现问题分解,实际上就是前二个操作的联合执行。 字母重写问题例: 初始状态为字母列表(A B C), 目标状态为只包含字母x、y、z的字母列表, 提供二类操作算子: 面向问题分解——Split(n), 面向状态变迁—字母列表的重写规则。 2.2.1 问题归约的描述 与或图——应用问题归约策略得到的 状态空间图:参见图2.16 逻辑“与”关系——用园弧将几条节点 间关联弧连接在一起, 指示问题分解为子问题, 子问题全部解决才会导致问题的 解决, 子问题的状态描述联合起来构成 问题状态的描述。 逻辑“或”关系: 问题的分解可以有多种方式, 对应于问题(子问题)可能激活 多条重写规则; 只要有一种分解方式或激活的规 则能导致最终的解答成功即可; 导致多个可能的解答。 2.2.1 问题归约的描述 面向状态变迁的操作和面向问题分解的操作合并: 基于状态变迁的问题分解操作, 获得更为紧凑的问题归约描述, 参见图2.17。 子问题求解的排序: 子问题相互独立,可按任意次序进行; 复杂问题,子问题仅相对独立,排序是重要的。 更多的例子 (原理简单,方法有效, 应用广泛): 梵塔问题(图2.18) 符号积分问题(SAINT) 分子结构识别问题 (DENDRAL) 2.2.1 问题归约的描述 2.2.2 与或图搜索 与或图视为对一般图(或图)的扩展; 与或图也有根节点,用于指示初始状态; 同父子节点间可以存在“与”关系,父、 子节点间不能简单地以弧线关联,需要 引入超连接概念; 解答路径往往不复存在,代之以广义的 解路径——解图。 与或图搜索的基本概念: 参见图2.19 K-连接——表示从父节点到子节点间的连接: 也称为父节点的外向连接, 以园弧指示同父子节点间的“与”关系, 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,…nk f(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都是合适公式,则A∧B、A∨B、A?B和A?B也都是合适公式; 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。 这些指派就确定了该合适公式的一个解释。 在这个解释下,合适公式有线)合适公式 合适公式的永线)合适公式的永真性 若某合适公式P对于某论域D上的所有可能的解释都有真值T,则称P在D上是永真的;若P在每个可能的非空论域上均永线)合适公式的可满足性 对于合适公式P,若在论域D上至少可以建立一个解释,使P有真值T,则称P在D上是可满足的;若至少有一个论域使P可满足,则称P是可满足的。 3)合适公式的永假性 若某合适公式P对于论域D上的所有可能的解释都有真值F,则称P在D上是永假的(即不可满足的);若P在每个可能的非空论域上均永假,则称P是永假的。 论域个数较多,每个论域较大,且解释的个数有限时,可以判定; 解释的个数无限时,不能确保可以判定,或者不能确保在有限的时间内判定。 2)合适公式 合适公式的性质:十个常用性质 1谓词演算 3)合适公式的标准化 标准化需求 常见的基于谓词演算的推理有归结反演和规则演绎。 要求以所谓的量词前束范式来表示合适公式, (Q1x1)(Q2x2)…(Qkxk )M M称为母式,不包括任何量词, 量词前束,Qi 可以是量词符号? 或?,xi 是量词的约束变量。 归结反演要求母式M标准化为合取范式: M = W1∧W2∧…∧Wn Wi = Li1∨Li2∨…∨Lim (i=1,2,…,n) Lij= Pij ?Pij (j=1,2,…,m) // Lij称为文字 析取范式(与合取范式对偶): M = W1∨W2∨…∨Wn Wi = Li1∧Li2∧…∧Lim (i=1,2,…,n) Lij= Pij ?Pij (j=1,2,…,m) 3)合适公式的标准化 合取范式的标准化过程 应用合适公式性质将公式逐步转化 对转化过程步骤的顺序并无严格的规定, 遵从一个合理顺序可以降低化简的困难和减少差错。 一个较合理的化简过程,分8个步骤: 例子: 2 H域和海伯伦定理 定理的自动证明一般表示形式为: {F1, F2,… ,Fn}= W F1, F2,… ,Fn都是合适公式, 公式间隐含合取关系,构成一个公式集(也称公理集或事实集), W是待证明的一个合适公式(也称为定理或目标公式)。 证明的方法可分二大类: 演绎法——直接证明F1∧F2∧…∧Fn ? W为永真;从而,当公式集为真时,定理W成立。 反证法——间接证明?(F1∧F2∧…∧Fn ? W)为永假。即证明 F1∧F2∧…∧Fn ∧?W的永假性,即{F1, F2,… ,Fn} ∪{?W}是一个矛盾集。 海伯伦提出的H域(海伯伦域)和海伯伦定理——为自动定理证明奠定了理论基础: 将合适公式标准化为子句集, 引入H域(即海伯伦域),从理论上给出了证明子句集(从而合适公式)永假(即不可满足)的可行性及方法。 鲁宾逊提出的归结原理——使机器定理证明成为可能。 2 H域和海伯伦定理 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的化简过程中,为消除存在量词而引入了Sk?lem函数,使子句集S只是F的一个特例。 可以证明F和S在永假性上等价——建立海伯伦定理的重要基础。 2 H域和海伯伦定理 2)H域(海伯伦域) H域的迭代构造:(S:子句集,D:S的某个论域) (1) 令H0 是S中出现的所有常量的集合,若S中未出现常量,就任取常量a?D,并令H0 ={a}。 (2) 令Hi+1 = Hi∪{出现于S中的函数在Hi上的所有实例},i=1,2,…;形如f(x1, x2, …, xn)的函数的实例通过让xj = kj∈ Hi来形成(j=1,2,…,n)。 Hi可以迭代扩展到H∞,称为海伯伦域,简称H域(一个可数无穷集)。 例子 2)H域(海伯伦域) 2)H域(海伯伦域) H域上的原子谓词公式实例集A(为研究子句集的永假性): A={所有出现于S中原子谓词公式的实例}。 命题(不包含变量)——其实例就是其本身; P(t1, t2,…, tm)——其实例通过让ti=ki∈H(即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域上的所有解释都不满足。 2 H域和海伯伦定理 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域上一解释)都至少引起一个基子句线)={?P(a), ?Q(a), P(f(a)),?Q(f(a))} 就引起了基子句P(a)∨Q(f(a)真值为F。 当建立起一棵封闭语义树时,实际上也建立了一个由有限个不可同时满足的基子句构成的集合S‘ S’ = {P(a)∨Q(f(a)), ?P(a), ?Q(a), ?Q(f(a))} 4)海伯伦定理 子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S‘。 子句集S不可满足——封闭语义树——有限的不可满足的基子句集S‘ 。 基于海伯伦定理法的自动定理证明面临的主要困难: 子句集的不可满足性是不可判的, 计算量往往很大。 3 归结原理 动机 尽管海伯伦提出的H域(即海伯伦域)和海伯伦定理,为自动定理证明奠定了理论基础;但并未提供有效的操作化方法。 为提高判定子句集不可满足的有效性,鲁宾逊于1965年提出了归结(Resolution)原理,也称为消解原理。归结原理简单易行,便于计算机实现和执行,从而使定理的机器自动证明成为现实,也成为人工智能技术实用化的一次重要突破。 基本思路 是通过归结方法不断扩充待判定的子句集,并设法使其包含进指示矛盾的空子句。空子句是不可满足(即永假)的子句,既然子句集中子句间隐含着合取关系,空子句的出现实际上判定了子句集不可满足。 3 归结原理 1)归结方法 归结式C = C1’∨C2’, 由二个子句 C1 = L∨C1’, C2 = ? L∨C2’ 归结而成, 从C1 和C2 中消去互补文字L和? L,并通过析取将C1 和C2 的剩余部分组成新的子句, 例子:P(A)∨Q(x)∨R(f(x)), ? P(A)∨Q(y)∨R(y)的归结式: Q(x)∨R(f(x))∨Q(y)∨R(y)。 归结式性质: 定理:二个子句C1 和C2 的归结式C是C1 和C2 的逻辑推论。 推论:设C1 和C2 是子句集S中的两个子句,并以C作为它们的归结式,则通过往S中加入C而产生的扩展子句集S’与子句集S在不可满足的意义上是等价的,即:S’的不可满足? S的不可满足。 空子句C = 口 由C1 = L和C2 = ? L归结而成, 空子句是不可满足的子句,指示C1 和C2 是一对矛盾子句,成为用归结原理判定子句集不可满足的成功标志。 3 归结原理 2)归结推理过程 命题逻辑中的归结推理过程: 子句中文字只是原子命题公式或其 取反, 不带变量,易于判别哪些子句对包 含互补文字, 归结过程表示为归结演绎树, 例子:S={?P∨Q, P∨R, ?Q, ?R} (图2.24) 谓词逻辑中的归结推理过程: 子句中含有变量,不能直接发现和消去互补文字, 需对潜在的互补文字先作变量置换和合一处理。 2)归结推理过程 变量置换——用置换项取代公式中的变量,置换项可以是变量、常量或函数。 置换——包含若干置换元素(形如t/v)的集合, t/v ——置换项/变量。 例子 潜在的互补文字:P(x, y, x, g(x)), ?P(A, B, A, z) 置换:S1 = {A/x, B/y, g(x)/z} S2 = {f(w)/x, z/y, C/z} S3 = {B/x, f(w)/y, y/z} 置换结果:{P(x, y, x, g(x)), ?P(A, B, A, z)}S1 ={P(A, B, A, g(A)), ?P(A, B, A, g(A))} {P(x, y, x, g(x)), ?P(A, B, A, z)}S2 ={P(f(w)), z, f(w), g(f(w)), ?P(A, B, A, C)} {P(x, y, x, g(x)), ?P(A, B, A, z)}S3 ={P(B, f(w), B, g(B)), ?P(A, B, A, y)} 2)归结推理过程 潜在互补文字的合一处理——通过变量置换,使相应于这二个文字的原子谓词公式同一化的过程。 健全的合一算法——面向任意表达式, 归结演绎过程中只须对原子谓词公式作合一处理, 只需通过一个匹配过程去检查两个原子谓词公式的可合一性,并同时建立用于实现合一的置换。 匹配过程: 例子: P(x, y, x, g(x)), P(A, B, A, z) 可合一,实现合一的置换S1={A/x, B/y, g(x)/z}。 2)归结推理过程 谓词逻辑中子句归结例: C1 = P(x, y)∨Q(x, f(x))∨R(x, f(y)) C2 = ?P(A, B)∨?Q(z, f(z))∨R(z, g(z)) 令L11 = P(x, y), L21 = ?P(A, B), L11和?L21可合一 L11和L21是互补文字 置换S1 = {A/x, B/y} 变量的置换必须在整个子句对范围内进行 归结式:Q(A, f(A))∨R(A, f(B))∨?Q(z, f(z))∨R(z, g(z)) 两个子句可以有多于一对的互补文字, 另一对互补文字:L12 = Q(x, f(x)), L22 = ?Q(z, f(z)) 置换S2 = {z/x} 归结式: P(z, y)∨R(z, f(y))∨?P(A, B)∨R(z, g(z)) 谓词逻辑中的归结推理过程例: 2)归结推理过程 给定子句集: (1) ?R(x, y)∨?Q(y)∨P(f(x)) (2) ?R(z, y)∨?Q(y)∨W(x, f(x)) (3) ?P(z) (4) R(A, B) (5) Q(B) 对这些子句进行归结: (6)?R(x,y∨?Q(y), (1)与(3)归结,{f(x)/z}; (7) ?Q(B) , (6)与(4)归结,{A/x,B/y}; (8) 口, (7)与(5)归结。 该归结过程生成的归结演绎树。(图2.25) 3)归结演绎的完备性 若子句集S不可满足,就必定存在一个从S到空子句的归结演绎; 反之,若存在一个从S到空子句的归结演绎,则S必定是不可满足的。 归结原理并不能用于解决子句集不可满足性的不可判问题。 3 归结反演 应用归结演绎方法的定理证明。 1)归结反演系统 归结反演的基本思路: 要从作为事实的公式集F证明目标公式W为真,可以先将W取反,加入公式集F,标准化F为子句集S,再通过归结演绎证明S不可满足,并由此得出W为真的结论。 归结反演系统: 标准化部件——将公式集和取反的目标公式分别标准化为子句集,再合并为子句集S; 归结演绎部件——遵从归结演绎方法,控制定理证明的全过程。 食物问题例: 形式化, 标准化, 归结演绎; 归结反演树, 参见图2.26。 1)归结反演系统 1)归结反演系统 3 归结反演 2)归结策略 归结反演面临大子句集引起演绎效率问题, 选择有利于导致快速产生空子句的子句对进行归结, 支持集、线性输入、单文字子句优先、祖先过滤等策略等, 归结反演技术并未在定理自动证明以外的领域得到广泛应用。 3)提取问题回答 问题回答系统 目标公式往往是受存在量词约束的,形如(?x)W(x) 。 不仅证明目标公式为真, 回答提取——给出使W(x)为真的个体实例,即x的某个取值。 问答系统的运作: 归结反演, 回答提取——又分二个步骤: (1)对于标准化取反的目标公式而产生的子句(称为目标子句)G,建立其重言式G∨?G; (2)以G∨? G取代G,重复已进行过的归结演绎过程,建立修改证明树。 归结反演树的树根不再是空子句,而是?G,且G中的变量已为其置换项取代,实现了回答提取。 3)提取问题回答 回答提取例: 食物例:张吃什么食物? 目标公式: (?x)[Food(x)]∧Eat(Zhang, x) 取反并标准化为子句: (8)?Food(x4)∨ ?Eat(Zhang, x4) 进行归结反演并生成归结反演 树(图2.27)。 接着再进行回答提取,即建立 (8)式的重言式: ?Food(x4)∨?Eat(Zhang, x4 ) ∨[Food(x4)∧Eat(Zhang, x4)] 用其取代(8)式重复已进行过 的归结演绎过程,产生修正的 归结反演树,称为修改证明树 (图2.28)。 3)提取问题回答 例子小结: 目标子句G的重言式G∨?G中的?G并不 真正参与归结演绎, 只是为了使?G中的变量随着G中出现的 变量置换而同时得到置换。 归结反演和回答提取可以合为一体进行。 避免误用?G参与归结,可以用特定的符 号替代?G,如:ANSWER(x1,x2,…,xn)。 应用修改证明树提取回答是可行的: 依据归结演绎过程,树根中?G实际上是作 为事实的公式集与重言式G∨?G的逻辑推 论,由于重言式永真,只要公式集为线)提取问题回答 目标公式或许会取更为复杂的形式: 2.4 基于规则的演绎推理 动机: 基于归结的演绎推理 简单易行——只要将问题求解的依据(事实或公式)和目标以合适公式加以形式化描述,就可交由归结反演系统和问答系统执行。 丢失隐含于合适公式的启发式知识 合适公式标准化为高度统一的子句集: P∧Q ? R ?P∨?Q∨R, 效率低下,难以适应于复杂的应用域。 不利于人们从自然思维的角度组织问题的求解和提供问题求解所需的知识——归结演绎并非人类的自然思维方式。 基于规则的演绎推理 保留蕴涵式,将其作为推理规则,用于直接推导目标公式, 符合人的自然思维方式, 通过规则(作为启发式知识)更有效地引导演绎推理过程, 比归结反演更为有效的推理技术,广泛地应用于许多问题求解任务中。 2.4 基于规则的演绎推理 总体描述 规则演绎将求解问题所需的知识分为二类: 规则——表示为蕴涵式,作为启发式知识(表示应用域中存在的规律和法则),引导演绎推理过程。 事实——表示为非蕴涵形式的合适公式,作为应用规则进行推理时参考的有关问题状态和环境的知识。 规则演绎的任务——从给定的事实(即问题的状态和环境知识)和规则,证明某个目标公式成立。 规则演绎的分类: 正向演绎——从事实出发,应用规则不断推导出中间结果作为新的事实,直至推导出目标公式。 逆向演绎——从目标公式出发,逆向应用规则不断推导出子目标,直至所有子目标就是给定的事实为止。换言之,目标公式通过逆向推理找到了支持其成立的所有依据。 主要内容: · 基于规则的正向演绎推理 · 基于规则的逆向演绎推理 · 演绎推理的应用讨论 · 逻辑语言Prolog(略) 1基于规则的正向演绎推理 1)问题求解的规范表示——分为三个部分:事实、规则集和目标 事实——表示为不含蕴涵符号的文字与或形。 例子: 作换名处理; 文字与或形更接近原始表达式 1)问题求解的规范表示 事实表达式的文字与或形可以用与或图表示: 若母式为析取式: E1∨E2∨…∨Ek 以一个K-连接指向各析取项Ei; 若母式为合取式: E1∧E2∧… ∧Ek 以k个1-连接指向各合取项Ei。 与或图例; 参见图2.29 析取(连词∨)符号与K-连接 同向,根节点在图下方。 根节点——整个事实表达式, 叶节点——对应于文字与或形 中的每一个文字。 仅借用与或图表示事实表达式,但 语义上与表示搜索过程的与或图有 本质的区别。 1)问题求解的规范表示 规则——以正向方式使用规则(称为F规则),化简为:L ? W L为单文字——便于通过L和与或图叶节点的匹配来激活规则, W是文字与或形, 例子: L1∨L2 ? W L1 ? W, L2 ? W, L1∧L2 ? W L1 ? ?L2∨W或L2 ? ?L1∨W。 1)问题求解的规范表示 目标——化简后限定表示为文字的析取式,即子句 量词消去方法取事实表达式的对偶形式, 即将全称量词的约束变量以Sk?lem函数或常量取代; 子句隐含地受存在量词约束。 例子: 用对偶方式消去量词的直观说明——归结反演将目标公式取反, 子句中变量须作换名处理,使各文字不含同名变量。 2)正向演绎推理的实现 借助于与或图表示方式,正向演绎推理从事实表达式出发,不断用激活(左部单文字和与或图叶节点匹配)的F规则对与或图进行变换(从而扩展了与或图),直至得到一个将目标表达式(子句)包含的文字作为叶节点的一致解图。 命题逻辑的情况 基本方法——选用激活的规则对与或图进行变换。 所有公式都不含变量——易于寻找左部单文字和 与或图中叶节点匹配的规则。 例子 与或图的变换——将激活的规则加入与或图: 规则左部单文字作为节点插入与或图, 通过匹配弧和与或图相应叶节点连接; 规则右部以与或图子图的方式插入。 目标文字(目标公式中的某个文字)加入与或图: 和与或图叶节点匹配, 作为目标节点(以方框指示)插入与或图, 通过匹配弧和与或图相应叶节点连接。 演绎推理的成功结束条件——获得终止于目标节点的一个解图, 注意:要求解图的所有叶节点都是目标节点。 2)正向演绎推理的实现 谓词逻辑的情况 复杂性(因含有变量): 规则或目标文字的激活判断——须对单文字和与或图中的相应叶节点作合一处理; 演绎推理过程可能会对同一变量进行不一致的置换,从而导致不一致解图的生成。 猎狗问题例: 参见图2.31。 解图置换——收集解图中所有变量的置换(为置换元素) 对解图置换作合一复合处理:参见书上, 例子: 参见表2.3。 回到猎狗问题例: 其解图置换的合一复合就是其自身, 得到一致解图,演绎推理成功结束, 只要将目标公式中的变量z、z1分别 以置换项Fido取代,就可得到解答。 演绎过程中同一规则或同一文字的 多次使用,必须换名。 2)正向演绎推理的实现 2 基于规则的逆向演绎推理 逆向演绎推理与正向演绎推理形成对偶关系,其从目标公式出发,逆向应用规则对相应于目标公式的原始与或图进行变换,直至得到一个所有叶节点都是事实节点(以事实表达式中的文字作为节点内容的节点)的一致解图为止。 1)问题求解的规范表示——分为三个部分:事实、规则集和目标 目标公式 目标公式的表示不受限制,化简为不含蕴涵符号的文字与或形, 全称量词的约束变量以Sk?lem函数或常量取代, 隐含着变量受存在量词的约束。 例子: 通过换名,使顶层析取式的各析取项不含同名变量。 目标公式的文字与或形也可以用与或图表示 若母式为合取式:E1∧E2∧… ∧Ek——以一个k-连接指向各合取项Ei; 若母式为析取式:E1∨E2∨… ∨Ek ——以k个1-连接指向各析取项Ei。 与或图例 合取(连词∧)符号与K-连接同向,根节点在图上方, 根节点——整个目标公式, 叶节点——对应于目标公式中的每一个文字。 1)问题求解的规范表示 1)问题求解的规范表示 规则——以逆向方式使用规则(称为B规则),化简为:W ? L L为单文字——便于通过L和与或图叶节点的匹配来激活规则, W是与或形, 例子: (?x){(?y)(?z)[P(x, y, z)∧Q(y, z)] ?(?u)R(x, u)} 则先暂时消去蕴涵符号并化简为与或形: ?P(x, y, f(x, y))∨?Q(y, f(x, y))∨R(x, u) 再恢复蕴涵式表示: P(x, y, f(x, y)∧Q(y, f(x, y)) ? R(x, u) W ? L1∧L2 W ? L1, W ? L2。 事实表达式 化简后限定表示为文字的合取式, 消去量词时将存在量词的约束变量以Sklem函数或常量取代, 合取式隐含地受全程量词约束。 2) 逆向演绎推理的实现 借助于与或图表示方式,逆向演绎推理不断用激活(右部单文字和与或图叶节点匹配)的B规则对与或图进行变换,直到获得一个叶节点全是事实节点(以方框指示)的一致解图。 推理的实现 与或图的变换——将激活的规则加入与或图: 规则右部单文字作为节点插入与或图, 通过匹配弧(以双箭头表示)和与或图相应叶节点连接; 规则左部以与或图子图的方式插入。 事实文字(事实表达式中的某个文字)加入与或图: 和与或图叶节点匹配, 作为事实节点(以方框指示)插入与或图, 通过匹配弧和与或图相应叶节点连接。 演绎推理的成功结束条件——出现叶节点全是事实节点(以方框指示)的一致解图。 注意:并不要求所有事实文字都进入解图。 逆向演绎推理实际是给目标公式寻找原始证据(事实文字)的过程,当推理的各个分支(解图中的分支)都到达事实节点时,目标公式有了支持它成立的足够证据。 2) 逆向演绎推理的实现 不等式问题例:参见图2.33 每次使用规则时都对变量作换名处理, 注意事实表达式中的文字G(C,0)未出现在解图中, 事实可以原子谓词公式的集合形式给出,原子事实间隐含合取关系, 解图置换,置换的合一复合S‘就是其自身,所以解图是一致的。 2) 逆向演绎推理的实现 3 演绎推理的应用讨论 1)正、逆向演绎推理的特点比较 共同的特点 以与或形和相应的与或图来表示和支持推理过程。 推理控制的基本策略——通过不断激活规则去变换与或图,直至搜索到某个一致解图为止。 问题求解的描述——分三个部分:事实、规则和目标。 采用同样的方式标准化这三个部分的表示。 事实和规则的标准化过程对量词及其约束变元的处理遵从合取范式的化简要求。 目标的标准化过程采用对偶原则作处理,即将全称量词的约束变量以Sk? lem函数或常量取代,并在量词消去后隐含着所有变量均受存在量词的约束。 正、逆向演绎推理的特点对比见表2.4。 3 演绎推理的应用讨论 2)双向演绎推理 实现优势互补。 处理结束条件的复杂性以及需分别支持 正、逆向推理,增加了系统设计和知识 获取的困难 更实用化的方式——分解复杂的问题求 解任务,根据子任务的特点选用。 3)解图搜索修剪策略 动机: 与或图中的“或”关系导致多个解图存在的可能。 基本的解图搜索策略——先生成一个任意解图, 再检索其一致性。 直到解图生成后才检查其一致性,往往太晚。 解图的不一致性往往在早期就可发现,及时修剪有重要意义。 修剪策略——每当以规则扩展局部解图时,就及时检查解图置换的一致性,并随即修剪掉不一致的局部解图,以免除对这种局部解图的进一步徒劳搜索。 例子: 参见图2.34。 终止于事实节点的一致解图 终止于目标节点的一致解图 结束条件 B规则 目标————-?事实 F规则 事实———----?目标 演绎推理 相应于目标公式 ∧--—K-连接 相应于事实表达式 ∨--—K-连接 初始与或图 文字与或形 目标 文字析取形 目标 W ? L 规则 L ? W 规则 文字合取式 事实 文字与或形 事实 问题求解的描述 逆向演绎推理 正向演绎推理 1 2 3 1 2 3 A B C * * *

本文链接:http://furymagazine.com/yuyishu/62.html