人工智能（全套课件）

人工智能2022/10/12人工智能2

第1章绪论1.1什么是人工智能1.2人工智能的研究内容1.3人工智能的研究目标1.4人工智能的研究途径和方法1.5人工智能的研究领域1.6人工智能的发展概况2022/10/121.1什么是人工智能人工智能技术成功的代表：1997年，IBM超级电脑“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫；2011年2月17日，在美国最受欢迎的智力竞猜电视节目《危险边缘》（Jeopardy）中，IBM超级电脑“沃森”（Watson）击败该节目历史上两位最成功的选手肯-詹宁斯和布拉德-鲁特.2022/10/12人工智能3人工智能（ArtificialIntelligence”，AI）2022/10/121.1什么是人工智能1.1.1人工智能1.1.2智能1.1.3人工智能的测试2022/10/122022/10/12人工智能51.1.1人工智能人工智能概念一般描述人工智能（ArtificialIntelligence），简称AI，又称机器智能（MachineIntelligence，MI），主要研究用人工的方法和技术开发智能机器或智能系统，以模仿、延伸和扩展人的智能、生物智能、自然智能，实现机器的智能行为。不同学者给出不同的定义2022/10/12

学者们从不同的角度、不同的层面给出了各自的定义:（1）人工智能是那些与人的思维相关的活动，诸如决策、问题求解和学习等的自动化（Bellman，1978）。（2）人工智能是研究怎样让电脑模拟人脑从事推理、规划、设计、思考、学习等思维活动，解决至今认为需要由专家才能处理的复杂问题（ElaineRich，1983）。（3）人工智能是研究如何让计算机做现阶段只有人才能做得好的事情（RichKnight，1991）。2022/10/12人工智能7（4）人工智能是那些使知觉、推理和行为成为可能的计算的研究（Winston,1992）。（5）广义地讲，人工智能是关于人造物的智能行为，而智能行为包括知觉、推理、学习、交流和在复杂环境中的行为（Nilsson，1998）。（6）StuartRussell和PeterNorvig（2003）则把已有的一些人工智能定义分为4类：像人一样思考的系统像人一样行动的系统理性地思考的系统理性地行动的系统2022/10/122022/10/12人工智能8

涂序彦教授概括了“广义人工智能GAI”的涵义：（1）“广义人工智能”是兼容多学派的“多学派人工智能”，模拟、延伸与扩展“人的智能”及其他动物智能，既研究“机器智能”，也研究“智能机器”。（2）“广义人工智能”是多层次结合的“多层次人工智能”；（3）“广义人工智能”不仅研究个体的、单机的、集中式的人工智能，而且研究群体的、网络的、多智能体、分布式人工智能。2022/10/122022/10/12人工智能91.从微观和宏观的角度认识智能微观角度人的智能产生于人的大脑，而人脑是一个由1011~1012个神经元连接形成的巨系统，结构和活动规律都极其复杂，智能产生仍然作为自然界四大奥秘之一(物质的本质，宇宙的起源，生命的本质，智能的产生)。宏观角度智能系统通常包括感知、记忆与思维、效应三大部分。甚至更狭义的理解认为：智能系统主要完成思维活动。1.1.2智能2022/10/122022/10/12人工智能102.从知识工程的角度认识智能知识和智能密不可分从内涵上智能=知识＋思维；从外延上智能就是发现规律、运用规律的能力和分析问题、解决问题的能力（或者说获取知识、处理知识、运用知识的能力）。2022/10/122022/10/12人工智能113.广义智能观

何华灿教授认为：“广义智能是信息系统感知环境及其变化，通过自身结构和功能的改变，恰当而有效地对其做出反映，以适应环境，达到系统生存目标的能力”；钟义信教授则认为：“广义智能是一切可以把信息转化为知识，把知识转化为智力的机制”。2022/10/12自然智能的全面概括（1）系统发育层面（2）个体发育层面（3）个体免疫层面（4）神经网络层面（5）抽象思维层面（6）群体协作层面（7）生态系统层面2022/10/122022/10/12人工智能13何华灿教授对存在于自然界中的自然智能的表现进行了较为全面的概括：（1）系统发育层面：在生物的系统发育过程中，存在一种自然智能——进化机制，它一般都能使生命不断适应生存环境的时空变化，最大限度地保存自己。如，生物通过遗传、变异、和选择等过程使物种得以生存下来等。（2）个体发育层面：生物个体发育过程中，存在一种自然智能——生长机制，它一般都能使一个生物个体适应生存环境进行生长发育，达到最佳的生存状态。如，植物的根系必须绕开石头向着有水肥的地方生长等。2022/10/122022/10/12人工智能14（3）个体免疫层面：在生物的免疫系统中，存在一种自然智能——免疫机制，它一般都能保证一个生物个体在存在大量有害微生物入侵的环境中平安地生存下去。如，种牛痘可以预防感染天花等。（4）神经网络层面：在动物的大脑存在一种自然智能——神经机制，它一般都能认识生存环境，对环境的变化做出恰当地反映，保证自身更好地生存下去。如，动物认识巢穴和伙伴联合捕捉猎物、巧妙地趋利避害等。2022/10/122022/10/12人工智能15（5）抽象思维层面：人类的抽象思维能力是一种自然智能——思维机制，它的基本功能是记忆、联想、问题求解、学习和发现等。思维机制的模拟导致了人工智能的诞生和早期发展，然而，经典数理逻辑无法解决现实中不良结构问题，是导致狭义人工智能出现理论危机的直接原因。（6）群体协作层面：在生物的群体行为中，存在一种自然智能——协作机制，它一般能保证生物群体的能力高于任何单一个体的能力，使整个群体能够更好地生存繁衍下去，如，蚁群、蜂群、猴群和人类社团等。（7）生态系统层面：在生态系统中，存在一种自然智能——平衡机制，它一般能保证整个生态系统相对于其生存环境处在一个最佳的平衡状态中。如，生物群落间的相互制约、相互依存关系，使生态系统处于相对平衡状态。2022/10/122022/10/12人工智能161.1.3人工智能的测试1.

