人工智能——搜索技术
转载：https://blog.csdn.net/Sun7_She/article/details/40344329
AI-3的80~84不懂
A*算法不懂
引言：
什么是搜索：
根据问题的实际情况不断寻找可利用的知识，构造出一条代价较少的推理路线，使问题得到圆满的解决的过程称为搜索。
包括两个方面：
——找到从初始事实到问题最终答案的一条推理路径
——找到的这条路径在时间和空间上复杂度最小
搜索分两大类：
盲目搜索：也称无信息搜索，即只按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。
启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向进行，加速问题的求结果称并找到最优解。
回溯问题——皇后问题
存在问题：深度问题、死循环问题
解决办法：对搜索深度加以限制、记录从初始状态到当前状态的路径
图搜索策略：
在对问题的状态空间进行搜索时：
回溯搜索：只保留从初始状态到当前状态的一条路径
图搜索：保留所有已经搜索过的路径
一些基本概念：
节点深度——根节点深度=0
其他节点深度=父节点深度+1
路径：设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。
路径的耗散值：一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。
扩展一个节点：生成出该节点的所有后继节点，并给出它们之间的耗散值，这一过程称为“扩展一个节点”。
无信息图搜索过程：
深度优先搜索、宽度优先搜索
深度优先搜索的性质：
一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法
时间复杂度O(bm):如果m比b大很多则比较严重空间复杂度O(bm),线性空间缺点：如果目标节点不在搜索所进入的分支上,而该分支又是一个无穷分支,则就得不到解.因此该算法是不完备的优点：如果目标节点恰好在搜索所进入的分支上,则可以较快地得到解
宽度优先搜索性质：
当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法
时间复杂度1+b+b2+b3+…+bd+b(bd-1)=O(bd+1)空间复杂度O(bd+1)————空间是大问题(和时间相比)缺点：当目标节点距离初始节点较远时会产生许多无用的节点,搜索效率低优点：只要问题有解,则总可以得到解,是完备的，而且是最短路径的解
回溯与宽度优先方法的结合：
目的：解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想：首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所有分支为止。
时间和空间复杂度：
一字棋的棋局数:9!=105跳棋的棋局数:大约1078国际象棋的棋局数:大约10120围棋的棋局数:大约10761搜索速度10-100年/步 搜索一遍国际象棋的时间是1016年(一亿亿年),宇宙的寿命100亿年.
启发式图搜索：
利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的
启发信息的强度——强：降低搜索工作量，但可能导致找不到最优解
弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能找到最优解
希望：
引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率
路径的耗散值和求取路径所需搜索的耗散值二者的组合最小
基本思想：
定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展
启发式搜索算法A（A算法）
1、A算法与A*算法定义
或图通用算法在采用如下形式的估计函数时,称为A算法。 f(n)=g(n)+h(n) 其中g(n)表示从s到n点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)可计算出。h(n)表示从n到g接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。
符号意义：
g(n)：从S到n的最短路径的耗散值h(n)：从n到g的最短路径的耗散值f(n)=g(n)+h(n)：从s经过n到g的最短路径的耗散值g*(n)、h*(n)、f*(n)分别是g(n)、h(n)、f(n)的估计值
算法特例：
1、若令h(n)≡0，则A算法相当于宽度优先搜索，因为上一层节点的搜索费用一般比下一层的小。2、g(n)≡h(n)≡0，则相当于随机算法。3、g(n)≡0，则相当于最佳优先搜索算法。4、特别是当要求h(n)≤h*(n）， 就称为这种A算法为A*算法。
A算法举例：
同一问题三种不同方法的比较：
深度优先扩展次数:13 未扩展结点8 搜索树中的结点21宽度优先扩展次数:8 未扩展结点9 搜索树中的结点17启发式搜索扩展次数:6 未扩展结点8 搜索树中的结点14
A*算法：
在A算法中，如果满足条件： (1)g(n)是对g*(n)的估计g(n)>0 (2)h(n)≤h*(n) ， 则A算法称为A*算法。
迭代加深A*
基本思想：回溯与A*的结合
其他搜索算法：
1、爬山法（局部搜索算法）
2、分枝定界法
3、动态规划法：如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法
算法描述：通过删除多余后继节点大大减少了搜索空间，从而降低了搜索费用。 删除了四个节点，从而减少了8个节点的扩展生成。
4、分支界限法：分支界限法是优先扩展当前具有最小耗散值分支路径的端节点；评价函数：f(n)=g(n)
人工智能发展与应用综述
人工智能发展与应用综述摘要自人工智能的概念在1956年被提出以来，研发者们就不断研究，六十多年的发展，在理论研究以及应用领域都已取得了喜人的成果，人工智能在医疗，交通，教育，商业，信息安全等领域已经深入国民生活。本文对人工智能概念进行解读，并对人工智能发展与应用进行综述，探索人工智能发展轨迹，以更好认识人工智能，对行业技术与发展有更深刻的理解。
关键词：人工智能发展应用综述总结1、引言人工智能的概念越来越深刻影响着人类的生活，如同蒸汽时代的蒸汽机，电气时代的发电机，信息时代的计算机，人工智能已经成为推动人类进入智能时代的决定性力量。当然，人工智能并不是凭空产生的，其发展具有一定的过程，在无数科学研究者，学者的辛勤努力下，人工智能研究的研究体系已经初见成果。人工智能的概念产生于欧美、日本等国家，并迅速风靡全球，可喜的是，根据清华大学发布的《人工智能发展研究报告2018》统计，我国已经成为全球人工智能投资融资规模最大的国家，我国人工智能在人脸识别，语音识别，安防监控，智能音箱，智能家居等人工智能应用领域处于国际前列。根据2017年，爱思唯尔文献数据库[1]统计结果，我国在人工智能领域发表的论文数量已居世界第一。当然，作为一项新兴事物，人工智能并非完美无缺，在许多方面仍然有较多的困难尚未攻克，本文对人工智能发展与应用进行综述[2、3]，指导正确看待这一新兴事物，更好指导未来的技术发展。
2、人工智能以及核心概念由于“智能”这一概念难以确切定义，图灵用：“机器能够思考吗？”这一问题代替。图灵提出通过对机器进行“图灵测试”，以判断它是否具有智能。“图灵测试”就是让机器当做人，与人进行对话，如果有30%的测试人相信此机器是人类，那么这台机器被认为具有智能。美国斯坦福大学人工智能研究中心尼尔逊教授给人工智能下了这样的定义：人工智能是关于知识的学科，是怎样表示知识以及怎样获得知识并使用知识的科学。从实用观点来看，人工智能是一本知识工程学：以知识为对象，研究知识的获取，知识的表示方法和知识的使用。目前学术界将人工智能分为强人工智能和弱人工智能，强人工智能就是机器具有自我意识，要求机器有知觉有意识。弱人工智能是指没有知觉意识的智能，机器按照事先写好的程序进行工作，并不拥有智能。
（1）、机器学习机器学习[4]是人工智能的核心技术，是使机器拥有智能的主要途径，是指让机器模拟人的学习能力，以此来增强机器的性能。早在上个世纪图灵就给出了类似机器学习的想法，他设想让机器模仿儿童思维，使其接受正确的教育成长为一个成人的大脑。这种想法与当今学者研究的方向不谋而合。后来图灵与同事一起编写了程序去实践这种想法，机器能够做他们编写过的事情，除此之外，不会向人类一样在能力方面有更多的延伸。如何让机器自主的学习，在今天仍然是人工智能发展的难题。
（2）、人工神经网络是受人脑神经元的启发，试图设计与人脑结构类似的网络结构，模拟大脑处理信息的的过程，以提高运算速度。作为人工神经网络的一类，卷积神经网络已经广泛用于大型图像处理中。虽然人工神经网络无法与人类大脑媲美，在模式识别，医疗，智能机器人等领域取得的成果有目共睹。
(3)、专家系统是指依靠人类专家已有的知识建立的知识系统，是一种特定领域内大量知识与经验的程序系统。它应用人工智能技术，模拟人类专家求解问题的思维过程求解领域内的各种问题，其水平可以甚至超过人类专家的水平。目前专家系统开发最早应用最广泛的领域，多是医疗诊断，地质勘探，文化教育等领域。
3.发展历程回顾人工智能的发展可以有以下四个时期：孕育，形成，知识运用，综合集成四个阶段。孕育期：一般认为人工智能的最早工作是Warre基本出发点。Mcculloch跟WalterPitts完成的。他们提出一套人工神经元模型，两名普林顿大学数学系的研究生在1951年建造了第一台神经元网络计算机。不少早期工作可以被当做人工智能，古希腊的亚里士多德创立的演绎法，三段论的至今仍然是演绎推理的基本出发点。形成期：人工智能诞生于1956年的一次历史性聚会。几位来自美国的数学，神经学，心理学，信息科学和计算机科学的杰出科学家齐聚一堂，由麦卡锡提出了“人工智能（AI）”这一概念。会议过后，各地的科学家、学者纷纷研究相关知识，“人工智能”这一学科以及相关研究如雨后春笋一般形成。1969年的国际人工智能联合会议标志着人工智能得到国际的认可。知识应用期：1977年费根鲍姆在第五届国际人工智能大会上提出了知识工程的概念。从此之后，各类专家系统得以发展，大量的商品化专家系统和智能系统纷纷推出。专家系统的发展，也是得人工智能的发展范围扩大到了人类各个领域，并产生了巨大的经济效益。但是专家系统发展过程中也存在很多缺陷，应用领域窄，缺乏常识性知识，知识获取困难，不能访问现存的数据库等问题被逐渐暴露出来，人工智能面临着考验。综合形成期，在专家系统方面，从20世纪80年代末开始逐步向多技术，多方法的综合集成与多领域的综合应用型发展。大型专家系统开始采用了人工智能的多种语言，多种知识表示方法，多种推理机制和多种在控制策略相结合的方式，人工智能的发展进入综合形成期。目前，人工智能技术正在向大型分布式人工智能，大型分布式多专家协同系统，并行推理，多种专家系统开发工具，大型分布式人工开发环境和分布式环境下的多智能协同系统等方向发展。但是从目前来看，无论是人工智能理论还是实践都不够成熟，人工智能研究仍然需要科研工作者长期摸索。
4、人工智能的应用（1）、虚拟各人助理目前市面上的人工智能助理如：Siri，小娜等。个人助理能够帮助用户完成多项任务，多项服务，其推动力是人工智能技术。现阶段的人工助理一般具有基于上下文的对话能力，可以实现简单的人机对话，回答一些简单的问题。个人助理的应用包括语音识别，图像识别，深度学习等技术，其工作原理是“语音识别+云计算服务”。
（2）、自动驾驶谷歌公司一直致力于自动驾驶汽车的研究，2012年4月。谷歌公司宣布自动驾驶汽车已经行驶20万公里，这一数据已经接近汽车的最大里程数。我国自动驾驶技术的研究同样取得振奋人心的成果。2017年由海梁科技与深圳巴士集团等联合打造的自动驾驶客运巴士，正式进行线路的信息采集和试运行。
（3）、智慧医疗医疗一直是关系到国际民生的重要范畴。随着专家系统的不断发展完善，已有实例表明，人工智能可参与到医疗建设中。Watson[5]是IBM公司研发的采用认知计算系统的人工智能平台，watson肿瘤系统是其产品之一，可以作为辅助诊疗手段，与医院数据对接，实现病例数据的信息共享，还可以为临床医生在诊断过程中推荐诊疗方案，苏北人民医院2017年正式引入此系统，开启了智慧医疗的新时代。
5、我国人工智能发展趋势与展望人工智能技术发展至今60多年，其概念已经逐渐清晰，在生物，医疗，交通等领域孕育出了突破性的成果，但是人工智能技术能否发展到人类的水平仍然不能给出确切的答案。目前人工智能面临的问题主要是：
（1）、体系结构受限受限于冯诺依曼体系结构，目前人工智能系统在感知，认识方面无法突破瓶颈。这主要是由于传统的冯诺依曼体系结构采用的是存储程序的方法，程序是事先设定的，无法随着外界的改变而改变，这也是限制人工智能发展的关键。不过，我们有理由相信，在不久的未来能够克服这种制约。
（2）、社会问题困扰如果人工智能真的发展到与人类智慧媲美的程度，又会引发一系列的问题。一方面心理学上，“恐怖谷”理论就是假如机器人接近人类的时候，我们会对其产生莫名的厌恶和惧怕。另一方面，人工智能带来的社会问题同样困扰着人类，以自动驾驶汽车为例，3-18美国自动驾驶车辆车祸致人死亡的事件给自动驾驶技术的发展带来不小的冲击，事故责任的划分成为一大难题。目前人工智能的发展，主要是在弱人工智能发展并取得显著的成果，在强人工智能的研究上仍在开展，存在很多问题，有很大的发展空间，从目前的一些前瞻性研究可以看出人工智能可能会向以下几个方面发展：模糊处理，并行化，神经网络和机器情感。人工智能的下一个突破可能是赋予计算机情感能力。
参考文献
[1]中央人民政府驻香港特别行政区联络办公室副主任中国科学院院士谭铁牛.人工智能的发展趋势及对策[N].中华工商时报,2019-02-25(003).[2]张妮,徐文尚,王文文.人工智能技术发展及应用研究综述[J].煤矿机械,2009,30(02):4-7.[3]杨俊龙,柳作栋.人工智能技术发展及应用综述[J].计算机产品与流通,2018(03):132-133.[4]陈彦淇.简析人工智能的发展与应用[J].科技传播,2019(04):162-163+170.[5]曹敦煜.人工智能在心脏疾病诊疗中的应用[J].科技传播,2019(04):141-142.