《AI-4(本)人工智能课件.ppt》由会员分享，可在线阅读，更多相关《AI-4(本)人工智能课件.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能基础人工智能基础22 问题归约问题归约 n问题归约：问题归约：n复杂的问题复杂的问题-若干需同时处理的简单子问题若干需同时处理的简单子问题n子问题全部解决，问题才算解决子问题全部解决，问题才算解决n问题的解答由子问题的解答联合构成问题的解答由子问题的解答联合构成n问题问题递归递归 本原问题集本原问题集n本原问题本原问题不可或不需再通过变换化简的不可或不需再通过变换化简的“原子原子”问题问题n主要内容：主要内容：n问题归约的描述问题归约的描述n与或图搜索与或图搜索n与或图的启发式搜索与或图的启发式搜索2.2.1 2.2.1 问题归约问题归约的描述的描述 广义的状态空间搜索技术广义的状态空
2、间搜索技术n状态空间表示为二元组：状态空间表示为二元组：SP=(S,O)SP=(S,O)n问题状态子问题状态的联合问题状态子问题状态的联合n操作算子的执行导致问题的变换：操作算子的执行导致问题的变换：n状态变迁状态变迁导致问题从上一状态变迁到下一状态导致问题从上一状态变迁到下一状态n问题分解问题分解分解问题为需同时处理的子问题，但不改变问题状态分解问题为需同时处理的子问题，但不改变问题状态n基于状基于状态变态变迁的迁的问题问题分解分解先先导导致状致状态变态变迁，再迁，再实现问题实现问题分解分解 例：字母重写问题例：字母重写问题n初始状态为字母列表初始状态为字母列表(A B C)(A B C)n
3、目目标标状状态为态为只包含字母只包含字母x x、y y、z z的字母列表的字母列表，n提供二类操作算子：提供二类操作算子：n面向问题分解面向问题分解Split(nSplit(n)字母列表分解为子表字母列表分解为子表约束子表需有可用重写规则约束子表需有可用重写规则n面向状态变迁面向状态变迁 字母列表的重写规则：字母列表的重写规则：求解重写问题的与或图求解重写问题的与或图2.2.1 2.2.1 问题归约问题归约的描述的描述n与或图应用问题归约策略得到的状态空间图应用问题归约策略得到的状态空间图n逻辑逻辑与关系关系用园弧连接关联节点用园弧连接关联节点n指示问题分解为子问题指示问题分解为子问题n问题状
4、态子问题的状态描述联合问题状态子问题的状态描述联合n逻辑逻辑或关系：关系：n问题的分解可以有多种方式，问题的分解可以有多种方式，对应于问题对应于问题/子问题可能激活子问题可能激活 多条重写规则多条重写规则n多个可能的解答多个可能的解答 4 4求解重写问题的与或图n基于状态变迁的问题分解：基于状态变迁的问题分解：n面向状态变迁的操作和面向问题分解的操作合并面向状态变迁的操作和面向问题分解的操作合并面向非本原问题的操作算子表示为紧凑的重写规则面向非本原问题的操作算子表示为紧凑的重写规则2.2.1 2.2.1 问题归约问题归约的描述的描述n子子问题问题求解的排序求解的排序:n子子问题问题相互独立，可
5、按任意次序相互独立，可按任意次序进进行行;n复复杂问题杂问题，子，子问题仅问题仅相相对对独立，排序重要独立，排序重要。n用用问题归约问题归约策略求解策略求解问题问题：n梵塔梵塔问题问题n符号符号积积分分问题问题（SAINTSAINT）n分子结构识别问题分子结构识别问题 （DENDRAL）用问题归约策略求解问题梵塔问题 1 2 3 1 2 3ABC初始状态目标状态初始状态目标状态规则：每次只能搬一个盘子，且较大盘不能压放在较小盘之上规则：每次只能搬一个盘子，且较大盘不能压放在较小盘之上问题状态：三元组问题状态：三元组 (111)=(333)用问题归约策略求解问题梵塔问题 1 2 3 1 2 3A
6、BC2.2.2 2.2.2 与或图搜索与或图搜索 n与或图与或图对一般图对一般图(或图或图)的扩展；的扩展；n根节点指示初始状态根节点指示初始状态n同父子节点间可存在与关系，父、子同父子节点间可存在与关系，父、子节点间不能简单地以弧线关联节点间不能简单地以弧线关联 超链接超链接n解图解图广义的解路径广义的解路径求解重写问题的与或图求解重写问题的与或图与或图搜索与或图搜索基本概念基本概念nK-K-连接连接(父节点的外向连接父节点的外向连接)n表示从父节点到子节点间的连接表示从父节点到子节点间的连接n园弧指示同父子节点间的园弧指示同父子节点间的与与关系关系nK-子节点的个数，子节点的个数，K1-超
7、链接超链接，所有超链接所有超链接K=1-K=1-一般图一般图n一个父节点可有多个外向的一个父节点可有多个外向的K-连接连接n根、叶、终节点根、叶、终节点n无父节点的节点无父节点的节点根节点根节点，指示问题的初始状态，指示问题的初始状态n无子节点的节点无子节点的节点叶节点叶节点n用于联合表示目标状态的节点用于联合表示目标状态的节点终节点终节点n终节点必定是叶节点，反之不然终节点必定是叶节点，反之不然与或图搜索与或图搜索基本概念基本概念n解图的生成解图的生成自根节点开始选一外向连接，并从自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如该连接指向的每个子节点出发，再选一外
8、向连接，如此反复进行，直到所有外向连接都指向终节点为止。此反复进行，直到所有外向连接都指向终节点为止。n解图纯粹是一种解图纯粹是一种与图与图n搜索到多个解图，由于与或图中存在或关系搜索到多个解图，由于与或图中存在或关系n解解图应图应无无环环(任何任何节节点的外向点的外向连连接均不得指向自接均不得指向自 己或自己的先己或自己的先辈辈)，否，否则则会使搜索陷入死循会使搜索陷入死循环环 图图2.204个可能的解图个可能的解图与或图搜索与或图搜索术语的形式定义术语的形式定义 解图解图：与或图（记为：与或图（记为G）任一节点（）任一节点（n）到终节点集合的解图（）到终节点集合的解图（G）是）是G的子图。
9、的子图。1)若若n是终节点，则是终节点，则G就由单一节点就由单一节点n构成；构成；2)若若n有一外向有一外向K-连接指向子节点连接指向子节点n1，n2，nk,且这些子节点每个都有到终节点集合的且这些子节点每个都有到终节点集合的解图，则解图，则G由该由该k-连接和所有这些相应于子节点的解图构成；连接和所有这些相应于子节点的解图构成；3)否则不存在否则不存在n到终节点集合的解图。到终节点集合的解图。解图代价解图代价:以以C(n)指示节点指示节点n到终节点集合解图的代价，并令到终节点集合解图的代价，并令K-连接的代价就为连接的代价就为K,则有：则有：1)若若n是终节点，则是终节点，则C(n)=0 2
10、)若若n有一外向有一外向K-连接指向子节点连接指向子节点n1，n2，nk,且这些子节点每个都有到终节点集合的且这些子节点每个都有到终节点集合的解图解图,则则C(n)=K+C(n1)+C(n2)+C(nk)能解节点：能解节点：1)终节点是能解节点；终节点是能解节点；2)若节点若节点n有一外向有一外向K-连接指向子节点连接指向子节点n1，n2，nk,且这些子节点都是能解节点，则且这些子节点都是能解节点，则n是能解节点；是能解节点；不能解节点不能解节点：1)非终节点的叶节点是不能解节点；非终节点的叶节点是不能解节点；2)若节点若节点n的每一个外向连接都至少指向一个不能解节点，则的每一个外向连接都至少
11、指向一个不能解节点，则n是不能解节点。是不能解节点。2.2.3 与或图的启发式搜索与或图的启发式搜索 n需求分析需求分析n引入应用领域的启发式知识去引导搜索过程引入应用领域的启发式知识去引导搜索过程n搜索的是解图估算搜索的是解图估算h(nh(n)估算评价函数估算评价函数f(n)f(n)的第的第1 1分量分量g(n)g(n)无意义无意义nh(n)h(n)是对最小解图代价的估计是对最小解图代价的估计n可同时出现多个候选的待扩展局部解图可同时出现多个候选的待扩展局部解图,选择一个可能代价最小的继续搜索选择一个可能代价最小的继续搜索n解图代价的递归方式估算解图代价的递归方式估算n父节点父节点n n的由
12、外向的由外向K-K-连接指向的子节点连接指向的子节点(n(n1 1，n n2 2，n nk k)各自估算其各自估算其h(nh(nk k)n从父节点从父节点n n到终节点集合解图的可能代价到终节点集合解图的可能代价f(nf(n)=K+h(n)=K+h(n1 1)+h(n)+h(n2 2)+)+h(nh(nk k)比直接基于比直接基于h(n)h(n)估算而得出的估算而得出的f(n)f(n)值更为准确值更为准确递归计算出递归计算出f(nf(n0)2.2.3 与或图的启发式搜索与或图的启发式搜索1.1.与或图的启发式搜索算法与或图的启发式搜索算法AO*AO*w w 参数参数nGG搜索图搜索图nG G被
13、选中的待扩展局部解图被选中的待扩展局部解图nLGSLGS候选的待扩展局部解图集候选的待扩展局部解图集nn n0根节点根节点/初始状态节点初始状态节点nnn被选中的待扩展节点被选中的待扩展节点nf fi(n(n0)第第i i个候选的待扩展局部解图的可能代价个候选的待扩展局部解图的可能代价w w 算法的执行划分为二个阶段：算法的执行划分为二个阶段：n初始化初始化建立只包括初始状态节点的搜索图；建立只包括初始状态节点的搜索图；n搜索循环搜索循环选择和扩展局部解图，精化解图代价的估计，选择和扩展局部解图，精化解图代价的估计，传递节点的能解性。传递节点的能解性。1.1.与或图的启发式搜索算法与或图的启发
14、式搜索算法AO*AO*（1 1）G:=nG:=n0，LGSLGS为空集；为空集；（2 2）若）若n n0 是终节点，则标记是终节点，则标记 n n0 0为能解节点；否则计算为能解节点；否则计算f(nf(n0)=h(n)=h(n0),),并把并把G G作为作为0 0号候号候选局部解图加进选局部解图加进LGSLGS；（3 3）若）若n n0 标记为能解节点，则算法成功返回；标记为能解节点，则算法成功返回；（4 4）若）若LGSLGS为空集为空集,则搜索失败返回则搜索失败返回;否则从否则从LGSLGS选择选择f fi(n(n0)最小的待扩展局部解图作为最小的待扩展局部解图作为G G；（5 5）G G
15、中选择一个非终节点的外端节点（尚未用于扩展出子节点的节点）作为中选择一个非终节点的外端节点（尚未用于扩展出子节点的节点）作为n n；（6 6）扩展扩展n n，生成其子节点集，并从中删去导致有环的子节点以及和它们有生成其子节点集，并从中删去导致有环的子节点以及和它们有“与与”关系的关系的子节点；若子节点集为空，则子节点；若子节点集为空，则n n是不能解节点，从是不能解节点，从LGSLGS删去删去G G(因为因为G G不可能再扩展为不可能再扩展为解图解图)；否则；否则,计算每个子节点计算每个子节点 n ni的的f(nf(ni),),并通过建立外向并通过建立外向K-K-连接将所有子节点加到连接将所有
16、子节点加到G G中中;（7 7）若存在）若存在j j个（个（j1j1）外向外向K-K-连接连接,则从则从LGSLGS删去删去G G，并将并将j j个新局部解图加进个新局部解图加进LGSLGS；（8 8）G G中或在取代中或在取代G G的的j j个新局部解图中用公式个新局部解图中用公式f(n)=K+h(nf(n)=K+h(n1)+h(n)+h(n2)+)+h(nh(nk)的计算结果取代原先的的计算结果取代原先的f(n)f(n)，并传递这种精化的作用到并传递这种精化的作用到f fi(n(n0)（i=1,2,i=1,2,j j）；）；同时将作为终节点的子节点标记为能解节点，并传递节点的能解性。同时将
17、作为终节点的子节点标记为能解节点，并传递节点的能解性。（9 9）返回语句（）返回语句（3 3）。）。与或图的启发式搜索算法与或图的启发式搜索算法AO*AO*1号局部解图3号局部解图4号局部解图被选中的待扩展局部解图G2.2.3 与或图的启发式搜索与或图的启发式搜索2 2 算法应用的若干问题算法应用的若干问题n从局部解从局部解图图中中选择选择加以加以扩扩展的展的节节点点n选择选择f(nf(n)=)=h(nh(n)的的值值最小的最小的节节点点不一定会加速搜索不一定会加速搜索过过程，（搜索解程，（搜索解图图）n引入启引入启发发式知式知识识，选择导选择导致解致解图图代价代价发发生生较较大大变变化的化的
18、节节点点使搜索快速聚焦到使搜索快速聚焦到实际实际代价代价较较小的候小的候选选解解图图上上 否则，随机选择加以扩展的节点否则，随机选择加以扩展的节点nAOAO*算法的可采纳性算法的可采纳性nAOAO*算法的应用要求遵从的约束：算法的应用要求遵从的约束：nh(nh(n)h)h*(n)h(n)h*(n)(n)实际的代价最小解图找到时解图的代价实际的代价最小解图找到时解图的代价nh(n)满足单调限制条件满足单调限制条件:h(n)K+h(n1)+h(n2)+h(nk)粗略的估计总是不超过细致的计算粗略的估计总是不超过细致的计算 nAOAO*算法是可采纳的算法是可采纳的 当某与或图存在解图时，应用当某与或
19、图存在解图时，应用AOAO*算法一定能找出代价最小的解图。算法一定能找出代价最小的解图。2 2 算法应用的若干问题算法应用的若干问题n算法算法AO*与与A*的比较的比较n解图解图解答路径解答路径n优先扩展估算代价最小的局部解图优先扩展估算代价最小的局部解图解答路径解答路径nf(nf(n)=)=h(nh(n)，修正，修正f fi(n(n0)f(nf(n)=)=g(n)+h(ng(n)+h(n)n应用应用LGSLGS存放候选的待扩展局部解图，并依据存放候选的待扩展局部解图，并依据f fi(n(n0)值排序值排序应用应用OPENOPEN表和表和CLOSECLOSE表分别存放待扩展节点和已扩展节点，并
20、依据表分别存放待扩展节点和已扩展节点，并依据f(n)f(n)值排序值排序 n解图代价的重复计算解图代价的重复计算n某些子节点可能会有多个父节点，某些子节点可能会有多个父节点，其到终节点集合解图其到终节点集合解图的代价在计算自根节点的代价在计算自根节点n0出发的解图时被重复出发的解图时被重复累计，需删除累计，需删除 小结一般图搜索、基于问题归约的与或图搜索一般图搜索、基于问题归约的与或图搜索n相同相同应用状态空间概念，强调设计高效的算法应用状态空间概念，强调设计高效的算法n设计高效算法的关键设计高效算法的关键引入应用领域相关的启发式知识引入应用领域相关的启发式知识n启发式函数设计可采纳性启发式函
21、数设计可采纳性n好的启发式函数不仅能快速搜索到解答，且能确保搜索算法可采纳性好的启发式函数不仅能快速搜索到解答，且能确保搜索算法可采纳性n考虑设计代价，放弃可采纳性，只求搜索到代价较小解答路径考虑设计代价，放弃可采纳性，只求搜索到代价较小解答路径/解图解图n本质区别本质区别关注的问题求解策略关注的问题求解策略n前者应用操作算子逐步缩小问题状态和目标状态的差别前者应用操作算子逐步缩小问题状态和目标状态的差别。与或图特例与或图特例,解路径解路径n关注于把复杂的问题逐步关注于把复杂的问题逐步/逐层分解为子问题逐层分解为子问题。搜索的结果是解图搜索的结果是解图 2.3 2.3 基于归结的演绎推理基于归结的演绎推理 n人的问题求解行为人的问题求解行为 解答搜索过程解答搜索过程?解答识别过程解答识别过程?!?!n识别解答或部分解答依赖于应用领域特有的知识识别解答或部分解答依赖于应用领域特有的知识n符号推理是基于知识来求解问题的主要手段符号推理是基于知识来求解问题的主要手段n符号推理符号推理 重要方式重要方式 演绎推理演绎推理 形式逻辑形式逻辑)AI)AI研究的重要基础之一研究的重要基础之一2.3 2.3 基于归结的演绎推理基于归结的演绎推理 n主要内容：主要内容：谓词演算谓词演算 H H域和海伯伦定理域和海伯伦定理 归结原理归结原理 归结反演归结反演