图灵测试”（TuringTest）◆图灵测试的反向应用登录校验码2022/10/122022/10/12人工智能172.中文屋子2022/10/122022/10/12人工智能18人工智能的争论神学认为：“思维是人类不朽灵魂的一种机能，上帝把不朽的灵魂给了每个男人和女人，而没有给任何动物和机器。所以，任何动物和机器都不能有思维”；“把头埋在沙中”：“机器思维的后果太可怕了，我们希望并且相信机器做不到这点”。1950年10月，图灵发表了一篇题为《机器能思考吗？》的论文，成为划时代之作。在这篇论文里，图灵第一次提出“机器思维”的概念。2022/10/122022/10/12人工智能19人工智能的研究与进展几乎涉及并影响到自然科学和社会科学的所有学科，大体来看：社会科学的相关理论和方法为人工智能的研究提供方法论的指导；自然科学为人工智能的研究提供理论和技术的指导。

1.2人工智能的研究内容2022/10/121.2人工智能的研究内容1.2.1学科结构1.2.2基本技术1.2.3基本内容2022/10/122022/10/12人工智能211.2.1人工智能的学科结构2022/10/122022/10/12人工智能22（1）知识表示技术：研究各种知识的形式化方法，并要求所采用的形式化方法能够便于知识在计算机中进行存贮、组织，便于问题求解中的检索、推理等操作。（2）知识推理、计算和搜索技术：研究各种问题的求解规律，设计可机械执行的智能算子，用以实现问题求解过程。（3）系统实现技术：它研究如何实现相关知识的计算机内部表示，将各种智能算子或求解过程转换为程序，对智能应用系统，还要特别考虑人机交互及界面的实现。1.2.2人工智能的基本技术2022/10/122022/10/12人工智能23（1）从人工智能的定义出发，人工智能的基本内容可包括：感知与交流的模拟记忆、联想、计算、思维的模拟输出效应或行为模拟（2）从知识工程的角度出发，人工智能的基本内容是知识的获取知识的处理知识的运用1.2.3人工智能的基本内容2022/10/122022/10/12人工智能24近期目标

人工智能的近期目标是实现机器智能。即先部分地或某种程度地实现机器智能，从而使现有的计算机更灵活好用和更聪明有用。远期目标

人工智能的远期目标是要制造智能机器。具体讲就是使计算机具有看、听、说、写等感知和交互能力，具有联想、学习、推理、理解、学习等高级思维能力，还要有分析问题解决问题和发明创造的能力。1.3人工智能的研究目标2022/10/122022/10/12人工智能25

1.4.1传统划分方法

1.4.2现代划分方法1.4人工智能的研究途径和方法2022/10/122022/10/12人工智能261.4.1传统划分方法1.符号主义学派（Symbollisism）2.连接主义学派（Connectionism）3.行为主义学派（Actionnism）2022/10/121.符号智能学派（Symbollisism）符号主义学派也称心理学派、计算机学派、功能学派、逻辑学派、宏观结构学派。符号主义是以人脑的心理模型为依据，将问题或知识表示成某种符号，采用符号推演的方法，宏观上模拟人脑的推理、联想、学习、计算等功能，实现人工智能。早期代表人物有纽厄尔(AllenNewell)、肖（Shaw）、西蒙（HerbertSimon），后来还有费根宝姆(E.A.Feigenbaum)、Nilsson等。2022/10/12人工智能272022/10/122.连接主义学派（Connectionism）连接主义学派也称生理学派、仿生学派、微观结构学派。连接主义学派以人脑的生理模型为依据，通过对生物神经结构的模拟，实现学习、记忆、联想、计算和推理等功能，从而模拟人脑的智能行为。这种方法也称为神经计算。其代表人物有McCulloch，Pitts(MP模型)，F.Rosenblatt（感知器），T.Kohonen，J.Hopfield（全连接网络模型）等。2022/10/12人工智能282022/10/12

