人工智能技术导论总复习课件

人工智能总复习人工智能总复习第第1章章 人工智能概述人工智能概述n什么是人工智能？人工智能的研究目标和意义什么是人工智能？人工智能的研究目标和意义？n人工智能的研究学派、人工智能的研究学派、途径与方法途径与方法n人工智能的研究目标人工智能的研究目标n人工智能的主要领域（基于应用领域）人工智能的主要领域（基于应用领域）n人工智能基本技术人工智能基本技术第第3章章 图搜索技术图搜索技术n状态图知识表示状态图知识表示n状态图搜索状态图搜索q穷举式搜索穷举式搜索q启发式搜索启发式搜索q加权状态图搜索加权状态图搜索n与或图知识表示与或图知识表示n与或图搜索与或图搜索q启发式与或树搜索启发式与或树搜索n博弈树搜索博弈树搜索q极小极大分析法极小极大分析法q-剪枝剪枝状态图知识表示状态图知识表示n状态空间（状态空间（State SpaceState Space）q问题的状态空间是一个表示该问题全部的可能状态问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。及相互关系的图。q一般包含一般包含nS S：问题的可能有的初始状态的集合；：问题的可能有的初始状态的集合；nF F：操作的集合；：操作的集合；nG G：目标状态的集合。：目标状态的集合。n状态空间常记为三元序列状态空间常记为三元序列SG状态空间中问题求解（状态空间中问题求解（1）n在状态空间图中，问题求解过程转化为在图中寻找从初始在状态空间图中，问题求解过程转化为在图中寻找从初始状态状态S0出发到达目标状态出发到达目标状态Sg的路径问题，也就是寻找操作的路径问题，也就是寻找操作序列的问题。序列的问题。n状态空间的解为三元组状态空间的解为三元组qS0：某个初始状态某个初始状态qSg：某个目标状态某个目标状态qO：把：把Qs变换成变换成Qg的有限的操作序列的有限的操作序列O1,O2,Onq状态转换图状态转换图S1S3S2O1O2O3O4S0SgOn状态空间中问题求解（状态空间中问题求解（2）n状状态态图图搜搜索索：从从初初始始节节点点出出发发，沿沿着着与与之之相相连连的的边边试试探地前进，寻找目标节点的过程。探地前进，寻找目标节点的过程。n状状态态图图的的解解：搜搜索索成成功功后后，从从目目标标结结点点反反向向沿沿搜搜索索树树按按所所作作标标记记追追溯溯一一直直到到初初始始结结点点，所所得得到到一一条条从从初初始始结点到目标结点的路径就是问题的一个解。结点到目标结点的路径就是问题的一个解。状态图搜索状态图搜索n穷举式搜索穷举式搜索q广度优先广度优先q深度优先深度优先q有界深度优先有界深度优先n启发式搜索启发式搜索q全局择优（广度优先搜索全局择优（广度优先搜索+h(x)）q局部择优（深度优先搜索局部择优（深度优先搜索+h(x)）n加权状态图搜索加权状态图搜索q分支界限（广度优先搜索分支界限（广度优先搜索+g(x)）q最近择优最近择优/瞎子爬山（深度优先搜索瞎子爬山（深度优先搜索+g(x)）nA算法（一般树式搜索算法算法（一般树式搜索算法+f(x)）nA*算法（算法（h(x)=2then a=a-1 If a=1then a=4Pb：if b=2 then b=b-1 If b=1then b=4Pc：if c=2 then c=c-1 If c=1then c=4 广度优先搜索树广度优先搜索树Pb2，2，21，2，22，1，22，2，1PaPbPc4，2，21，1，2PaPc1，2，1Pb1，2，12，1，1PaPc2，2，4PaPbPc1，1，22，4，22，1，13，2，24，1，24，2，1PaPbPc深度优先搜索树深度优先搜索树Pb2，2，21，2，22，1，22，2，1PaPbPcPcPbPc4，2，21，1，2PaPc1，2，13，2，24，2，1PaPb4，1，22，2，2Pa3，1，23，2，1补充例题：加权状态图搜索n代价树如下图所示：分别给出宽度优先及深度优先搜索策略下的搜索过程和解。其中，F、I、J、L是目标节点。宽度优先搜索过程：宽度优先搜索过程：A C B GED M J，G（J）=6，解为：解为：A B E J深度优先搜索过程为：深度优先搜索过程为：A C GMPOL，G（L）=7，解为：解为：A CGL图搜索图搜索解：用宽度优先搜索搜索树为：用宽度优先搜索过程为：SABHCGDF解为：SABCF代价树搜索代价树搜索n下图是五城市间的交通路线图，下图是五城市间的交通路线图，A是出发地，是出发地，E是目的地，两城市间的交通费用（代价）如是目的地，两城市间的交通费用（代价）如图中数字所示。求图中数字所示。求A到到E的最小费用交通路线。的最小费用交通路线。代价树代价树AC1B1D1D2E1E2B2E4C2E33423454523图4-2广度优先搜索广度优先搜索n所以，最优路径为所以，最优路径为A-C-D-E扩展节点，将其子节点放入扩展节点，将其子节点放入open表中，计算各子节点的代价，并按各节点的代价表中，计算各子节点的代价，并按各节点的代价对对open表中全部节点按从小到大的顺序进行排序（队列）表中全部节点按从小到大的顺序进行排序（队列）深度优先搜索深度优先搜索n扩展节点，将其子节点按代价从小到大的顺序扩展节点，将其子节点按代价从小到大的顺序放到放到open表的首部（栈）表的首部（栈）435AC1B1D12AC1B143435AC1B1D18934E2B2E为目标节点，E2-D1-C1-A所以路径为A-设如图与或树，请分别按和代价法及最设如图与或树，请分别按和代价法及最大代价法求解树代价。大代价法求解树代价。n按和代价法：按和代价法：h(B)=7,h(C)=3,h(A)=7+3+5+6=21n按最大代价法：按最大代价法：h(B)=5,h(C)=2,h(A)=5+5=10BCDt2t1t4At357223621书82页图3-19 剪枝例7 72 24 4-1-12 24 4-2-2 6 64 43 34 45 56 6-5-5 6 68 86 63 31 1N2 26 68 822-23441-51242知识表示知识表示知 识表示谓词表示法产生式表示法框架表示法语义网络表示法框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。语义网络由节点和弧线或链线组成，节点用于表示物体、概念和状态，弧线用于表示节点间的关系。产生式系统由3个基本部分组成：规则库、综合数据库、控制系统。首先定义谓词，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。归结原理证明定理应用归结原理证明定理应用2 任何兄弟都有同一个父亲，任何兄弟都有同一个父亲，John和和Peter是兄弟，是兄弟，John的的父亲是父亲是David，问，问Peter的父亲是谁？的父亲是谁？解：第一步：定义谓词：解：第一步：定义谓词：设设Father(x,y)表示表示x是是y的父亲。的父亲。设设Brother(x,y)表示表示x和和y是兄弟。是兄弟。第二步：将已知事实、要证结论用谓词公式表示出来：第二步：将已知事实、要证结论用谓词公式表示出来：F1:xyz(Brother(x,y)Father(z,x)Father(z,y)F2:Brother(John,Peter)F3:Father(David,John)G:Father(u,Peter)归结原理证明定理应用归结原理证明定理应用第三步，将它们化成子句集，得第三步，将它们化成子句集，得F1：Brother(x,y)Father(z,x)Father(z,y),F2：Brother(John,Peter),F3：Father(David,John)G:Father(u,Peter)增配辅助谓词，即将其增配辅助谓词，即将其G的否定与谓词的否定与谓词ANSWER做析取。做析取。G:Father(u,Peter)ANSWER(u)第四步：应用归结原理进行归结。第四步：应用归结原理进行归结。（1）Brother(x,y)Father(z,x)Father(z,y)（2）Brother(John,Peter)（3）Father(David,John)（4）Father(u,Peter)ANSWER(u)（5）Brother(John,y)Father(David,y)1,3,=David/z,John/x（6）Brother(John,Peter)ANSWER(David)4,5，=David/u,Peter/y（7）ANSWER(David)2,6即即Peter的父亲是的父亲是David。产生式系统系统产生式系统系统设有如下问题：设有如下问题：（1）有五个相互可直达且距离已知的城市）有五个相互可直达且距离已知的城市A、B、C、D、E，如图所示；，如图所示；（2）某人从）某人从A地出发，去其它四个城市各参观一次后回到地出发，去其它四个城市各参观一次后回到A;（3）找一条最短的旅行路线）找一条最短的旅行路线请用产生式规则表示旅行过程。请用产生式规则表示旅行过程。解：解：综合数据库（综合数据库（x）：）：(x)中中x可以是一个字母，也可以是一个字符串。可以是一个字母，也可以是一个字符串。初始状态（初始状态（A）目标状态（目标状态（Ax1x2x3x4A）规则集：规则集：r1:IF L(S)=5 THEN GOTO(A)r2:IF L(S)5 THEN GOTO(B)r3:IF L(S)5 THEN GOTO(C)r4:IF L(S)5 THEN GOTO(D)r5:IF L(S)5 THEN GOTO(E)其中其中L(S)为走过的城市数，为走过的城市数，GOTO(x)为走向城市为走向城市x路线如下图所示路线如下图所示:(A)(AB)(AC)(AD)(AE)(A CB)(A CD)(ACE)(A CDB)(ACDE)(ACDEB)(ACDEBA)751010769108107起始目标推理推理推 理经典逻辑推理不确定与非单调推理归结演绎推理与/或形演绎推理自然演绎推理谓词逻辑的归结原理谓词逻辑的归结原理用谓词公式表示下列刑侦知识，并用归结原理求取结论。用谓词公式表示下列刑侦知识，并用归结原理求取结论。（1）用子句集表示下述知识）用子句集表示下述知识 A John是贼；是贼；B Paul喜欢酒喜欢酒 C Paul也喜欢奶酪也喜欢奶酪 D 如果如果Paul喜欢某物，则喜欢某物，则John也喜欢也喜欢 E 如果某人是贼，而且喜欢某物，则他可能会偷窃该物如果某人是贼，而且喜欢某物，则他可能会偷窃该物（2）求取结论：）求取结论：John可能会偷窃什么？可能会偷窃什么？（1）定义谓词）定义谓词thief（x）：表示）：表示x是贼是贼likes(x,y):表示某人表示某人x喜欢某物喜欢某物ymay_steal(x,y)：表示某人：表示某人x可能会偷某物可能会偷某物y将已知事实表示成谓词公式并化子句集将已知事实表示成谓词公式并化子句集A：thief(John)B:likes(Paul,wine)C:likes(Paul,cheese)D:x(likes(Paul,x)likes(Johnl,x)E:x y(thief(x)likes(x,y)may_steal(x,y)化子句集：化子句集：1：thief(John)2:likes(Paul,wine)3:likes(Paul,cheese)4:likes(Paul,z)likes(John,z)5:thief(x)likes(x,y)may_steal(x,y)目标为：目标为：x may_steal(John,x)目标谓词否定增配辅助谓词：目标谓词否定增配辅助谓词：6:may_steal(John,u)Answer(u)（2）利用归结原理求取答案）利用归结原理求取答案7:likes(John,y)may_steal(John,y)(1,5John/x)8:likes(John,wine)(2,4wine/z)9:likes(John,cheese)(3,4cheese/z)10:may_steal(John,wine)(7,8wine/y)11:may_steal(John,cheese)(7,9cheese/y)12:Answer(wine)(6,10wine/u)13:Answer(cheese)(6,11cheese/u)学科前沿讲座学科前沿讲座皇帝的新脑还是人类的终结皇帝的新脑还是人类的终结 一、关于人工智能一、关于人工智能 一、关于人工智能一、关于人工智能n从从数值计算数值计算文字、图像等文字、图像等多媒体信息处理多媒体信息处理初步实现了初步实现了Leibniz提出的提出的“将人的思维机器化将人的思维机器化”的思想的思想n让机器拥有人的心智让机器拥有人的心智成为计算机专家梦寐成为计算机专家梦寐以求的理想！以求的理想！1956年，年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父人工智能之父)等在美国达德茅斯等在美国达德茅斯大学召开第一届人工智能学术会议。大学召开第一届人工智能学术会议。会上首次使用会上首次使用“人工智能人工智能”这一术语。这一术语。标志着人工智能学科的诞生。标志着人工智能学科的诞生。一、关于人工智能一、关于人工智能1950年，年，W.格雷格雷.瓦尔特，可以自己充电的瓦尔特，可以自己充电的“乌龟乌龟”1960年，年，K.M.柯尔，模拟了一个柯尔，模拟了一个精神病疗法精神病疗法专家专家电脑下棋方面，电脑下棋方面，97年的年的“深蓝深蓝”(Deep Blue)，03年的年的“小深小深”(Deep Junior)一、关于人工智能一、关于人工智能n医生：我可以为你医生：我可以为你效劳吗效劳吗n病人：我不知道病人：我不知道n医生：请告诉我一医生：请告诉我一些情形些情形n病人：不病人：不n医生：请你说得仔医生：请你说得仔细些细些n病人：今天我厌烦病人：今天我厌烦得很得很n医生：你知道这是医生：你知道这是什么原因什么原因n病人：是的我老了病人：是的我老了n医生：请继续讲医生：请继续讲n病人：仿佛任何事病人：仿佛任何事情都激不起我的兴情都激不起我的兴致致n医生：请更多地医生：请更多地告诉我你的这种告诉我你的这种感觉感觉n病人：我也有些病人：我也有些知道为何我会这知道为何我会这样感觉样感觉n医生：是吗医生：是吗n病人：我似乎在病人：我似乎在想有一个家想有一个家n医生：什么东西医生：什么东西使你有这样的想使你有这样的想法法n病人：它是一种病人：它是一种挑战挑战n医生：为什么那医生：为什么那对你是重要的对你是重要的二、电脑能否实现人的智能？二、电脑能否实现人的智能？n机机器器n n体体力力n电脑电脑n n计算速度和计算速度和准确性准确性n人人脑脑n n思思维维n是否电脑能代替人脑实现智能？是否电脑能代替人脑实现智能？n一旦能够实现，这种被认为是特权的智能行一旦能够实现，这种被认为是特权的智能行为将受到挑战。为将受到挑战。二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？l人真实地回答问题并试图说服质问者，他确人真实地回答问题并试图说服质问者，他确实是人；实是人；l电脑被编好电脑被编好“说谎说谎”的程序，试图说服质问的程序，试图说服质问者它是人。者它是人。三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：n爱因斯坦曾经将其比喻为爱因斯坦曾经将其比喻为“与上与上帝的对话帝的对话”三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍 四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍n推荐网址推荐网址nhttp:/ 四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍n镶嵌图案镶嵌图案 埃舍尔的版埃舍尔的版画画(1957)四、对人工智能领域有影响的理论与书籍四、对人工智能领域有影响的理论与书籍问题求解问题求解逻辑推理与定理逻辑推理与定理证明证明自然语言理解自然语言理解自动程序设计自动程序设计专家系统专家系统机器学习机器学习神经网络神经网络机器人学机器人学五、目前人工智能的研究与应用领域五、目前人工智能的研究与应用领域模式识别模式识别机器视觉机器视觉智能控制智能控制智能检索智能检索智能调度与指挥智能调度与指挥分布式人工智能与分布式人工智能与Agent计算智能与进化智计算智能与进化智能能数据挖掘与知识发数据挖掘与知识发现现 六、计算机视觉中的困惑六、计算机视觉中的困惑n这些与人类视觉活动相比，显得微不足道。这些与人类视觉活动相比，显得微不足道。n人类视觉中的视觉含义的把握以及主观经验在视人类视觉中的视觉含义的把握以及主观经验在视觉中的作用，使机器不可能拥有的。觉中的作用，使机器不可能拥有的。六、计算机视觉中的困惑六、计算机视觉中的困惑六、计算机视觉中的困惑六、计算机视觉中的困惑 六、计算机视觉中的困惑六、计算机视觉中的困惑六、计算机视觉中的困惑六、计算机视觉中的困惑n著名的混沌理论著名的混沌理论“蝴蝶效应蝴蝶效应”：q美国气象学家洛伦芝（美国气象学家洛伦芝（Lorenz）于）于1960年代提出年代提出一篇论文，名叫一篇论文，名叫一只蝴蝶拍一下翅膀会不会在德一只蝴蝶拍一下翅膀会不会在德克萨斯州引起龙卷风？克萨斯州引起龙卷风？，他说，亚马逊流域的一，他说，亚马逊流域的一只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风暴。暴。q洛伦芝把这种现象戏称做洛伦芝把这种现象戏称做蝴蝶效应蝴蝶效应，意思即，意思即一一件表面上看来毫无关系、非常微小的事情，可能带件表面上看来毫无关系、非常微小的事情，可能带来巨大的改变。来巨大的改变。六、计算机视觉中的困惑六、计算机视觉中的困惑n眼睛和大脑的组合并不只具有眼睛和大脑的组合并不只具有“摄像机摄像机”般般的功能。的功能。n虽然，人们对虽然，人们对“视觉理解视觉理解”发生的机制还不发生的机制还不太清楚，但可以肯定其中含有非线性突变的太清楚，但可以肯定其中含有非线性突变的因素，而且导致某种结果的因素是不确定的。因素，而且导致某种结果的因素是不确定的。（即蝴蝶效应）（即蝴蝶效应）n“视觉理解视觉理解”中抹不去的主观因素不可能通中抹不去的主观因素不可能通过确定的算法给出。过确定的算法给出。七、展望七、展望n在计算机上要实现人的心智，充在计算机上要实现人的心智，充满困境。满困境。n要冲破这一困境，必须有理论性要冲破这一困境，必须有理论性的突破：的突破：n大自然的机大自然的机理理+算法算法 七、展望七、展望n问题的解决不依赖于复杂的逻辑运算，而问题的解决不依赖于复杂的逻辑运算，而是利用装置本身的复杂性功能。是利用装置本身的复杂性功能。七、展望七、展望n大自然的机大自然的机理理+算法算法n目前，在计算原理和模式方面出现了一些目前，在计算原理和模式方面出现了一些新的尝试：新的尝试：p生物计算生物计算p量子计算量子计算p光子计算光子计算p