人工智能中的搜索问题1课件

SearchingProblemsinAI人工智能中的搜索问题智能体的初始状态是确定的智能体当前状态是否为目标状态是可以检测的智能体的状态空间是离散的智能体在每个状态可以采取的合法行动和相应后继状态是确定的环境是静态的路径的耗散函数是已知的什么是搜索问题搜索问题：已知智能体的初始状态和目标状态，求解一个行动序列使得智能体能从初始状态转移到目标状态。如果所求序列可以使得总耗散最低，则问题称为最优搜索问题。几个典型的搜索问题起始状态：Arad路径规划问题目标状态：Bucharest合法行动与后继的确定性：与某一城市相邻的城市才能成为合法后继状态空间的离散性：城市是离散的环境的静态性：城市的相对位置不会改变路径的耗散函数的确定性：城市之间的距离是已知的搜索问题：从Arad到Bucharest的路径最优化搜索问题：从Arad到Bucharest的最短路径几个典型的搜索问题起始状态8-Puzzle问题目标状态合法行动与后继的确定性：只有空格四周的格子是可以移动的状态空间的离散性：8个格子的排列方式是离散的环境的静态性：九宫格的大小和形状在格子移动过程中不会改变路径的耗散函数的确定性：相邻两个状态之间所需步骤为1搜索问题：从起始状态到目标状态的移动方法最优化搜索问题：从起始状态到目标状态步骤最少的移动方法华容道是不是一个搜索问题？几个典型的搜索问题八皇后问题合法行动与后继的确定性：满足棋盘上所有皇后不能互相攻击的后继才是合法的状态空间的离散性：0-8个皇后在棋盘上的摆放方式环境的静态性：棋盘的格局和大小不会改变路径的耗散函数的确定性：相邻两个状态之间所需步骤为1搜索问题：求出（所有）合法的目标状态起始状态：空的棋盘目标状态：棋盘上摆了八个皇后，并且任意两个皇后都不能互相攻击。目标状态不确定，但是当前状态是否为目标状态是可以检测的。搜索问题的组成初始状态：智能体所处的初始状态后继函数：输入给定状态，可以输出合法行动和相应的后继状态目标测试：用来确定给定的状态是否为目标状态路径耗散函数：在两个给定状态之间进行转移所需的“代价”普通搜索问题：求出一条从初始状态到目标状态之间的行动序列全局搜索问题：求出所有从初始状态到目标状态之间的行动序列最优化搜索问题：求出从初始状态到目标状态之间耗散最少的行动序列搜索问题的求解所有搜索过程都可以用搜索树算法来进行表示搜索树搜索问题的求解搜索树实例搜索问题的求解搜索树实例搜索问题的求解搜索树实例搜索问题的求解节点与状态的区别节点（Node）是一种数据结构，每个节点的信息包括当前状态、父节点、子节点、深度和路径耗散状态（State）只是一种系统可能存在的形式不同节点包含的状态可能是相同的搜索问题的求解完备性：当问题有解时，这个算法是否保证能找到一个解？最优性：这个搜索策略是否能找到最优解？时间复杂度：找一个解需要花费多长时间？空间复杂度：在执行搜索过程中需要多少内存？普通搜索问题：求出一条从初始状态到目标状态之间的行动序列全局搜索问题：求出所有从初始状态到目标状态之间的行动序列最优化搜索问题：求出从初始状态到目标状态之间耗散最少的行动序列搜索策略的性能搜索问题的求解无信息的搜索策略：无法知道当前状态离目标状态的“远近”或者不利用类似的先验信息来进行搜索的策略广度优先搜索（BFS，Breadth-firstsearch）代价一致搜索（UCS，Uniform-costsearch）深度优先搜索（DFS，Depth-firstsearch）深度有限搜索（Depth-limitedsearch）迭代深入搜索（Iterativedeepeningsearch）有信息的（启发式）搜索策略：利用启发式信息来进行搜索的策略贪婪最佳优先搜索（Greedybestfirstsearch）A*搜索（A*search）搜索策略的分类不同搜索策略的区别仅在于扩展节点的顺序无信息的搜索策略广度优先搜索先被访问的节点先进行扩展每次扩展深度最浅的节点可以用一个先进先出的数据结构来保存待扩展节点序列CBDECFGDEDGEFCDEDEFG无信息的搜索策略代价一致搜索累积路径耗散最小的节点先被扩展倘若每一步的耗散都为正，则保证可以得到最优解若单步耗散相等，该算法和广度优先搜索一样CBDE？？？CDE？为累积路径耗散最小的节点无信息的搜索策略深度优先搜索后被访问的节点先进行扩展每次扩展深度最深的节点“一条路走到黑”，对于无边界搜索问题无法保证完备性可以用一个后进先出的数据结构来保存待扩展节点序列无信息的搜索策略深度优先搜索CBEDDIHCECEDCEIH无信息的搜索策略深度优先搜索CHICECEICEIHEICE无信息的搜索策略深度有限搜索深度优先搜索它可能错误地选择一条分支并且沿着一条很长的（甚至是无限的）路径一直走下去对于无边界的搜索问题，可以通过对深度优先搜索提供一个预先设定的深度限制m来防止深度优先搜索进入死循环如果目标深度d>深度限制m，深度有限搜索可能无法得到解，因此完备性也无法保证无信息的搜索策略迭代深入搜索用来寻找最合适的深度限制的通用策略，经常和深度优先搜索结合使用不断增大深度限制，直到找到目标节点结合了深度有限搜索的优点，又保证了完备性，还能保证得到最优解无信息的搜索策略迭代深入搜索无信息的搜索策略策略之间的比较为了避免含有相同状态的节点被重复扩展，可以用一个数据结构来记录所有被访问过的节点。如果当前待扩展节点与某个已访问过的节点对应的状态相同的话，则当前节点将不会被扩展。这时树搜索（TreeSearch）策略将成为图（GraphSearch）策略启发式搜索策略最佳搜索策略最佳优先搜索的通用思想：用一个评价函数f(n)来对节点进行评价。在扩展节点的过程中，从候选节点中选择f(n)最小的节点来进行扩展。对于BFS，f(n)表示节点深度；对于UCS，f(n)表示节点的累计路径耗散；对于DFS，f(n)表示节点深度的负值很多时候f(n)不能真正度量节点的好坏，因此可以考虑引进启发式信息来估计节点离目标状态的距离启发式函数：h(n)=从节点n到目标节点的最低耗散路径的耗散估计值启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n)在这个路径规划问题中，h(n)取为当前城市离目标Bucharest的直线距离启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n)启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n)启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n)启发式搜索策略贪婪最佳优先搜索与深度优先搜索一样，它更倾向于沿着一条路径搜索下去直到目标因为在扩展节点时没有考虑累计路径耗散，因此它也不能保证得到最优解如果状态空间是无限的，它也可能是不完备的启发式搜索策略A*搜索为了弥补贪婪最佳优先搜索无法找到最优解的缺点，考虑在评价函数里加入累计路径耗散，由此形成A*搜索算法评价函数f(n)=g(n)+h(n)g(n)：从起始节点到节点n的路径耗散h(n)：从节点n到目标节点的最低耗散路径的耗散估计值f(n)：经过节点n到目标节点的总耗散估计值启发式搜索策略A*搜索启发式搜索策略A*搜索启发式搜索策略A*搜索启发式搜索策略A*搜索启发式搜索策略A*搜索启发式搜索策略如果h(n)是可采纳的（admissible），即h(n)从不过高估计节点n到目标节点的最低耗散，则基于A*搜索策略的树搜索方法（不检查重复节点）是最优的如果h(n)是一致的（consistent），则基于A*搜索策略的图搜索方法（检查重复节点）是最优的A*搜索Thanks人工智能