生物神经元的基本结构2022/10/123.行为主义学派（Actionnism）行为主义学派也称进化主义学派、控制论学派、实用技术学派。行为模拟是模拟人在控制过程中的智能活动和行为特性，如自适应，自寻优、自学习、自组织等，以此来研究和实现人工智能。是一种基于“感知-行为”或“激励-响应”模型的研究途径和方法，代表作是R.Brooks的六足行走机器人。其代表人物是MIT的R.Brooks教授。2022/10/12人工智能302022/10/122022/10/12人工智能311.4.2现代划分方法1.符号智能流派2.计算智能流派3.群体智能流派2022/10/121.符号智能流派由心理学派、认知学派、语言学派、计算机学派、逻辑学派、和数学学派等汇集而成。本流派的共同特征是对智能和人工智能持狭义的观点，侧重于研究任何利用计算机软件来模拟人的抽象思维过程，并把思维过程看成是一个抽象的符号处理过程。50多年来符号主义在人工智能中一直占有霸主地位。2022/10/12人工智能322022/10/122.计算智能流派是连接主义、行为主义、进化计算、免疫计算和模糊计算等学派的统称。它们与符号流派完全不同，计算机智能又重新回到依靠数值计算解决问题的轨道上来，它是对符号智能中符号推演的再次否定。连接主义学派的复兴大有夺取人工智能霸主地位之势。受大脑生理结构研究的限制，人工神经网络有一定的局限性。2022/10/12人工智能332022/10/123.群体智能流派由多智能体系统、生态平衡、细胞自动机、蚁群算法和微粒群算法等组成。它认同智能同样可以表现在群体的整体特性上，群体中每个个体的智能虽然很有限，但通过个体之间的分工协作和相互竞争，可以表现出很高的智能。这个流派形成晚，还很年轻，也最有发展前途，它用生态系统的观点看待智能，相信团结就是力量。2022/10/12人工智能342022/10/122022/10/12人工智能351.5.1博弈1.5.2自动定理证明1.5.3专家系统1.5.4模式识别1.5.5机器学习1.5.6计算智能1.5.7自然语言处理1.5.8分布式人工智能1.5.9机器人1.5人工智能的研究领域

2022/10/121.5.1博弈博弈（GamePlaying）可泛指单方、双方或多方依靠“智力”获取成功或击败对手获胜等活动过程。例如1956年塞缪尔的跳棋程序，1997年能够战胜世界国际象棋冠军卡斯帕罗夫的“深蓝”目前较为流行的对抗类游戏博弈问题的求解过程通常是一个启发式搜索过程。博弈中的很多概念、方法和成果对人工智能自身及其他领域提供了极具价值的参考和指导。2022/10/12人工智能362022/10/121.5.2

自动定理证明

自动定理证明的方法主要有：自然演绎法依据推理规则，从前提和公理中推出许多定理，若待证明的定理恰在其中，则定理得证。判定法对一类问题找出统一的计算机上可实现的算法解。定理证明器研究一切可判定问题的解法。1965年鲁滨逊提出的消解原理是这类工作的基础，计算机辅助证明以计算机为辅助工具，利用机器的高速和大容量，帮助人完成手工证明中无法完成的大量计算、推理和穷举。1956年，Newll、Shaw和Simon研制了逻辑理论机，证明了《数学原理》中的38条定理。2022/10/12人工智能372022/10/121.5.3专家系统专家系统（ExpertSystem）是一种智能计算机系统，在一定程度上辅助、模拟或代替人类专家解决某一领域内的问题，其水平可以达到甚至超过人类专家的水平。1965年费根鲍姆研究小组开始研制第一个专家系统——分析化合物分子结构的DENDRAL，标志着专家系统的正式诞生。专家系统的成功源于专门知识在智能模拟中的重要作用。专家系统是基于知识的智能问题求解系统。新型专家系统采用分布式处理，引入新的知识获取方法和新型的软件开发思想。2022/10/12人工智能382022/10/122022/10/12人工智能391.5.4模式识别模式识别（PatternRecognition）指的是用计算机进行物体识别。这里的物体一般指文字、符号、图形、图像、语音、声音及传感器信息等形式的实体对象，也就是说，这里所说的模式识别是狭义的模式识别，它是人和生物的感知能力在计算机上的模拟和扩展。模式识别的应用主要有：文字识别语音识别指纹识别遥感医学诊断2022/10/122022/10/12人工智能40

图像识别系统2022/10/121.5.5机器学习

机器学习（MachineLearning）研究：如何使机器通过经验来改善、提高其自身性能。具体地说，研究用计算机模拟或实现人类的学习能力，使其解决同一问题的水平不断提高。机器学习是人工智能的高级课题，同时也是众多相关研究领域的基础，它的应用涉及到博弈、数据挖掘、模式识别、自然语言处理等众多领域，主要使用归纳、统计、计算等方法。2022/10/12人工智能412022/10/121.5.6计算智能

计算智能（ComputationalIntelligence）也称自然智能（或自然计算）：是基于“从大自然中获取智慧”的理念、受到大自然智慧和人类智慧的启发而设计出来的一类算法的统称。或模仿生物界的进化过程（遗传算法）或模仿生物的生理构造和身体机能（免疫算法）或模仿动物的群体行为（粒群算法）或模仿人类的思维、语言和记忆过程的特性（神经网络）或模仿自然界的物理现象（模拟退火算法）

实现对实际问题的优化求解，在可接受的时间内求出可以接受的解。2022/10/12人工智能422022/10/121.5.7自然语言处理

