人工智能考试整理40

1、.：.；智能定义知识阈值实际 智能就是在宏大的搜索空间中迅速找到一个称心解的才干智能的综合性定义:智能是知识和智力的总和。其中知识是智能行为的根底。智能的特征:1具有记忆与思想才干存贮有感官得到的外界信息并加以处置如分析，计算，联想、决策等2具有感知才干：经过感官获取外部信息的才干。3具有自顺应才干 经过与外部世界交互学习，积累阅历，增长知识，以顺应环境变化。4具有表达才干经过言语、手势、表情等方式完成信息的输出。深蓝：可以模拟人的思想，进展博弈的计算机。1997年5月12日，一个名为“深蓝deep Blue 的IBM计算机系统战胜当时的国际象棋冠军 盖利.卡斯帕罗夫图灵测试：两个房间，一个是

2、人，一个是机器，测试者经过一系列的提问，假设提问题的人无法分辨是人还是机器在回答以下问题，那么以为该机器具有智能人工智能Artifical Intelligence，简称AI又称机智能machine intelligence，普通以为来源于美国1956年的一次夏季讨论达特茅斯会议在这次会议上，第一次提出了“Artifical Intelligence这个词。AI的本质问题：研讨如何制造出人造的智能机器或系统，来模拟人类的智能活动的才干，以延伸人们智能的科学。产生式系统由三个部分组成1综合数据库Globe Database 也称为：现实库，上下文等。 作用:存放问题求解的过程中产生的形状描画信息

3、。2规那么库Rule Base(问题本身知识、求解知识)也称为规那么基、规那么集等。作用：存放规那么知识。产生式规那么的普通表达方式：IF前提THEN(结论)即 ： 假设 那么.例：1数学定理 2IF A是一种动物 AND A 是哺乳动物 AND A 吃肉 THEN A 是高级动物 关于不准确推理 当规那么的前提成立时，结论并非完全成立。这种推理称为不准确推理。通常采用阈值方法来处理此类问题。3控制战略Control Strategy a 选择规那么库中的规那么与综合数据库的知现实进展匹配，匹配胜利的规那么为可用规那么，否那么为不可用规那么。 b 规那么冲突的处理可用规那么书1。c将选中的规那

4、么的结论放入综合数据库。产生式系统的特点： 1 方式化：一切规那么具有一样的方式2构造化：规那么见的关联比较简单，容易维护。3自燃性：规那么表达了因果关系，比较符合人们的思想方式，容易了解。4单一性：智能处置因果关系问题。5效率低，规那么匹配过程很大。产生式系统的适用范围：1知识杂乱、现实众多、无一致实际的领域2该领域的知识可以笼统出来3该领域的知识可分解为一组独立的动作，以便用规那么加以表示。概括说的说：问题空间从一个形状到另一个形状的转移序列独立的领域可采用产生式系统模拟。产生式系统普通性算法：1 DATA 初始数据库2 until DATA满足终了条件条件之前 do：3 Begin 在规

5、那么集中选择某一可用于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的走步序列。产生式系统的根本控制战略概括的讲：产生

6、式系统控制战略-搜索1不可撤回方式2试探性方式 a 回溯方式Backtracking b 图搜索方式Graph search1.不可撤回方式 根本战略：选择规那么时只依托部分知识信息，而不思索能否全局最正确选择，只能满足部分优化条件，用过的规那么不再撤回。特点： a 方法简单，容易实现 b 具有一定的局限性，适用范围小只可用于单极值情况 c 能够会呵斥规那么的多次反复运用。比如：爬山算法，不可用于处理多极值问题。关于 部分知识的利用 ：设计部分评价函数W(n),根据W(n)最大为原那么来选择规那么。例：八数码问题设：- W(n):不在位的数码个数 n：恣意形状目的形状：- W(n)=0 每个数

7、码就位最不利形状- W(n)= -8 每个数码都不在规定的位置2.回溯方式根本战略：试探性的选择一条规那么，假设发现此规那么不适宜，那么退回去另选其他规那么。关键在于回溯条件的设定。特点： a 适用性好(相对不可回撤方式) b 适用范围较大，在一定程度上能防止盲目性 c 可处理部分极值问题设计方法： a 确定适宜的回溯条件 b 充分利用可用知识来陈列规那么，减少回溯次数例：八数码游戏主要讨论回溯条件回溯条件： a 新产生的形状曾经在搜索过程中出现； b 运用规那么的数量曾经超越规定值(深度限制) c 当前形状，无可用规那么满足上述条件之一 那么产生回溯，每次回溯一层。图搜索方式根本战略： 它是

8、一种展开式搜索方法，把问题空间看成一张隐含图，从中搜索出一条解途径。特点： a 适用性好 b 能保管完好的搜索树 c 对于解空间较大的问题而言，搜索代价较大。例：八数码问题这是一个典型的宽度优先战略，所以搜索代价比较大。总结：三种控制战略的特点 1 不可撤回方式：沿一条途径单向延伸搜索2)回溯方式：可修正搜索途径3图搜索方式：展开式搜索，可保管完好的搜索树。产生式系统分类1.普通性产生式系统 根据规那么的运用方式，普通性产生式系统可以分为三种类型： 1正向系统数据驱动 采用正向推理方式，即由初始形状推理到目的形状，正向系统里的规那么是正向运用的:规那么的前提成立，那么规那么的结论成立。 2)反