是一门交叉学科

脑科学认知科学心理学语言学逻辑学哲学计算机科学人工智能什么是人工智能人工智能的定义可以分为两部分，即“人工”和“智能”。关于什么是“智能”？智能需要具备的特征？具有感知能力（系统输入）:

机器视觉，机器听觉，图像语音识别……具有记忆与思维能力：思维是智能的根本原因，思维是一个动态的过程。思维分为：逻辑思维，形象思维和顿悟思维。具有学习能力及自适应能力：适应环境的变换、积累经验的能力

具有行为能力（系统输出）：对外界的智能化反应早期判断是否有智能的方法———图灵测试英国数学家阿兰·图灵(AlanTuring)提出了现称为“图灵测试”(TuringTest)的方法。简单来讲,图灵测试的做法是:让一位测试者分别与一台计算机和一个人进行交谈(当时是用电传打字机),而测试者事先并不知道哪一个是人,哪一个是计算机。如果交谈后测试者分不出哪一个被测者是人,

哪一个是计算机,则可以认为这台被测的计算机具有智能。

Turing测试存在的问题“图灵测试”没有规定问题的范围和提问的标准仅反映了结果的比较，无涉及思维过程没指出是什么人争论：通过了图灵检验的电脑就具备思维能力了么？测试主持人被测机器被测人中文屋子约翰·西尔勒的中文屋子假设是说:有一台计算机阅读了一段故事并且能正确回答相关问题,这样这台计算就通过了图灵测试。而西尔勒设想将这段故事和问题改用中文描述(因为他本人不懂中文),然后将自己封闭在一个屋子里,代替计算机阅读这段故事并且回答相关问题。描述这段故事和问题的一连串中文符号只能通过一个很小的缝隙被送到屋子里。西尔勒则完全按照原先计算机程序的处理方式和过程(如符号匹配、查找、照抄等)对这些符号串进行操作,然后把得到的结果即问题答案通过小缝隙送出去。西尔勒也得到了问题的正确答案。西尔勒认为尽管计算机用这种符号处理方式也能正确回答问题,并且也可通过图灵测试,但仍然不能说计算机就有了智能。

人工智能的发展概况