自然语言处理（NLP）：包含自然语言理解及自然语言生成。自然语言系统不是一个形式语言系统因此对自然语言理解，和自然语言生成，其实现都是十分困难的。在英语句子“Thespiritiswillingbutthefleshisweak”翻译成俄语，然后再翻译回来时竟变成了“酒是好的，肉变质了”，即“Thewineisgoodbutthemeatisspoiled”。自然语言理解的困难：这世上男人没有了女人就没法活。（不可解决的句法结构歧义）http:///2022/10/12人工智能432022/10/121.5.8分布式人工智能分布式人工智能（DAI）系统具有分布性、连接性、协作性、开放性、容错性等特点。DAI大约可划分为三个基本类型：多Agent系统（MAS）；分布式问题求解（DPS）；并行人工智能（PAI）。MAS也可看做是分布式人工智能系统。2022/10/12人工智能442022/10/121.5.9机器人（Robot）机器人定义：“一种可编程和多功能的的操作机；或是为了执行不同的任务而具有可用电脑改变和可编程动作的专门系统。”——美国机器人协会按照其智能程度来划分，大致可分为：操作型程控型示教再现型数控型感觉控制型适应控制型学习控制型智能型2022/10/12人工智能452022/10/122022/10/122022/10/122022/10/122022/10/12人工智能492022/10/122022/10/12人工智能501.6.1诞生1.6.2发展1.6.3现状与发展趋势1.6人工智能的发展概况2022/10/121.6.1诞生人工智能经历了漫长的孕育期具备思想基础、理论基础、物质技术基础1956年夏季，十位来自数学、心理学、神经生理学、信息论和计算机方面的专家在美国达特莫斯大学召开一次历时两个月的研究会，讨论了关于机器智能的有关问题，会上麦卡锡提议正式采用了“人工智能”一词，标志人工智能学科的正式诞生，基于此，麦卡锡也被称为“人工智能之父”。2022/10/12人工智能512022/10/12十位学者达特莫斯大学的麦卡锡（JohnMcCarthy）哈佛大学的明斯基（MarvinMinsky

）IBM公司的罗切斯特（MathanielRochester）贝尔实验室的香农（ClaudeShannon）IBM公司的莫尔（T.More）和赛缪而（AllenSamuel）MIT的塞尔弗里奇（O.Selfridge）和索门罗夫（R.Solomonff）卡内基工科大学的纽厄尔（A.Newell）和西蒙（H.A.Simon）2022/10/12数理逻辑发展历程（1/2）逻辑学的创始人、古希腊的哲学家亚里斯多得（Aristotle）是研究人类思维规律的鼻祖。12世纪末13世纪初的西班牙神学家和逻辑学家罗门·卢乐（Romen

Luee）最早提出了制造可以解决各种问题的通用逻辑机。17世纪法国的物理学家和数学家帕斯卡（B.Pascal，1623－1662）制成了世界上第一台机械式加法器。2022/10/12数理逻辑发展历程（2/2）德国数学家和哲学家莱布尼兹（G.W.Leibniz，1646－1716）制成了可进行四则运算的计算器。他还提出了“万能符号”和“推理计算”的思想。莱布尼兹被后人尊为数理逻辑的第一奠基人。19世纪英国的数学家布尔（G.Boole,1815-1864）在《思维法则》一书中，第一次用符号语言描述了思维活动中的推理的基本法则，创立了逻辑代数。在近代，研究思维机器的最高成就属于英国的数学家巴贝奇（1791－1871），他毕生致力于差分机和分析机的研究，分析机的设计思想与现代电子数字计算机十分相似，但由于种种限制而未能成功。2022/10/12自动机理论英国的数学家图灵（A.M.Turing,1912－1954）提出了理想计算机模型（即图灵机），创立了自动机理论。把思维机器的研究和计算机的理论研究向前推进了一步。图灵在1950年发表了题为“计算机与智能”的论文，提出了著名的图灵测试。2022/10/12控制论、信息论和系统论控制论1948年美国数学家维纳（N.Wiener）创立了控制论。信息论美国数学家香农（C.E.Shannon）创立了信息论。系统论美籍奥地利生物学家贝塔郎菲创立了系统论。2022/10/121.6.2发展推理期：人工智能的研究主要是以推理为中心知识期：费根鲍姆提出了“知识工程”的概念，使人们更加清楚的认识到，问题的智能求解过程就是一个知识处理过程。学习期：随着人工智能的进一步发展，人们越来越多地发现，没有学习功能的系统其解决问题的能力十分有限。机器学习是继专家系统之后人工智能的又一个令人瞩目的研究领域。2022/10/12人工智能572022/10/121.6.3现状与发展趋势进入20世纪90年代人工智能进入蓬勃发展的时期。计算智能是信息科学和生命科学相互交叉和渗透的产物，对自然界中存在的计算规律的模仿和借鉴，为人工智能的研究开辟了广阔的前景。21世纪，计算智能迅速发展的同时，值得一提的还有分布式人工智能技术。2022/10/12人工智能582022/10/12思考并讨论什么是智能？人类智能主要包括哪些方面？通过本章的学习，谈谈你对人工智能的认识，并结合实际，谈一谈人工智能的应用。人工智能的诞生、发展过程是怎样的？设想一下人工智能的未来会是怎样的，你认为未来人工智能会超过人类智能吗？2022/10/12第2章基于图的知识表示与图搜索技术2022/10/12人工智能61第2章基于图的知识表示与图搜索技术2.1概述2.2状态空间图表示2.3状态空间图的盲目搜索2.4状态空间图的启发式搜索2.5与或图表示及搜索技术2.6博弈树及搜索技术2022/10/122022/10/12人工智能622.1概述2.1.1知识与问题求解框架2.1.2知识表示2.1.3图搜索技术2022/10/122022/10/12人工智能632.1.1知识与问题求解框架(1)1.知识的定义心理学：个体通过与环境相互作用后获得的信息及其组织。费根鲍姆：知识是经过消减、塑造、解释和转换的信息。博恩斯坦（Bernstein）：知识是由特定领域的描述、关系和过程组成的。

