人工智能课件第一次课

人工智能原理与实践

ArtificialIntelligence:PrinciplesandApplications杨丰本课程的安排

CoursePlanning授课学时：30学时1-10周实验学时：18机时2-10周平时和实验成绩：20分考试：80分（在第十周随堂考）课程结构第一章绪论

（1*3=3学时）-1人工智能的界定人工智能的学科范畴人工智能的研究方法与应用人工智能的发展简史与趋势第二章游戏软件的设计

（2*3=9学时）人工智能与游戏追击与逃跑-2运动模式-3基本路径探索-4第三章搜索技术

（5*3=15学时）A*搜索算法-5有限状态机-6模糊逻辑-7概率概论-8遗传算法-9第四章优化算法及产生式规则

（1*3=3学时）-10

最优化问题产生式规则第一章绪论

Introduction第一节人工智能的界定第二节人工智能的学科范畴第三节人工智能的研究方法与应用第四节人工智能的发展简史与趋势第一节人工智能的界定

DefiningAI(ArtificialIntelligence)人工智能（AI）是研究和设计具有智能行为的计算机程序，使其如同具有智能行为的人或动物一样去执行任务。

定义1.1智能机器

(Intelligentmachine)能够在各类环境中自主地或交互地执行各种拟人任务（anthropomorphictask）的机器。定义1.2人工智能学科是计算机科学中涉及研究、设计和应用智能机器的一个分支。定义1.3人工智能（能力）人工智能（能力）是智能机器所执行的通畅与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。定义1.4人工智能是一种使计算机能够思维、使机器具有智力的激动人心的新尝试。定义1.5人工智能是那些与人的思维、决策、问题求解和学习等有关活动的自动化。定义义1.6人工工智智能能是是用用计计算算模模型型进进行行研研究究的的智力力行行为为。。定义义1.7人工工智智能能是是研研究究那那些些使使理理解解、、推推理理和和行行为为成成为为可可能能的的计算算。定义义1.8人工工智智能能是是一一种种能能够够执执行行需需要要人人的的智智能能的的创创造造性性机机器器的的技术术。定义义1.9人工工智智能能研研究究如如何何通通过过使使计算算机机做做事事而让让人人过过得得更更好好。。定义义1.10人工工智智能能是是一一门门通通过过计计算算过过程程力力图图理理解解和和模模仿仿智智能能行行为为的的学科科。定义义1.11人工工智智能能是是计计算算机机科科学学中中与与智智能能行行为为的的自自动动化化有有关关的的一一个个分支支。图灵灵测测试试当一一个个人人与与一一个个封封闭闭房房间间里里的的人人或或者者机机器器交交谈谈时时，，如如果果他他不不能能分分辨辨自自己己问问题题的的回回答答是是计计算算机机还还是是人人给给出出时时，，则则称称该该机机器器是是具具有有智智能能的的。。以以往往该该试试验验几几乎乎是是衡衡量量机机器器人人工工智智能能的的唯唯一一标标准准，，但但是是从从九九十十年年代代开开始始，，现现代代人人工工智智能能领领域域的的科科学学家家开开始始对对此此试试验验提提出出异异议议：：反反对对封封闭闭式式的的，，机机器器完完全全自自主主的的智智能能；；提提出出与与外外界界交交流流的的，，人人机机交交互互的的智智能能。。计算算机机需需要要的的能能力力自然然语语言言处处理理知识识表表示示自动动推推理理机器器学学习习计算算机机视视觉觉机器器人人技技术术第二二节节人人工工智智能能的的学学科科范范畴畴人工工智智能能是是一一门门新新兴兴的的边边缘缘科科学学，，是是自自然然科科学学和和社社会会科科学学的的交交叉叉学学科科，，吸吸取取了了自自然然科科学学和和社社会会科科学学的的最最新新成成就就，，以以思思维维和和智智能能为为核核心心，，形形成成具具有有自自身身研研究究特特点点的的新新的的体体系系。。人工工智智能能及及其其相相关关学学科科人工工智智能能的的基基础础哲学学-知识识从从哪哪里里来来？？知知识识如如何何导导致致行行动动的的？？数学学-如何何用用不不确确定定的的知知识识进进行行推推理理？？经济济学学-如何何决决策策获获得得最最大大利利益益？？神经经学学-人脑脑如如何何处处理理信信息息？？心理理学学-人类类如如何何思思考考和和行行动动的的？？计算算机机工工程程学学-如何何能能够够创创造造出出能能干干的的计计算算机机？？控制制论论-人工工制制品品如如何何能能在在自自己己的的控控制制下下运运转转？？语言言学学-语言言和和思思维维是是怎怎么么联联系系起起来来的的？？人工工智智能能各各学学派派的的认认知知观观符号号主主义义（（symbolicism）-逻辑辑主主义义（（logicism）、、心心理理学学派派（（phychologism）或或计计算算机机学学派派，，主主要要为为物物理理符符号号系系统统假假设设和和有有限限合合理理性性原原理理。。来源源于于-数理理逻逻辑辑连接接主主义义（（connectionism）-仿生生学学派派（（bionicsism）、、生生物物学学派派（（physiologism），，主主要要为为神神经经网网络络及及神神经经网网络络间间的的连连接接机机制制与与学学习习算算法法。。行为为主主义义（（actionism）-进化化主主义义(evolutionism）或或控控制制论论学学派派（（cyberneticsism）主要要为为控控制制论论及及感感知知-动作作型型控控制制系系统统。。人工工智智能能成成功功的的实实例例1953年，，美美国国乔乔治治敦敦大大学学组组织织了了第第一一次次机机器器翻翻译译的的实实际际实实验验。。1954年7月，，IBM公司司在在701计算算机机上上做做了了俄俄译译英英的的公公开开表表演演。。1956年，，Newell(艾伦伦.纽厄厄尔尔)和Simon(西蒙蒙)等人人首首先先取取得得突突破破，，他他们们编编的的程程序序LogicTheorist(应用用启启发发式式技技术术)证明明了了《数学学原原理理》第二二章章中中的的三三十十八八条条定定理理，，又又于于1963年证证明明了了该该章章中中的的全全部部五五十十二二条条定定理理，，走走上上了了以以计计算算机机程程序序来来模模拟拟人人类类思思维维的的道道路路，，第第一一次次把把求求解解方方法法和和问问题题的的领领域域知知识识分分离离开开。。1958年定定理理证证明明方方面面取取得得新新成成就就，，美美籍籍数数理理逻逻辑辑学学家家王王浩浩在在IBM704计算算机机上上以以3-5分钟钟证证明明了了《数学学原原理理》有关关命命题题演演算算的的全全部部220条定定理理，，还还用用了了几几分分钟钟证证明明了了该该书书中中带带等等式式的的谓谓词词演演算算的的150条定定理理中中的的85%，1959年再再接接再再厉厉，，仅仅用用了了8.4分钟钟就就证证明明了了以以上上全全部部定定理理。。1959年，，IBM公司司的的Gelernter(格伦伦特特尔尔)研制制出出平平面面几几何何证证明明程程序序。。智能能体体Agent智能体传感器执行器？环境感知行动第三三节节主主要要的的应应用用领领域域1.自然然语语言言理理解解（（NaturalLanguageUnderstanding）自然然语语言言是是人人类类之之间间信信息息交交流流的的主主要要媒媒介介。。，，由由于于人人类类有有很很强强的的理理解解自自然然语语言言的的能能力力，，因因此此互互相相间间的的信信息息交交流流显显得得轻轻松松自自如如。。目前前计计算算机机系系统统和和人人类类之之间间的的交交互互几几乎乎还还只只能能使使用用严严格格限限制制的的各各种种非非自自然然语语言言，，因因此此解解决决计计算算机机系系统统能能理理解解自自然然语语言言的的问问题题，，引引起起人人们们的的兴兴趣趣和和重重视视，，一一直直是是人人工工智智能能领领域域的的重重要要研研究究课课题题之之一一。。实现现机机器器翻翻译译过过程程中中，，如如果果计计算算机机确确实实会会理理解解一一个个句句子子的的意意义义，，那那么么就就可可能能进进行行释释义义，，从从而而能能较较通通顺顺地地给给出出译译文文。。目目前前人人工工智智能能研研究究中中，，在在理理解解有有限限范范围围的的自自然然语语言言对对话话和和理理解解用用自自然然语语言言表表达达的的小小段段文文章章或或故故事事方方面面的的程程序序系系统统已已有有一一些些进进展展，，但但由由于于理理解解自自然然语语言言涉涉及及对对上上下下文文背背景景知知识识的的处处理理以以及及根根据据这这些些知知识识进进行行推推理理的的一一些些技技术术，，因因此此实实现现功功能能较较强强的的理理解解系系统统仍仍是是一一个个比比较较艰艰巨巨的的任任务务。。主要要的的应应用用领领域域2.数据据库库的的智智能能检检索索（（IntelligentRetrievalfromDatabase）数据据库库系系统统是是存存储储某某个个学学科科大大量量事事实实的的计计算算机机系系统统，，随随着着应应用用的的进进一一步步发发展展，，存存储储信信息息量量愈愈来来愈愈庞庞大大，，因因此此解解决决智智能能检检索索的的问问题题便便具具有有实实际际意意义义。。智智能能信信息息检检索索系系统统应应具具有有如如下下的的功功能能：：（（1）能能理理解解自自然然语语言言，，允允许许用用自自然然语语言言提提出出各各种种询询问问；；（（2）具具有有推推理理能能力力，，能能根根据据存存储储的的事事实实，，演演绎绎出出所所需需的的答答案案；；（（3）系统统拥有有一定定常识识性知知识，，以补补充学学科范范围的的专业业知识识。系系统根根据这这些常常识，，将能能演绎绎出更更一般般询问问的一一些答答案来来。实实现这这些功功能要要应用用人工工智能能的方方法。。主要的的应用用领域域3.专家咨咨询系系统（（ExpertConsultingSystems）专家咨咨询系系统就就是一一种智智能的的计算算机程程序系系统，，该系系统存存储有有某个个专门门领域域中经经事先先总结结、并并按某某种格格式表表示的的专家家知识识（构构成知知识库库），，以及及拥有有类似似于专专家解解决实实际问问题的的推理理机制制（组组成推推理系系统））。系系统能能对输输入信信息进进行处处理，，并运运用知知识进进行推推理，，做出出决策策和判判断，，其解解决问问题的的水平平达到到专家家的水水准，，因此此能起起到专专家的的作用用或成成为专专家的的助手手。专家系系统的的开发发和研研究是是人工工智能能研究究中面面向实实际应应用的的课题题，受受到人人们的的极大大重视视。已已开发发的系系统数数以百百计，，应用用领域域涉及及化学学、医医疗、、地质质、气气象、、交通通、教教育、、军事事等，，可以以说只只要有有专家家工作作的场场合，，就可可以开开发专专家系系统。。目目前专专家系系统主主要采采用基基于规规则的的演绎绎技术术，开开发专专家系系统的的关键键问题题是知知识表表示、、应用用和获获取技技术，，困难难在于于许多多领域域中专专家的的知识识往往往是琐琐碎的的，不不精确确的或或不确确定的的，因因此目目前研研究仍仍集中中在这这一核核心课课题。。对专家家系统统开发发工具具的研研制发发展也也很迅迅速。。主要的的应用用领域域4.定理证证明（（TheoremProving）数学领领域中中对臆臆测的的定理理寻求求一个个证明明，一一直被被认为为是一一项需需要智智能才才能完完成的的任务务。证证明定定理时时，不不仅需需要有有根据据假设设进行行演绎绎的能能力，，而且且需要要有某某些直直觉的的技巧巧。例例如数数学家家在求求证一一个定定理时时，会会熟练练地运运用他他丰富富的专专业知知识，，猜测测应当当先证证明哪哪一个个引理理，精精确判判断出出已有有的哪哪些定定理将将起作作用，，并把把主问问题分分解为为若干干子问问题，，分别别独立立进行行求解解。因因此人人工智智能研研究中中机器器定理理证明明很早早就受受到注注视，，并取取得不不少成成果。。例例如使使用谓谓词逻逻辑语语言，，其演演绎过过程的的形式式体系系研究究，帮帮助人人们更更清楚楚地理理解推推理过过程的的各个个组成成部分分。因此机机器定定理证证明的的研究究具有有普遍遍意义义。主要的的应用用领域域5.博弈（（GamePlaying）博弈被被认为为是智智能的的活动动，人人工智智能中中主要要是研研究下下棋程程序，，在六六十年年代就就出现现了很很有名名的西西洋跳跳棋和和国际际象棋棋的程程序，，并达达到了了大师师的水水平。。进入入90年代，，IBM公司以以其雄雄厚硬硬件基基础，，支持持开发发后来来被称称之为为“深深蓝””的国国际象象棋系系统，，并为为此开开发了了专用用的芯芯片，，以提提高计计算机机的搜搜索速速度。。1996年2月，与与国际际象棋棋世界界冠军军卡斯斯帕罗罗夫进进行了了第一一次比比赛，，经过过六个个回合合的比比赛之之后，，“深深蓝””以2：4告负。。1997年5月，系系统经经过改改进以以后，，“深深蓝””又第第二次次与卡卡斯帕帕罗夫夫交锋锋，并并最终终以3.5：2.5战胜了了卡斯斯帕罗罗夫，，在世世界范范围内内引起起了轰轰动。。博博弈问问题为为搜索索策略略、机机器学学习等等问题题的研研究课课题提提供了了很好好的实实际背背景，，所发发展起起来的的一些些概念念和方方法对对其他他人工工智能能问题题也很很有用用。主要的的应用用领域域6.机器人人学（（Robotics）由于自自动装装配、、海洋洋开发发、空空间探探索等等实际际问题题的需需要，，对机机器的的智能能水平平提出出了更更高的的要求求。特特别是是危险险环境境，人人们难难以胜胜任的的场合合更迫迫切需需要机机器人人，从从而推推动了了智能能机器器的研研究。。机机器人人学的的研究究推动动了许许多人人工智智能思思想的的发展展，有有一些些技术术可在在人工工智能能研究究中用用来建建立世世界状状态模模型和和描述述世界界状态态变化化的过过程。。关于于机器器人动动作规规划生生成和和规划划监督督执行行等问问题的的研究究，推推动了了规划划方法法的发发展。。此外外由于于智能能机器器是一一个综综合性性的课课题，，除机机械手手和步步行机机构外外，还还要研研究机机器视视觉、、触觉觉、听听觉等等传感感技术术，以以及机机器人人语言言和智智能控控制软软件等等。可可以看看出这这是一一个涉涉及精精密机机械、、信息息传感感技术术、人人工智智能方方法、、智能能控制制以及及生物物工程程等学学科的的综合合技术术。主要的的应用用领域域7.自动程程序设设计（（AutomaticProgramming）自动程程序设设计的的任务务是设设计一一个程程序系系统，，它接接受关关于所所设计计的程程序要要求实实现某某个目目标的的非常常高级级的描描述作作为其其输入入，然然后自自动生生成一一个能能完成成这个个目标标的具具体程程序。。在某某种意意义上上来说说，编编译程程序实实际就就是去去做"自动程程序设设计"的工作作。编编译程程序接接受一一段有有关干干某件件事情情的源源码说说明（（源程程序）），然然后转转换成成一个个目标标码程程序（（目的的程序序）去去完成成这件件事情情。而而这里里所说说的自自动程程序设设计相相当于于一种种"超级编编译程程序"，它要要求能能对高高级描描述进进行处处理，，通过过规划划过程程，生生成得得到所所需的的程序序。因因而自自动程程序设设计所所涉及及的基基本问问题与与定理理证明明和机机器人人学有有关，，要用用到人人工智智能方方法来来实现现，它它也是是软件件工程程和人人工智智能相相结合合的课课题。。自自动动编制制出一一份程程序来来获得得某种种指定定结果果的任任务同同论证证一份份给定定的程程序将将获得得某种种指定定结果果的任任务是是紧密密相关关的，，前者者也称称程序序综合合，后后者称称为程程序验验证。。许多多自动动程序序设计计系统统将产产生一一份输输出程程序的的验证证作为为额外外的收收益。。自自动程程序设设计研研究的的重大大贡献献之一一是把把程序序调试试的概概念作作为问问题求求解的的策略略来使使用。。实践践已经经发现现，对对程序序设计计或机机器人人控制制问题题，先先产生生一个个代价价不太太高的的有错错误的的解，，然后后再进进行修修改的的作法法，要要比坚坚持要要求第第一次次得到到的解解就完完全没没有缺缺陷的的作法法，通通常效效率要要高得得多。。主要的的应用用领域域8.组合调调度问问题（（CombinatorialandSchedulingProblems）有许多多实际际的问问题是是属于于确定定最佳佳调度度或最最佳组组合的的问题题，例例如旅旅行商商问题题就是是其中中之一一。这这个问问题是是要求求给推推销员员确定定一条条最短短的旅旅行路路线，，他的的旅程程是从从某一一个城城市出出发，，然后后遍访访他所所要访访问的的城市市，而而且每每个城城市只只访问问一次次，然然后回回到出出发城城市。。该问问题的的一般般化提提法是是：对对由几几个节节点组组成的的一个个图的的各条条边，，寻找找一条条最小小耗费费的路路径，，使得得这条条路径径只对对每一一个节节点穿穿行一一次。。在在大大多数数的这这类问问题中中，随随着求求解问问题规规模的的增大大，求求解程程序都都面临临着组组合爆爆炸问问题。。这些些问题题中有有几个个（包包括旅旅行商商问题题）是是属于于计算算理论论家称称为NP-完全性性一类类的问问题。。用用现在在知道道的最最佳方方法求求解NP-完全性性问题题，所所花费费的时时间是是随着着问题题规模模增大大按指指数方方式增增长，，但迄迄今还还不知知道是是否有有更快快的方方法（（如只只涉及及多项项式时时间））存在在。人人工智智能学学者们们曾经经研究究过若若干种种组合合问题题的求求解方方法，，他们们的努努力主主要集集中在在使"时间-问题大大小"曲线的的变化化尽可可能地地缓慢慢，即即使它它必须须按指指数方方式增增长。。此外外有关关问题题领域域的知知识，，确实实是一一些较较有效效的求求解方方法的的关键键因素素，为为处理理组合合问题题而发发展起起来的的许多多方法法，对对其他他组合合爆炸炸不甚甚严重重的问问题也也是有有用的的。主要的的应用用领域域9.感知问问题（（PerceptionProblems）人工智智能研研究中中，已已经给给计算算机系系统装装上摄摄象机机输入入以便便能够够"看见"周围的的东西西，或或者装装上话话筒以以便能能"听见"外界的的声音音。视视觉和和听觉觉都是是感知知问题题，都都涉及及到要要对复复杂的的输入入数据据进行行处理理。实实验表表明有有效的的处理理方法法要求求具有有"理解"的能力力，而而理解解则要要求大大量有有关感感受到到的事事物的的许多多基础础知识识。在在人人工智智能中中研究究的感感知过过程通通常包包含一一组操操作，，例如如可见见的景景物由由传感感器编编码，，并被被表示示为一一个灰灰度数数值的的矩阵阵，这这些灰灰度数数值由由检测测器加加以处处理，，检测测器搜搜索主主要图图象的的成份份，如如线段段、简简单曲曲线、、角等等等。。这些些成份份又被被处理理以便便根据据景物物的表表面和和形状状来推推测有有关景景物三三维特特征的的信息息，其其最终终目标标则是是利用用某个个适当当的模模型来来表示示该景景物。。例如如一个个高层层描述述组成成的模模型是是："一座山，山山顶上有一一棵树，山山上牛正在在吃草"。整整个感知问问题的要点点是建立一一个精炼的的表示来取取代难以处处理的极其其庞大的、、未经加工工的输入数数据，这种种最终表示示的性质和和质量取决决于感知系系统的目标标。例如若若颜色是重重要的，则则系统必须须予以重视视；若空间间关系和变变量是重要要的，则系系统必须给给予精确的的判断。不不同的系统统将有不同同的目标，，但所有的的系统都必必须把来自自输入多得得惊人的感感知数据压压缩为一种种容易处理理和有意义义的描述。。在在视觉问题题中，感知知一幅景物物的主要困困难是候选选描述的数数量太多。。有一种策策略是对不不同层次的的描述作出出假设，然然后再测试试这些假设设，这种假假设-测试的策略略给这个问问题提供了了一种方法法，它可应应用于感知知过程的不不同层次上上。此外假假设的建立立过程还要要求大量有有关感知对对象的知识识。感感知问题题除了信号号处理技术术外，还涉涉及知识表表示和推理理模型等一一些人工智智能技术。。第四节人人工智能的的

发展简简史与趋势势人工智能（（ArtificialIntelligence）是计算机机科学、控控制论、信信息论、神神经生理学学、心理学学、语言学学等多种学学科互相渗渗透而发展展起来的一一门综合性性新学科，，其诞生可可追溯到50年代中期。。1956年夏季，在在美国Dartmouth大学，由年年青数学助助教J.McCarthy（现斯坦福福大学教授授）和他的的三位朋友友M.Minsky（哈佛大学学年青数学学和神经学学家，现MIT教授）、N.Lochester（IBM公司信息研研究中心负负责人）和和C.Shannon（贝尔实验验室信息部部数学研究究员）共同同发起，邀邀请IBM公司的T.More和A.Samuel、MIT的O.Selfridge和R.Solomonff以及RAND公司和Carnagie工科大学的的A.Newell和（均为CMU教授）等人人参加夏季季学术讨论论班，历时时两个月。。这十位学学者都是在在数学、神神经生理学学、心理学学、和计算算机科学等等领域中从从事教学和和研究工作作的学者，，在会上他他们第一次次正式使用用了人工智智能（AI）这一术语语，从而开开创了人工工智能的研研究方向。。1.萌芽期（1956年以前）公元850年，古希腊腊就有制造造机器人帮帮助人们劳劳动的神话话传说。在我国公元元前900多年，也有有歌舞机器器人传说的的记载，这这说明古代代人就有人人工智能的的幻想。十二世纪末末至十三世世纪初年间间，西班牙牙的神学家家和逻辑学学家RomenLuee试图制造能能解决各种种问题的通通用逻辑机机。十七世纪法法国物理学学家和数学学家B.Pascal制成了世界界上第一台台会演算的的机械加法法器并获得得实际应用用。随后德国数数学家和哲哲学家在这台加法法器的基础础上发展并并制成了进进行全部四四则运算的的计算器。。他还提出出了逻辑机机的设计思思想，即通通过符号体体系，对对对象的特征征进行推理理，这种““万能符号号”和“推推理计算””的思想是是现代化““思考”机机器的萌芽芽，因而他他曾被后人人誉为数理理逻辑的第第一个奠基基人。十九世纪英英国数学和和力学家C.Babbage致力于差分分机和分析析机的研究究，虽因条条件限制未未能完全实实现，但其其设计思想想不愧为当当时人工智智能最高成成就。1936年，年仅24岁的英国数数学家在他的一篇篇"理想计算机机"的论文中，，就提出了了著名的图图林机模型型，1945年他进一步步论述了电电子数字计计算机设计计思想，1950年他又在"计算机能思思维吗？"一文中提出出了机器能能够思维的的论述，可可以说这些些都是图灵灵为人工智智能所作的的杰出贡献献。2.形成成时期（1956-1961）1956年在美国的的Dartmouth大学的一次次历史性的的聚会被认认为是人工工智能学科科正式诞生生的标志，，从此在美美国开始形形成了以人人工智能为为研究目标标的几个研研究组：如如Newell和Simon的Carnegie-RAND协作组；Samuel和Gelernter的IBM公司工程课课题研究组组；Minsky和McCarthy的MIT研究组等1957年A.Newell、J.Shaw和H.Simon等人的心理理学小组编编制出一个个称为逻辑辑理论机LT(TheLogicTheoryMachine)的数学定理理证明程序序1956年Samuel研究的具有有自学习、、自组织、、自适应能能力的西洋洋跳棋程序序是IBM小组