1.形成期（1956--1970年）AI诞生于一次历史性的聚会(Dartmouth人工智能夏季研讨会)时间：1956年夏季地点：美国达特茅斯(Dartmouth)大学目的：为使计算机变得更“聪明”，或者说使计算机具有智能发起人：麦卡锡(J.McCarthy），Dartmouth的年轻数学家、计算机专家，后为MIT教授明斯基(M.L.Minsky），哈佛大学数学家、神经学家，后为MIT教授洛切斯特(N.Lochester)，IBM公司信息中心负责人香农(C.E.Shannon)，贝尔实验室信息部数学研究员会议结果：由麦卡锡提议正式采用了“ArtificialIntelligence”这一术语人工智能的发展概况2.形成期（1956----1970年）其他开创性贡献1958年，美籍华人数理逻辑学家王浩在IBM-740计算机上仅用了3-5分钟就证明了《数学原理》命题演算全部220条定理。1965年，费根鲍姆(E.A.Feigenbaum)开始研究化学专家系统DENDRAL，用于质谱仪分析有机化合物的分子结构。1969年召开了第一届国际人工智能联合会议（InternationalJointConferenceonAI，IJCAI），标志着人工智能作为一门独立学科登上了国际学术舞台。此后IJCAI每两年召开一次。1970年《InternationalJournalofAI》创刊。人工智能的发展概况3.暗淡期（1966----1974年）失败的预言给人工智能的声誉造成重大伤害“20年内，机器将能做人所能做的一切”---------1965在博弈方面：塞缪尔的下棋程序在与世界冠军对弈时，5局败了4局。在定理证明方面：发现鲁宾逊归结法的能力有限。当用归结原理证明两个连续函数之和还是连续函数时，推了10万步也没证出结果。在机器翻译方面：发现并不那么简单，甚至会闹出笑话。例如，把“心有余而力不足”的英语句子翻译成俄语，再翻译回来时竟变成了“酒是好的，肉变质了”在问题求解方面：对于不良结构，会产生组合爆炸问题。在神经生理学方面：研究发现人脑有1011-12以上的神经元，在现有技术条件下用机器从结构上模拟人脑是根本不可能的。在英国，剑桥大学的詹姆教授指责“人工智能研究不是骗局，也是庸人自扰”。从此，形势急转直下，在全世界范围内人工智能研究陷入困境、落入低谷。

人工智能的发展概况

4.知识应用期（1970----1988年）整个20世纪80年代，专家系统和知识工程在全世界得到了迅速发展。专家系统为企业等用户赢得了巨大的经济效益。在开发专家系统过程中，许多研究者获得共识，即人工智能系统是一个知识处理系统，而知识获取、知识表示和知识利用则成为人工智能系统的三大基本问题。同时出现新的问题：专家系统本身所存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、没有分布式功能、不能访问现存数据库等问题被逐渐暴露出来。人工智能的发展概况

5.集成发展期（1986年以来）1997年5月11日，由IBM研制的超级计算机“深蓝”首次击败了国际象棋特级大师卡斯帕洛夫。2000年，中国科学院计算所开发出知识发现系统MSMiner。该系统是一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种知识发现方法。2011年，IBM超级电脑“沃森”亮相美国最受欢迎的智力竞赛节目《危险边缘》战胜该节目两位最成功的选手。人工智能研究形成了三大学派符号主义连接主义行为主义符号主义又称：逻辑主义、心理学派或计算机学派符号主义的实现基础是纽威尔和西蒙提出的物理符号系统假设。该学派认为：人类认知和思维的基本单元是符号，而认知过程就是在符号表示上的一种运算。它认为人是一个物理符号系统,计算机也是一个物理符号系统,因此,我们就能够用计算机来模拟人的智能行为,即用计算机的符号操作来模拟人的认知过程。这种方法的实质就是模拟人的左脑抽象逻辑思维，通过研究人类认知系统的功能机理，用某种符号来描述人类的认知过程，并把这种符号输入到能处理符号的计算机中，就可以模拟人类的认知过程，从而实现人工智能。可以把符号主义的思想简单的归结为“认知即计算”。连接主义又称：仿生学派或生理学派原理：神经网络及神经网络间的连接机制与学习算法。起源：源于仿生学，特别是人脑模型的研究。学派代表：卡洛克、皮茨、Hopfield、鲁梅尔哈特等。连结主义基本理论认为思维基元是神经元，而不是符号处理过程。认为人脑不同于电脑，并提出连结主义的大脑工作模式，用于取代符号操作的电脑工作模式。行为主义又称：进化主义或控制论学派原理：控制论及感知—动作型控制系统认为智能不需要知识、不需要表示、不需要推理；人工智能可以象人类智能一样逐步进化(所以称为进化主义)；智能行为只能在现实世界中与周围环境交互作用而表现出来。催化当今人工智能的出现三大催化剂1）摩尔定律在价格、体积不变的条件下，计算机的计算能力可以不断增长。这就是被人们所熟知的摩尔定律，它以Intel共同创办人GordonMoore命名。GordonMoore从各种形式的计算中获利，包括人工智能研究人员使用的计算类型。数年以前，先进的系统设计只能在理论上成立但无法实现，因为它所需要的计算机资源过于昂贵或者计算机无法胜任。今天，我们已经拥有了实现这些设计所需要的计算资源。举个梦幻般的例子，现在最新一代微处理器的性能是1971年第一代单片机的400万倍。催化当今