概括地说，知识是高度组织起来的信息集团，是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。2022/10/122.1.1知识与问题求解框架(2)2.知识的分类（1）从应用领域来划分常识性知识领域（专业）性知识（2）从在问题求解中的作用来划分叙述性知识过程性知识控制性知识（3）从确定性来划分确定性知识非确定性知识（4）从知识的表现形式来划分，可分为文字、符号、声音、图形、图像等。2022/10/12人工智能642022/10/122.1.1知识与问题求解框架(3)3.问题求解框架问题：是指事件或事物的已知或当前状态与目标状态之间有差异。问题求解：是指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一致。例如，李明在北京，他要去西安（办事）。又如，博弈问题。问题的求解框架（1）叙述性知识：描述问题的状态有关的各种知识。（2）过程性知识：描述状态之间的变换关系的各种知识。（3）控制性知识：描述如何在当前状态下选择合适操作的知识。2022/10/12人工智能652022/10/122022/10/12人工智能662.1.2知识表示(1)知识表示：就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络……2022/10/122.1.2知识表示(2)2022/10/12人工智能67例2.1麦卡赛问题。在一个2n2n的方格棋盘中，去掉对角的两个方格，如图（a），问能否将它全部划成若干12的小长方块？目标状态初始状态可达状态同构问题同态问题2022/10/122022/10/12人工智能682.1.3图搜索技术(1)1.搜索

搜索，简单地说就是“寻找”，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。2.搜索树

搜索过程中经过（考察过）的节点和边，按原图的连接关系，便会构成一个树型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。2022/10/122.1.3图搜索技术(2)2022/10/12人工智能69图2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图：2022/10/122.1.3图搜索技术(3)3.搜索策略搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。盲目搜索：无向导的搜索，也称穷举搜索。启发式搜索：利用“启发性信息”作为导航的搜索过程。对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。2022/10/12人工智能702022/10/122022/10/12人工智能712.2状态空间图表示2.2.1状态空间图2.2.2隐式状态空间图2022/10/122022/10/12人工智能722.2.1状态空间图（1）1.状态

状态对应叙述性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量

，表示与问题状态相关的各种要素，并用这组变量所构成的多元组

来表示状态。状态在状态图中表示为节点。2022/10/122022/10/12人工智能732.2.1状态空间图（2）2.操作

操作对应过程性知识，即状态转换规则，描述状态之间的关系。描述一个操作要包含两个部分条件:指明被作用的状态要满足的约束条件动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。如：如果室内温度低于26度，则关闭空调。2022/10/122022/10/12人工智能742.2.1状态空间图（3）3.状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图，如考虑操作的代价，状态空间图就是一个赋值有向图。状态空间常记为三元组：

S：初始状态的集合

F：操作的集合

G：目标状态的集合。由问题的状态空间表示就可以构造出状态空间图。2022/10/122.2.1状态空间图（4）4.求解在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组<Qs,a,Qg>Qs

：某个初始状态Qg

：某个目标状态a：把Qs变换成Qg的有限的操作序列状态转换图S1S3S2…f1f2f3f4QsQgfn2022/10/12人工智能752022/10/122022/10/12人工智能76例2.2翻转钱币问题（1）三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。初始状态Qs目标状态集合{Q0,Q7}2022/10/12例2.2翻转钱币问题（2）引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面为1，全部可能的状态为：

Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子，即F＝{a,b,c}a:把钱币q0翻转一次

b:把钱币q1翻转一次

c:把钱币q2翻转一次问题的状态空间为<{Q5},{a,b,c}，{Q0Q7}>2022/10/12人工智能772022/10/12例2.2翻转钱币问题（4）3.状态空间图问题的状态空间为：

2022/10/12人工智能78构造状态空间图：

aabababaabbbbcccbcccb2022/10/12例2.2翻转钱币问题（5）2022/10/12人工智能79图2-5翻动三次后三枚钱币问题的状态变化翻转钱币问题状态空间图的另一种表示：2022/10/122022/10/12人工智能80例2.3修道士和野人问题（1）

在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运两个人；（2）在任何岸边野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。2022/10/122022/10/12人工智能81例2.3修道士和野人问题（2）1、问题的状态可以用一个三元数组来描述：

S＝(m,c,b)

m：左岸的修道士数

