人工智能复习幻灯片

复习•第0章绪论•第1章搜索问题•第2章与或图搜索问题•第3章谓词逻辑与归结原理•第4章知识表示方法•第5章不确定性推理•第6章机器学习•第7章高级搜索1第0章绪论主要知识点：人工智能的定义人工智能的研究目标人工智能的三个主要学派人工智能的主要研究应用领域。2第0章绪论•人工智能的定义研究怎样使计算机模仿人脑所从事的感知、推理、学习、思考、规划等思维活动，来解决需要用人类智能才能解决的问题。3第0章绪论人工智能的研究目标近期目标建造智能计算机代替人类的部分智力劳动远期目标用自动机模仿人类的思维过程和智能行为4第0章绪论•符号主义（Symbolists),又称逻辑主义(Logic's),心理学派(Psychlogism),计算机学派(Computerism).原理主要为物理符号系统(符号操作系统），认为人工智能源于数理逻辑，人的认知基元是符号,认知过程就是符号操作过程，人和计算机系统都是一个物理符号系统.其方法:以功能模拟人的智能5第0章绪论•联结主义(Connectionism),又称仿生学派(Bionicisism),生理学派(Physiologism).主要原理为神经网络及神经网络间的连接机制与学习算法，认为人工智能源于仿生学.特别是人脑模型的研究，认为人的认知思维基元是神经元,用大脑工作模式代替电脑工作模式。其方法:以结构模拟人的智能6第0章绪论•联结主义(Connectionism),又称仿生学派(Bionicisism),生理学派(Physiologism).主要原理为神经网络及神经网络间的连接机制与学习算法，认为人工智能源于仿生学.特别是人脑模型的研究，认为人的认知思维基元是神经元,用大脑工作模式代替电脑工作模式。其方法:以结构模拟人的智能78第0章绪论人工智能研究论域•自然语言理解与机器翻译•数据库的智能检索•专家咨询系统•定理证明•博弈•机器人学•自动程序设计•组合调度问题•感知问题第1章搜索问题•主要知识点：状态空间表示法盲目搜索和启发式搜索的特点宽度优先搜索、深度优先搜索、分支界限法、最佳优先搜索法、A算法、A*算法9•问题的状态空间(statespace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、算符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。•图搜索的定义—一种计算机在状态图中寻找路径的方法。第1章搜索问题10•深度优先搜索首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索或纵向搜索。深度优先搜索算法是一种“后进先出”的算法。第1章搜索问题11八数码魔方的深度优先搜索树第1章搜索问题12•宽度优先搜索以接近起始节点的程度逐层扩展节点的搜索方法(breadth-firstsearch)，这种盲目(无信息)搜索叫做宽度优先搜索或横向搜索。宽度优先搜索算法是一种“先进先出”的算法。第1章搜索问题131238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码魔方的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567428293031123845671238456712384567123845673213456123678381238456739扩展26个节点，共生成46个节点之后，才得到目标14•分支界限法分支界限法是优先扩展当前具有最小代价的分支路径的节点，其评价函数为f(n)=g(n)，直到生成目标节点为止。第1章搜索问题15•A算法定义每个节点n的估价函数f(n)=g(n)+h(n)从起始节点到节点n的代价g(n)以及从节点n到达目标节点代价的估算值h(n)，找出一个最有希望的节点来扩展。第1章搜索问题16•A*算法•在A算法中，如果满足条件：h(n)≤h*(n)则A算法称为A*算法。在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。第1章搜索问题17•8数码问题–h1(n)=“不在位”的将牌数–h2(n)=将牌“不在位”的距离和2831647512345768将牌1：1将牌2：1将牌6：1将牌8：2八数码魔方（8-puzzleproblem）12384567（目标状态）12384567（初始状态）1857①④⑤⑥③123845671238456712384567(1+4=5)(1+6=7)(1+6=7)②123845671238456712384567(2+5=7)(2+5=7)(2+3=5)1238456712384567(3+2=5)(3+4=7)12384567(4+1=5)8132456712384567(5+0=5)(5+2=7)123846(0+5=5)7⑦八数码魔方的A*算法搜索树1957①④⑤⑥③123845671238456712384567(1+4=5)(1+6=7)(1+6=7)②123845671238456712384567(2+5=7)(2+5=7)(2+3=5)1238456712384567(3+2=5)(3+4=7)12384567(4+1=5)8132456712384567(5+0=5)(5+2=7)123846(0+5=5)7⑦八数码魔方的A*算法搜索树20第三章与或图搜索问题•主要知识点：与或图的启发式搜索算法AO*博弈搜索的极大极小法-剪枝法。21第三章与或图搜索问题•启发式搜索算法AO*过程：图生成过程，即扩展节点–从最优的局部途中选择一个节点扩展计算耗散值的过程–对当前的局部图重新新计算耗散值22第三章与或图搜索问题AO*算法可划分成两个操作阶段：第一阶段是完成自顶向下的图生成操作,先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终结点进行扩展，并对其后继结点赋估计耗散值和加能解标记。23第三章与或图搜索问题第二阶段是完成自下向上的耗散值修正计算、连接符(即指针)的标记以及结点的能解标记。耗散值的修正从刚被扩展的结点n开始，其修正耗散值q(n)取估计h(n)的所有值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈结点的耗散值，只有下层耗散值修正后，才可能影响上一层结点的耗散值，因此必须自底向上一直修正到初始结点。这由算法中的内循环过程完成。2425AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n826目标目标初始节点n0n1n2n3n4n5n6n7n8n4(1)红色：4黄色：3初始节点n0n1(2)n5(1)27目标目标初始节点n0n1n2n3n4n5n6n7n8红色：4黄色：6n3(4)初始节点n0n4(1)n5(1)n1n2(4)528目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)229目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21第三章与或图搜索问题•对各个局面进行评估–评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。–评估的方法：用评价函数对棋局进行评估。赢的评估值设为+∞，输的评估值设为-∞，平局的评估值设为0。–评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。30第三章与或图搜索问题•正方（MAX节点）从所有子节点中，选取具有最大评估值的节点。•反方（MIN节点）从其所有子节点中，选取具有最小评估值的节点。•反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极小极大搜索法。31第三章与或图搜索问题•在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子(每次一枚)，谁先取得三线的结果就取胜。设程序方MAX的棋子用(×)表示，MAX先走。对手MIN的棋子用(o)表示。32第三章与或图搜索问题估计函数f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线数)－(所有空格都放上MIN的棋子之后，MIN的三子成线的总数)若P是MAX获胜的格局，则f(p)=+∞；若P是MIN获胜的格局，则f(p)＝-∞。33估计函数值f(p)=6-4=2估计函数f(p)=(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角)数)－(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)当前棋局f(p)=2第三章与或图搜索问题34第三章与或图搜索问题35•-剪支法的引入在极小极大法中，必须求出所有终端节点的评估值，当预先考虑的棋步比较多时，计算量会大大增加。为了提高搜索的效率，引入了通过对评估值的上下限进行估计，从而减少需进行评估的节点范围的-剪支法。第三章与或图搜索问题36作为正方出现的MAX节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评估值为时，则对于其它的子节点，如果有高过的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为。总之，该MAX节点的评估值不会低于，这个就称为该MAX节点的评估下限值。MAX节点的评估下限值第三章与或图搜索问题37•MIN节点的评估上限值作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评估值为时，则对于其它子节点，如果有低于的，就取那个低于的值作为该MIN节点的评估值；如果没有，则该MIN节点的评估值取。总之，该MIN节点的评估值不会高过，这个就称为该MIN节点的评估上限值。第三章与或图搜索问题38•剪支法MAX节点MIN节点=剪支ABCD设MAX节点的下限为，则其所有的MIN子节点中，其评估值的上限小于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。第三章与或图搜索问题39设MIN节点的上限为，则其所有的MAX子节点中，其评估值的下限大于等于的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了剪支。MAX节点MIN节点=剪支ABCD剪支法第三章与或图搜索问题40MAX节点(5,)35652164(6,)(2,)(-,5)(-,2)(5,)MIN节点终端节点剪支剪支ABCDEFGHIJKLNOMMAX节点第三章与或图搜索问题41第四章谓词逻辑与归结原理主要知识点：谓词逻辑表示的语言与方法谓词归结子句形谓词逻辑归结原理Herbrand定理42例：将下式化为Skolem标准形：～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))–解：第一步，消去→号，得：～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))–第二步，～深入到量词内部，得：(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))–第三步，变元易名，得(x)(y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))–第四步，存在量词左移，直至所有的量词移到前面，(x)(y)(u)(v)(P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式43–第五步，消去“”（存在量词），略