人工智能考试整理.doc

智能定义（知识阈值理论） 智能就是在巨大的搜索空间中迅速找到一个满意解的能力智能的综合性定义:智能是知识和智力的总和。其中知识是智能行为的基础。智能的特征:1）具有记忆与思维能力存贮有感官得到的外界信息并加以处理（如分析，计算，联想、决策等）2）具有感知能力：通过感官获取外部信息的能力。3）具有自适应能力 通过与外部世界交互学习，积累经验，增长知识，以适应环境变化。4）具有表达能力通过语言、手势、表情等方式完成信息的输出。深蓝：能够模拟人的思维，进行博弈的计算机。1997年5月12日，一个名为“深蓝”（deep Blue ）的IBM计算机系统战胜当时的国际象棋冠军 盖利.卡斯帕罗夫图灵测试：两个房间，一个是人，一个是机器，测试者通过一系列的提问，如果提问题的人无法分辨是人还是机器在回答问题，则认为该机器具有智能人工智能（Artifical Intelligence，简称AI）又称机智能machine intelligence，一般认为起源于美国1956年的一次夏季讨论（达特茅斯会议）在这次会议上，第一次提出了“Artifical Intelligence”这个词。AI的本质问题：研究如何制造出人造的智能机器或系统，来模拟人类的智能活动的能力，以延伸人们智能的科学。产生式系统由三个部分组成1）综合数据库（Globe Database） 也称为：事实库，上下文等。 作用:存放问题求解的过程中产生的状态描述信息。2）规则库（Rule Base）(问题本身知识、求解知识)也称为规则基、规则集等。作用：存放规则知识。产生式规则的一般表达形式：IF（前提）THEN(结论)即 ： 如果 那么.例：1）数学定理 2）IF A是一种动物 AND A 是哺乳动物 AND A 吃肉 THEN A 是高级动物 关于不精确推理 当规则的前提成立时，结论并非完全成立。这种推理称为不精确推理。通常采用阈值方法来解决此类问题。（3）控制策略（Control Strategy） a 选择规则库中的规则与综合数据库的已知事实进行匹配，匹配成功的规则为可用规则，否则为不可用规则。 b 规则冲突的解决（可用规则书1）。c将选中的规则的结论放入综合数据库。产生式系统的特点： 1 模式化：所有规则具有相同的形式2结构化：规则见的关联比较简单，容易维护。3自燃性：规则表达了因果关系，比较符合人们的思维方式，容易理解。4单一性：智能处理因果关系问题。5效率低，规则匹配过程很大。产生式系统的适用范围：1）知识杂乱、事实众多、无统一理论的领域2）该领域的知识能够抽象出来3）该领域的知识可分解为一组独立的动作，以便用规则加以表示。概括说的说：问题空间从一个状态到另一个状态的转移序列独立的领域可采用产生式系统模拟。产生式系统一般性算法：1 DATA 初始数据库2 until DATA满足结束条件条件之前 do：3 Begin 在规则集中选择某一可用于DATA的规则R DATA R应用到DATA后得到的结果END例1 字符转换 问题：设字符转换规则 ABC ACD BCG BEF DE已知：A,B求：F一、综合数据库 x ：其中x为字符二、规则集 IF AB THEN C IF AC THEN D IF BC THEN G IF BE THEN F IF D THEN E三、控制策略 顺序排队四、初始条件 A,B五、结束条件：例2 八数码游戏问题：一个33棋盘有八张牌1,2，8 及一个空格，空格周围的牌可以向空格移动。求解：给定一个初始状态s一个目标状态G，求S到G的走步序列。产生式系统的基本控制策略概括的讲：产生式系统控制策略-搜索1）不可撤回方式2）试探性方式 a 回溯方式（Backtracking） b 图搜索方式（Graph search）1.不可撤回方式 基本策略：选择规则时只依靠局部知识（信息），而不考虑是否全局最佳选择，只能满足局部优化条件，用过的规则不再撤回。特点： a 方法简单，容易实现 b 具有一定的局限性，适用范围小（只可用于单极值情况） c 可能会造成规则的多次重复使用。比如：爬山算法，不可用于解决多极值问题。关于 局部知识的利用 ：设计局部评价函数W(n),根据W(n)最大为原则来选择规则。例：八数码问题设：- W(n):不在位的数码个数 n：任意状态目标状态：- W(n)=0 （每个数码就位）最不利状态- W(n)= -8 （每个数码都不在规定的位置）2.回溯方式基本策略：试探性的选择一条规则，如果发现此规则不合适，则退回去另选其他规则。关键在于回溯条件的设定。特点： a 实用性好(相对不可回撤方式) b 适用范围较大，在一定程度上能避免盲目性 c 可解决局部极值问题设计方法： a 确定合适的回溯条件 b 充分利用可用知识来排列规则，减少回溯次数例：八数码游戏（主要讨论回溯条件）回溯条件： a 新产生的状态已经在搜索过程中出现； b 应用规则的数量已经超过规定值(深度限制) c 当前状态，无可用规则满足上述条件之一 则产生回溯，每次回溯一层。3. 图搜索方式基本策略： 它是一种展开式搜索方法，把问题空间看成一张隐含图，从中搜索出一条解路径。特点： a 实用性好 b 能保留完整的搜索树 c 对于解空间较大的问题而言，搜索代价较大。例：八数码问题这是一个典型的宽度优先策略，所以搜索代价比较大。总结：三种控制策略的特点 1） 不可撤回方式：沿一条路径单向延伸搜索2)回溯方式：可修正搜索路径3）图搜索方式：展开式搜索，可保留完整的搜索树。产生式系统分类1.一般性产生式系统 根据规则的应用方式，一般性产生式系统可以分为三种类型： 1）正向系统（数据驱动） 采用正向推理方式，即由初始状态推理到目标状态，正向系统里的规则是正向使用的:规则的前提成立，那么规则的结论成立。 2)反向系统（目标驱动系统）采用反向推理方式：即由目标状态反向推理找到初始状态。反向系统的规则是反向使用的：先假设规则的结论成立，在寻找使其成立的前提条件。 3）双向系统 由数据、目标双向驱动，最后终止在某个中间状态。 例：数学证明思路2.可交换产生式系统定义：满足下列性质的产生式系统称为可交换产生式系统 a 给定可以用于数据库D的规则集R，对于使用R中的任何规则后产生的任何数据库，规则集R仍然可用。(规则适用性) b 如果目标条件被D满足，则应用R中的任何规则于D上所产生的任何数据库仍可满足目标条件。(数据库可用性) c 应用R中一个规则序列于D上后，得到的数据库不随这规则序列次序变化而变化。（规则次序无关性）3.可分解产生式系统定义：任何待求解的数据库都可以分解为若干个独立处理分量的产生式系统称为可分解产生式系统。求解方法：将初始数据库分解为几个可独立处理的分量，用规则分别求解，生成新的数据库，再分解，再求解，知道结束。可分解产生式系统的一般性算法：1 DATA 初始数据库2Di DATA， Di库：独立的分量数据库3 until Di 的所有元素都满足结束条件之前，do：4 begin 5 从 Di 中选择一个不满足结束条件的D*6 把D*从Di 中删除7 从规则集R中选一条可用于D*的规则r，设D是人应用于D*的结果是D的分解式。8 在 Di 添加di9 endAI领域的知识分类 a 陈述性知识：用于描述综合数据库的状态。（如事实等） b 过程性知识：用于规则中表达问题的知识.（如客观规律等） c 控制性知识：用于构成控制策略的知识（算法、数据结构等）AI系统的一个难题：知识表达问题，要能够客观的描述现实，简化求解过程，有效的提高求解效率，降低求解代价。产生式系统的搜索策略状态空间：由给定问题的所有可能的状态组成的空间（相当于全集G）搜索空间：按某种策略在状态空间中选取的部分空间（G的子集）解路径（解空间）：求解问题的一条有效路径。搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。搜索策略的评价准则：总体费用最低费用的划分： a 规则应用的费用：执行规则时所花的费用 b 控制费用：选择规则所花的费用。1.回溯策略2.图搜索策略3.启发式图搜索策略1）A算法2）爬山算法3）分支界限算法4）动态规划算法5）A*算法6）h函数与A*的关系7）关于单调性限制8）A*算法示例例 四皇后问题定义综合数据库：设：DATA=ij1=i,j=4,其中：ij表示棋子所在行列 如：24表示第二行第四列有一枚棋子因为棋盘上 可放入的棋子数为04个所以集合中元素数位0 4个，即length（DATA）=0 4图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：1，一个完整的搜索图G。2一个解路径，用指针表示的解路径。Procedure GraphSearch1 G=G0(G0=s),open=(s) /s:初始状态2 closed=() 3Loop:if open=() then exit(fall)4 nfirst(open) remove(n,open), add(n,closed)5 if goal(n) then exit(success)6mj expand(n), /mj不含n的先辈节点7 openadd(open，mj) / mj不在open，closed中标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，go loop深度优先算法Procedrue depth-First-Search1 G=G0(G0=s),open=(s),closed=() /s:初始状态2 Loop:if open=() then exit(fall)3 nfirst(open)4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先辈节点7 openadd(open，mj) / mj不在open，closed中标记mj每个到n节点指针，按照节点深度递减顺序排列open中的节点 8 go loop讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大宽度优先算法：Procedrue breadth-First-Search1 G=G0(G0=s),open=(s),closed=() /s:初始状态2 Loop:if open=() then exit(fall)3 nfirst(open)4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先辈节点7 open标记每个到n节点指针，按照节点深度递增顺序排列open中的节点 8 go loop 理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略penadd(open，mj) / mj不在open，closed中宽度优先例题： 由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图解：1）状态描述（P1，P2，P3）表示按A、B、C顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。初始状态时（B、T、T）,目标状态 可以表示（B、C、T）2）定义操作:move(x,y)表示将积木x移到Y上 ；约束条件:a X顶部必须是空的 b 如果Y是积木，Y的顶部必须是空 c 同一种状态出现不得多于一次。1）解题过程 2）open表和closed表3）节点样子画出整个图G 和解路径4）程序何时结束 5）改用深度优先如何？启发式图搜索策略：基本概念启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。降低搜索空间 找到最佳解启发式信息用于解决open表中节点的排列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大排列所有节点。评价函数的目的：把最有希望得到最佳解或者解的排列在前面。路径 ：给定节点序列（n0，n1，nk）。如果该序列中的任一节点ni-1都有后继节点ni，则该节点序列为从n0到nk的一条路径，路径长度为K路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。设：路径山任两点间的耗散值为才C(ni,nj),则从ni到nk的路径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路径耗散值：最佳路径上的实际耗散值，记为：K(ni,nj).K(ni,nj)=g*(n)2)当h=0且g(n) =d(n) 时，f(n)=d(n)既宽度优先策略，d(n):节点深度。3）h(n)称为启发函数。A算法：1 G=G0(G0=s),open=(s),closed=() ，f(s)=g(s)+ h(s) /s:初始状态2 Loop:if open=() then exit(fall)3 nfirst(open)h()4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先辈节点 计算f(n,mi)=g(n,mi)+h(mi),(自s经过n，mi 到目标节点的耗散值)openadd(open，mj) 标记mj到n的指针 (mj不在open，closed中) if f(n, mk)f(mk) then f(mk) f(n, mk)标记mk到n的指针(mk在open中)if f(n, mL)f(mL) then f(mL) f(n, mL)标记mL到n的指针(mL在closed中) add(mL,open),把mL放回到open中7 Open中的节点按f值升序排列 8 go loop例 八数码问题令：g(n)=d(n) 节点深度 h(n)=w(n) 不在位的数码个数(启发函数)则 f(n)=d(n)+w(n)如初始节点s的f值f(0)=d(0)+w(0)=0+4=4有4个数码不在位。对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h(n),即， 1) f(n)=g(n) 只考虑搜索过的路径已经耗费的费用；/分支界限算法 2）f(n)=h(n) 只考虑未来的发展趋势/爬山算法那么可以得到两种特殊的算法：爬山算法和分支界限算法。爬山算法：procedure Hill _Climbing1 n=s2 Loop: if goal(n) then exit(success)3mi expangd(n),计算每个h(mi) nextn h(mi)最小值的节点4 if h(n)h(nextn) then exit(fail)5 n nextn6go loop 优点，缺点分支界限算法f(n)=g(n)：Procedure Branch_Bound1 queue(s-s),g(s)=0 /queue中保存的是从s出发的路径。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH) /取第一条路径，及该路径的最后节点n4 if goal(n) then exit(success)5 mj expand(n), 计算g(mj)= g(n,mj) remove(s-n,queue),add(s-mj,queue) /删除原来的路径，添加长度加一的路径。6 queue队列中分支按g值升序排列7 GO LOOP例 下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从S到t的最佳路径。动态规划算法：Procedure dynamic_Programming1 queue(s-s),g(s)=0 /queue中保存的是从s出发的路径。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH) /取第一条路径，及该路径的最后节点n4 if goal(n) then exit(success)5 mj expand(n), 计算g(mj)= g(n,mj) remove(s-n,queue),add(s-mj,queue) /删除原来的路径，添加长度加一的路径。6 仅保留queue中到达某一公共节点路径中耗散值最小的路径，余者删除；queue队列中分支按g值升序排列7 GO LOOP讨论 a 动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。 b 如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达同一节点有多重路径的情况。C动态规划 改进的代价。比如上例中，增加一个城市。A算法总结：1 初始状态，open=（s）2 正常情况下（非成功非失败），取open中的第一个节点n，将n由open 转移到closed。3 扩充节点n ，将新节点加入到open中4修改某些节点的路径5 open中节点按照升序排列值得重视的一点：A算法失败的唯一原因是open表为空思考题：图中：s是起始点 t是目标节点；如果存在从s到t的一条最佳路径。而n是最佳路径上的一点。1）f*(s) f*(n) f*(t) 的关系2）如果f*(s)=10 ,g*(n)=4 问h*(n)=?A*算法（最佳图搜索算法）：A*算法定义： 对于算法A，如果有h（n） h*（n）,即h（n）以h*（n）为上界，则称 该算法称为A*算法。如果令h（n）=0，则满足h（n） h*（n） 这就是分支界限算法 和动态规划算法。再令g(n)=d(n) (d(n)是节点深度）则f(n)=d(n);A*算法就是宽度优先算法。宽度优先算法能找到最佳解。 例：第二章中八数码问题 令h(n)=w(n)=不在位数字个数。算法可采纳性：给定任意图，设存在从开始节点s到目标节点t的路径。如果算法能够结束在s到t的最佳路径上，则称该算法是可采纳的。A*是具有可采纳性。定理1 对于有限图，如果从s到t存在路径，则A算法一定成功结束。推论1.1 因为A*算法是A算法的一个特例。所以在有限图上如果如果从s到t存在路径，则A*算法一定成功结束。定理2对于无限图，如果存在s到t路径，则A*算法一定成功结束。推论2.1： open表中任一满足f(n) f*(s)的节点n最终都将被A*选作扩展节点。定理3：如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。推论3.1：A*选来扩展的节点都有f(n) f*(s)小结1如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。2 open表中所有满足f(n) f*(s)的节点n最终都将被A*选作扩展节点。3 A*选来扩展的节点都有f(n) f*(s) 4 f*(s)作为A*的一个衡量上限。h函数和A*算法的关系：本节重点来讨论h函数（即启发信息量）对A*算法搜索效率的影响总结。定义：给定两个A*算法A1 和A2，都有f(n1)=g(n1)+h(n1)，f(n2)=g(n2)+h(n2)如果对于所有非目标节点n，有h(n1) h(n2)，则算法A2 比算法A1有较多启发信息。讨论：启发信息与h函数值成正比。极端情况下，完全没有启发信息时h=0，则此时A*算法就是宽度优先算法。定理：给定两个A*算法A1 和A2 如果A2的启发式信息比A1多，则在任何存在节点s到目标节点t的路径上，搜索结束时，由A2扩展的每一个节点必定被A1扩展。(A1扩展的节点多)，注意搜索空间小，不代表能够找到最佳解。当h=0时，除最下面一层节点外，所有节点都进入closed表。求解路径如图红线所示。当考虑到h时，被扩充的节点只有s、c、 j，解路径相同h函数单调性限制单调性限制的作用是：避免重复计算某些节点的f值（主要对连通图而言）以便减少搜索代价。单调性定义：给定一个启发函数h，如果对于所有节点ni和nj (nj是ni的子节点)，如果满足 h(ni)-h(nj) c(ni,nj) h(t)=0,则称h满足单调性限制。上式可以写成h(ni)- h(nj)+ c(ni,nj)，可以理解为三角不等式。 定理5：如果好h(n)满足单调性限制条件，则A*算法