c：左岸的野人数

b：左岸的船数右岸的状态不必标出，因为：

右岸的修道士数m’＝3－m

右岸的野人数c’＝3－c

右岸的船数b’＝1－b2022/10/122022/10/12人工智能82例2.3修道士和野人问题（3）状态m,c,b状态m,c,b状态m,c,b状态m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28

030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S310002022/10/122022/10/12人工智能83例2.3修道士和野人问题（4）2.操作集F＝{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=1,m=m+1,c=c+1q10b=0,(m=0,c=1)或(m=2,c=2)b=1,m=m+1q01b=0,m=0或3,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=0,m=m-1,c=c-1p10b=1,(m=3,c=2)或(m=1,c=1)b=0,m=m-1p01b=1,m=0或3,c≥1b=0,c=c-1操作符条件动作2022/10/12例2.3修道士和野人问题（5）3.状态空间给出状态和操作的描述之后，该问题的状态空间是：{{S0}，{P

01，P

10，P

11，P

02，P

20，Q01，Q

10，Q

11，Q

02，Q

20}，{S31}}。2022/10/122022/10/12人工智能85例2.3修道士和野人问题（6）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S0(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0)p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.状态空间图：四条S0到S31长度相等的最短路径，对应的操作序列就是该问题的四个最优解2022/10/122022/10/12人工智能862.2.2隐式状态空间图显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显示表示。隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表示或隐式图。2022/10/12重排九宫问题的隐式图描述为：（1）有关状态的知识：状态S的定义：S＝(X0，X1，X2，X3，X4

，X5，

X6

，X7，X8)

其中，Xi｛0，1，2，3，4，5，6，7，8｝，，且。初始状态：S0

＝（0，1，2，3，5，6，4，7，8）

目标状态：

Sg

＝（0，1，2，3，4，5，6，7，8）重排九宫问题的状态表示例2.4重排九宫问题（八数码问题）

2022/10/12例2.4重排九宫问题（2）（2）有关操作的知识（规则）：0组规则

R1(X0=0

)(X2=n

)X0=nX2=0；

R2(X0=0

)(X4=n

)X0=nX4=0；

R3(X0=0

)(X6=n

)X0=nX6=0；

R4(X0=0

)(X8=n

)X0=nX8=0；1组规则

R5(X1=0

)(X2=n

)X1=nX2=0；

R6(X1=0

)(X8=n

)X1=nX8=0；8组规则:

R22(X8=0

)(X1=n

)X8=nX1=0；

R23(X8=0

)(X0=n

)X8=nX0=0；

R24(X8=0

)(X7=n

)X8=nX7=0；……2022/10/12例2.4重排九宫问题（3）八数码的状态图可表示为（{S0},{r1,r2,…,r24},{Sg}）八数码问题状态图仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。2022/10/12例2.4重排九宫问题（4）（3）隐式图搜索初始状态S＝（0，1，2，3，5，6，4，7，8）满足条件X0=0，故可以使用第0组的四条规则：如果选择规则R1，则状态转换为：S1＝（2，1，0，3，5，6，4，7，8)2022/10/122022/10/12人工智能91例2.5旅行商问题(TSP)(1)设有n个互相可直达的城市，某推销商准备从其中的A城出发，周游各城市一遍，最后又回到A城。要求为该推销商规划一条最短的旅行路线。（1）状态描述：该问题的状态为以A打头城市序列：

=AA1…Ai…

Aj…A’其中：A、Ai、Aj、A’为城市名，

1i、jn-1，AjA，AiA；

1||n+1；当i

j时，Ai

Aj；当且仅当||=n+1时，A’=A。初始状态：=A，||=1终止状态：=AA1A2…A，||=n+12022/10/12例2.5旅行商问题(TSP)(2)（2）操作描述（状态转换规则）：规则1

：如果=AA1…Ai…

Aj…，且||

n，但A’，则置=A。即没遍历完时，在城市序列中添加一个没有到过的城市。规则2

：如果||=n，置=

A，即从当前城市返回A城。

（3）隐式图搜索对于有A、B、C、D四个城市所组成的连通城市网，初始状态：=A，||=1，满足规则1，则操作的结果为：=AB、或=AC、或=AD，继续使用规则1

，直到生成包含四个城市的序列出现，再使用规则2。2022/10/12人工智能922022/10/12补充例

二阶梵塔问题（1）

一号杆有A、B两个金盘，A小于B。要求将A、B移至三号杆，每次只可移动一个盘子，任何时刻B不能在A上。（1）有关状态的知识：用二元组（SA，SB）表示状态，SA表示A所在杆号，SB表示B所在杆号。其中:SA

,SB{1,2,3}

,

则全部状态如下：

（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）初始状态为（1，1），终止状态为：（3，3）。2022/10/12人工智能932022/10/12AB123S0：（1，1）123S1：（1，2）123S2：（1，3）AA123S5：（2，3）123S4：（2，2）123S3：（2，1）123S8：（3，3）123S7：（3，2）123S6：（3，1）AAAAABABBBBB补充例

二阶梵塔问题（2）2022/10/12人工智能942022/10/12（2）有关操作的知识（规则）：A（i，j）表示金盘A从第I号杆移到j号杆，B（i，j）表示金盘B从第i号杆移到j号杆，其中：i,j

