人工智能第一次课

人工智能原理与实际

ArtificialIntelligence:PrinciplesandApplications杨丰yangf_2003@yahoo本课程的安排

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和H.A.Simon〔均为CMU教授〕等人参与夏季学术讨论班，历时两个月。这十位学者都是在数学、神经生理学、心思学、和计算机科学等领域中从事教学和研讨任务的学者，在会上他们第一次正式运用了人工智能〔AI〕这一术语，从而开创了人工智能的研讨方向。1.萌芽期〔1956年以前〕公元850年，古希腊就有制造机器人协助人们劳动的神话传说。在我国公元前900多年，也有歌舞机器人传说的记载，这阐明古代人就有人工智能的梦想。十二世纪末至十三世纪初年间，西班牙的神学家和逻辑学家RomenLuee试图制造能处理各种问题的通用逻辑机。十七世纪法国物理学家和数学家B.Pascal制成了世界上第一台会演算的机械加法器并获得实践运用。随后德国数学家和哲学家G.W.Leibniz在这台加法器的根底上开展并制成了进展全部四那么运算的计算器。他还提出了逻辑机的设计思想，即经过符号体系，对对象的特征进展推理，这种“万能符号〞和“推理计算〞的思想是现代化“思索〞机器的萌芽，因此他曾被后人誉为数理逻辑的第一个奠基人。十九世纪英国数学和力学家C.Babbage努力于差分机和分析机的研讨，虽因条件限制未能完全实现，但其设计思想不愧为当时人工智能最高成就。

1936年，年仅24岁的英国数学家A.M.Turing在他的一篇"理想计算机"的论文中，就提出了著名的图林机模型，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小组有影响的任务。1959年这个程序曾战胜设计者本人，1962年还击败了美国一个州的跳棋巨匠。

在MIT小组，1959年McCarthy发明的表〔符号〕处置言语LISP，成为人工智能程序设计的主要言语，至今仍被广泛采用。1958年McCarthy建立的行动方案咨询系统以及1960年Minsky的论文"走向人工智能的步骤"，对人工智能的开展都起了积极的作用。3.开展时期〔1961年以后〕六十年代以来，人工智能的研讨活动越来越遭到注重。为了提示