9、向系统目的驱动系统采用反向推理方式：即由目的形状反向推理找到初始形状。反向系统的规那么是反向运用的：先假设规那么的结论成立，在寻觅使其成立的前提条件。 3双向系统 由数据、目的双向驱动，最后终止在某个中间形状。 例：数学证明思绪2.可交换产生式系统定义：满足以下性质的产生式系统称为可交换产生式系统 a 给定可以用于数据库D的规那么集R，对于运用R中的任何规那么后产生的任何数据库，规那么集R依然可用。(规那么适用性) b 假设目的条件被D满足，那么运用R中的任何规那么于D上所产生的任何数据库仍可满足目的条件。(数据库可用性) c 运用R中一个规那么序列于D上后，得到的数据库不随这规那么序列次序变

10、化而变化。规那么次序无关性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 en

11、dAI领域的知识分类 a 陈说性知识：用于描画综合数据库的形状。如现实等 b 过程性知识：用于规那么中表达问题的知识.如客观规律等 c 控制性知识：用于构成控制战略的知识算法、数据构造等AI系统的一个难题：知识表达问题，要可以客观的描画现实，简化求解过程，有效的提高求解效率，降低求解代价。产生式系统的搜索战略形状空间：由给定问题的一切能够的形状组成的空间相当于选集G搜索空间：按某种战略在形状空间中选取的部分空间G的子集解途径解空间：求解问题的一条有效途径。搜索战略的根本思绪：搜索空间必需包含解途径，假设问题有解，且尽量减少搜索空间。搜索战略的评价准那么：总体费用最低费用的划分： a 规那么运用

12、的费用：执行规那么时所花的费用 b 控制费用：选择规那么所花的费用。1.回溯战略2.图搜索战略3.启发式图搜索战略1A算法2爬山算法3分支界限算法4动态规划算法5A*算法6h函数与A*的关系7关于单调性限制8A*算法例如例 四皇后问题定义综合数据库：设：DATA=ij1=i,j=4,其中：ij表示棋子所在行列 如：24表示第二行第四列有一枚棋子由于棋盘上 可放入的棋子数为04个所以集合中元素数位0 4个，即lengthDATA=0 4图搜索的本质是从问题空间中找出一张包含目的节点的子图。图搜索的结果：1，一个完好的搜索图G。2一个解途径，用指针表示的解途径。Procedure GraphSea

13、rch1 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按照某种方式陈列

14、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

15、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不含

16、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是积木或者桌子。初始形

17、状时B、T、T,目的形状 可以表示B、C、T2定义操作:move(x,y)表示将积木x移到Y上 ；约束条件:a X顶部必需是空的 b 假设Y是积木，Y的顶部必需是空 c 同一种形状出现不得多于一次。1解题过程 2open表和closed表3节点样子画出整个图G 和解途径4程序何时终了 5改用深度优先如何？启发式图搜索战略：根本概念启发式图搜索的本质是利用启发信息有目的地进展搜索，减少搜索的盲目性。降低搜索空间 找到最正确解启发式信息用于处理open表中节点的陈列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大陈列一切节点。评价函数的目的：把最有希望得到最正确

18、解或者解的陈列在前面。途径 ：给定节点序列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):节点深度。3h(n)称为启发函数。A算法：1 G=G0(G0=s),

19、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

20、(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) 只思索搜索过的途径曾经耗

21、费的费用；/分支界限算法 2f(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中保

22、管的是从s出发的途径。2 Loop：ifqueue=0 then exitfail3 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 dyna

23、mic_Programming1 queue(s-s),g(s)=0 /queue中保管的是从s出发的途径。2 Loop：ifqueue=0 then exitfail3 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值

24、升序陈列7 GO LOOP讨论 a 动态规划与分支界限差别在于去掉公共途径的冗余部分，提高效率。 b 假设问题空间是树构造，动态规划与分支界限一样。由于对于树构造不存在到达同一节点有多重途径的情况。C动态规划 改良的代价。比如上例中，添加一个城市。A算法总结：1 初始形状，open=s2 正常情况下非胜利非失败，取open中的第一个节点n，将n由open 转移到closed。3 扩展节点n ，将新节点参与到open中4修正某些节点的途径5 open中节点按照升序陈列值得注重的一点：A算法失败的独一缘由是open表为空思索题：图中：s是起始点 t是目的节点；假设存在从s到t的一条最正确途径。而n

25、是最正确途径上的一点。1f*(s) f*(n) f*(t) 的关系2假设f*(s)=10 ,g*(n)=4 问h*(n)=?A*算法最正确图搜索算法：A*算法定义： 对于算法A，假设有hn h*n,即hn以h*n为上界，那么称 该算法称为A*算法。假设令hn=0，那么满足hn h*n 这就是分支界限算法 和动态规划算法。再令g(n)=d(n) (d(n)是节点深度那么f(n)=d(n);A*算法就是宽度优先算法。宽度优先算法能找到最正确解。 例：第二章中八数码问题 令h(n)=w(n)=不在位数字个数。算法可采用性：给定恣意图，设存在从开场节点s到目的节点t的途径。假设算法可以终了在s到t的最

26、正确途径上，那么称该算法是可采用的。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 ope

27、n表中一切满足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的启发式

28、信息比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)，可以了解为三角