{1,2,3}，但ij，全部操作为：

A（1，2），A（1，3），A（2，1）

A（2，3），A（3，1），A（3，2）

B（1，2），B（1，3），B（2，1）

B（2，3），B（3，1），B（3，2）分析每个操作的条件和动作，得到下表：补充例

二阶梵塔问题（3）2022/10/12人工智能952022/10/12补充例

二阶梵塔问题（4）操作符条件动作A（1，2）SA=1SA=2A（1，3）SA=1SA=3A（2，1）SA=2SA=1A（2，3）SA=2SA=3A（3，1）SA=3SA=1A（3，2）SA=3SA=2B（1，2）SB=1，SA1,2或SA=3SB=2B（1，3）SB=1，SA1,3或SA=2SB=3B（2，1）SB=2，SA1,2或SA=3SB=1B（2，3）SB=2，SA2,3或SA=1SB=3B（3，1）SB=3，SA1,3或SA=2SB=1B（3，2）SB=3，SA2,3或SA=1SB=22022/10/12人工智能962022/10/12补充例

二阶梵塔问题（5）（3）状态空间图1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2022/10/12人工智能972022/10/122.3状态空间图的盲目搜索盲目搜索:搜索时不参考与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，具有通用性。算法中使用的数据结构:OPEN表：专门登记已经生成但还没有考察的节点，即待考察节点。CLOSED表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。CLOSED表中存放的就是一定搜索策略下的搜索树。2022/10/12人工智能98节点父节点编号编号节点父节点编号OPEN表CLOSED表2022/10/122022/10/12人工智能992.3状态空间图的盲目搜索2.3.1广度优先搜索2.3.2深度优先搜索2022/10/122022/10/12人工智能1002.3.1广度优先搜索（1）广度优先搜索（A٭ed）基本思想：广度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将OPEN表设计为一个队列来实现，将新生成的子节点放在OPEN表的后面，保证先生成的节点先考察。广度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3否则，取OPEN表中第一个节点N放在CLOSED表中；并冠以顺序编号n；步4若节点N为目标节点，则搜索成功。利用CLOSED表中的返回指针找出S0到N的路径即为所求解，退出；步5若N不可扩展，转步2；步6否则，扩展N，将其所有子节点配上指向N的返回指针放入OPEN表的尾部，转步2。2022/10/122.3.1广度优先搜索（2）2022/10/122022/10/12人工智能102例2.6使用广度优先搜索算法求解重排九宫问题1238574611238567481382574610123845767123845766138257461112384576212385746313825746412378546122318574613123847651412345876151285374617135827461881325746191237854620231857462112843765221238574651238476523八数码广度优先搜索12853746916123856742022/10/122022/10/12人工智能1032.3.1广度优先搜索广度优先搜索的特点：广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。广度优先搜索又称为宽度优先或横向搜索。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低。2022/10/122022/10/12人工智能1042.3.2深度优先搜索(1)深度优先搜索的基本思想：

深度优先搜索是一种一直向下的搜索过程，它优先在自己的子节点集合中选择下一个被考察的节点，不断向纵深方向前进，直到到达叶子节点或受到深度限制时，才返回到上一级节点沿另一方向继续前进。深度优先搜索算法：

与广度优先搜索策略的唯一不同点就是OPEN表被设计成后进先出的栈，新生成的子节点放在OPEN表的前面，后生成的节点优先被考察。深度优先搜索算法只需将宽度优先搜索算法步6修改为：步6否则，扩展N，将其所有子节点配上指向N的指针放入OPEN表的首部，转步2。2022/10/12例2.7使用深度优先搜索算法求解重排九宫问题

12385746112384576312384576

123845761382574612385746123847654128437651238574621238476552022/10/122022/10/12人工智能1062.3.2深度优先搜索深度优先搜索的特点：OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。如下图所示：图2-13深度优先搜索不具有完备性示意图2022/10/122022/10/12人工智能1071.有界深度优先搜索（Acd

）为克服深度优先搜索的不足，可以对其深度进行限制深度界限的选择很重要

dm

若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。2022/10/122.可变界深度优先搜索算法(1)当在dm界限之内找不到解时，可以将深度界限dm不断扩大，每次增加一个深度增量d，直到找到解，或者搜索完整棵树。这样算法的完备性得到了保证，称为可变界深度优先搜索算法(或迭代加深搜索)。当⊿d

=1时，算法开始蜕变为广度优先搜索算法。

2022/10/122.可变界深度优先搜索算法(2)迭代加深搜索过程：步1

把初始节点S0放入OPEN表中，置S0的深度d（S0

）＝0，dm为任意初值。步2

若OPEN表为空，则考查CLOSED表是否有待扩展节点：

①若无，则问题无解，退出。②若有，则取出CLOSED表中待扩展节点放入到OPEN表中，令dm=dm+⊿d。

2022/10/122.可变界深度优先搜索算法(3)

步3

取OPEN表中第一个节点N放在CLOSED表中；并冠以编号n；步4

若节点N为目标节点，成功退出。步5

若N的深度d（N）＞dm（深度限制值），则标N为待扩展节点，则转步2；

步6N无子节点，则转步2；步7

扩展N，将其所有子节点Ni配上指向N的指针放入OPEN首部，置d（Ni

）＝d（N）＋1，转步2。2022/10/123.可采纳的有界深度优先搜索算法(1)问题：当⊿d

>1时，是否能保证找到最优解？2022/10/122022/10/12人工智能1133.可采纳的有界深度优先搜索算法(2)步1把初始节点S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2若OPEN表为空，则考察CLOSED表是否有待扩展节点：（1）若无待扩展节点，则判断G表是否为空：若为空，搜索失败，退出；否则，取出G表最后面的节点Sg，Sg即为所求最优解，搜索成功，退出；（2）若有待扩展节点，则取出CLOSED表中待扩展节点放入到OPEN表中，令dm=dm+⊿d，转步2；2022/10/123.可采纳的有界深度优先搜索算法(3)步3取OPEN表中首部的节点N放在CLOSED表中；并冠以顺序编号n；步4若d（N）＞dm，则标N为待扩展节点，转步2；步5若N是目标节点Sg

，则令dm＝d（Sg

）-1，把Sg放到G

表的尾部，转步2。步6若N不可扩展，则转步2；步7否则，扩展N，将其所有子节点Ni配上指向N的返回指针放入OPEN表首部，置d（Ni

）＝d（N）＋1，转步2。

2022/10/12人工智能1142022/10/122.4状态空间图的启发式搜索(1)1.启发性知识与启发函数启发性知识就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。启发函数要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以指导搜索过程，这样的函数称为启发函数。2022/10/12人工智能1152022/10/122022/10/12人工智能1162.4状态空间图的启发式搜索(2)2.启发函数的设计在实际设计过程中，启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数，通常记为h（x）。启发函数可以是：（1）一个节点到目标节点的某种距离或差异的量度；（2）一个节点处在最佳路径上的概率；（3）根据主观经验的主观打分等。2022/10/122022/10/12人工智能1172.4状态空间图的启发式搜索(3)2.4.1启发式搜索算法2.4.2启发式搜索的A算法和A*算法2.4.3

A*算法在游戏中的应用2022/10/122022/10/12人工智能1182.4.1启发式搜索算法（1）启发式搜索用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。按选择范围不同，启发式搜索分为：全局择优搜索局部择优搜索2022/10/122022/10/12人工智能1192.4.1启发式搜索算法（2）1.全局择优搜索基本思想：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。2022/10/122.4.1启发式搜索算法（3）全局择优搜索算法：步1把初始节点S0放入OPEN表中，计算h(S0)；步2若OPEN表为空，则搜索失败，退出；步3否则，移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4若目标节点Sg

＝N，则搜索成功，利用CLOSED表中的返回指针找出S0到N的路径即为所求解，退出；步5若N不可扩展，则转步2；步6否则，扩展N，计算N的每个子节点x的函数值，并将N所有子节点x配以指向N的返回指针后放入OPEN表中，依据启发函数对节点的计算，再对OPEN表中所有节点按其启发函数值的大小以升序排列，转步2。2022/10/12人工智能1202022/10/122.4.1启发式搜索算法（4）2.局部择优搜索基本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成而未考察的节点，对其中新生成的每个子节点x计算启发函数，从全部子节点中选出最优节点进行扩展，其选择下一个要考察节点的范围是刚刚生成的全部子节点，局部择优搜索算法：与全局择优搜索算法的区别仅在步6：步6否则，扩展N，计算N的每个子节点x的函数值，并将N的所有子节点x配以指向节点N的指针后，将全部子节点按启发函数值升序排列后放入OPEN表的首部，转步2。2022/10/12人工智能1212022/10/122.4.2启发式搜索的A算法和A*算法（1）启发函数是对当前节点到达目标节点未来可能要付出的代价的估计。在全局择优和局部择优搜索算法中，都没有考虑从初始节点到当前节点已经付出的实际代价。在很多实际问题中，已经付出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法称为A算法和A*算法。2022/10/122022/10/12人工智能1232.4.2

启发式搜索的A算法和A*算法（2）1.A算法估价函数f（x）

:为了防止在单独利用启发函数的时候误入歧途，将启发函数h（x）与代价函数g（x）相结合，即初始节点S0到达节点x处已付出的代价与节点x

到达目标节点Sg的接近程度估计值总和。

f（x）＝g（x）＋h（x）

g（x）代价函数：初始节点S0到达节点x处已付出的代价，有利于搜索纵向发展，提高搜索效率，但影响完备性。

h（x）启发函数：节点x

到达目标节点Sg的接近程度估计值有利于搜索横向发展，提高搜索的完备性，但影响搜索效率。2022/10/122.4.2

启发式搜索的A算法和A*算法（3）代价g（x）的计算

g（x）表示从初始节点S0到节点x的代价：

g（S0）＝0

g（xj

）＝g（xi

）＋c（xi，xj）

其中，c（xi，xj）表示父节点xi到子节点xj的代价ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32022/10/12人工智能1242022/10/122.4.2

启发式搜索的A算法和A*算法（4）对估价函数

f（x）＝g（x）＋h（x）

令其中的h（x）=0