人工智能——搜索技术
转载：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)
人工智能在智能控制领域的应用前景怎么样，目前发展到什么程度
浅述人工智能在智能控制领域的应用
人工智能技术是用计算机去做原来只有人才能做的具有智能的工作，如符号、语言和知识表达、状态特征的识别、精确与模糊的信息处理、分析推理、判断决策等，将这一拟人思维的技术通过计算机来弥补传统控制方法的不足，促进了智能控制的迅猛发展。
智能控制一般按照实际结果进行控制，不依靠所控制对象的数学模型，传承了人类传统思想的非线性特性。它打破了传统控制理论中关于数学模型的框架。
1人工智能（AI）及智能控制的基本概念
人工智能是计算机学科的一个重要分支，一直处于计算机技术的前沿，被人们称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。人工智能研究的理论和发现在很大程度上将决定计算机技术的发展方向。
1.1人工智能的定义及应用领域
1.1.1人工智能的定义
人工智能（AI）也称机器智能，它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。
1.1.2人工智能的应用领域
①问题求解。计算机博弈是人工智能中关于对策和斗智问题的研究领域。目前，计算机博弈主要以下棋为研究对象，但研究的主要目的不是为了让计算机与人下棋，而是为了给人工智能研究提供一个试验场地。在下棋程序中体现出来的一些步骤，例如能够思考如何向前走几步，不仅要把对手的方法、步骤考虑进去，还能够把困难问题进行逐步分解，最终战胜对方的能力。如今的计算机软件已具有如象棋、围棋的世界锦标赛的先进水平。
②逻辑推理与定理证明。逻辑推理是人工智能研究中最持久的领域之一，重要的一点是要找到一些对策及方法，把大量的素材集中在一个大型数据库中（数据库需有很复杂的逻辑结构，甚至还要有模糊记忆），留意可信的证明，并在出现新信息时即时修正这些证明。定理证明就是让计算机模拟人类证明定理的方法，自动实现非数值符号的演算过程。如信息检索和医疗诊断等都可以和定理证明问题一样加以形式化。它方便了人类，促进了科学发展，达到了人类所不能及的智力……
③自然语言处理。自然语言处理主要研究如何使计算机能够理解和生成自然语言。现在的自然语言理解往往与模式识别、计算机视觉等技术结合在一起，在文字识别和语音识别系统的配合下进行书面语言和有声语音的理解。
④智能信息检索技术。当今，科学技术的飞速发展，信息获取是目前计算机科学与技术研究中迫切需要研究的课题。这一技术在人工智能领域的应用，能使人工智能迈向更广泛的实际应用当中。
⑤专家控制系统。专家系统是基于专家知识和符号推理方法的智能系统，它将专家领域的经验用知识表示的方法表示出来，放入数据库中，根据这些素材在推理机的作用下，解决某一专门行业内需要专家才能解决的问题。如在第二代专家系统中，把原理和经验分离开来，并引入基于前者的深层推理和基于后者的浅层推理，从而提高了系统运行的强壮性。现在这一点已被证实。如在矿物勘测、化学分析、医学诊断方面，专家系统已经达到了人类专家的水平。例如：地质勘探软件程序系统发现了一个钼矿沉积，价值超过1亿美元。MYCIN系统可以对人类血液传染病、乳腺癌的诊断治疗方案能够提供咨询意见；对患有细菌性血液病、脑膜炎方面的诊断和治疗方案已经超过了这一领域的专家水平。
1.2智能控制理论及研究领域
智能控制是在人工智能及自动控制等多学科之上发展起来的一门新兴、交叉学科，它具有非常广泛的应用领域，如专家控制、智能机器人控制、智能过程控制、智能故障诊断及智能调度与规划等。
1.2.1智能控制的定义
所谓智能控制是通过定性与定量相结合的方法，针对环境和任务的复杂性与不确定性，有效自主地实现复杂信息的处理及优化决策与控制功能。
1.2.2智能控制的研究领域
传统控制包括经典反馈控制和现代控制理论，它们的主要特征是基于精确的系统数学模型控制，在复杂问题的实际应用中遇到了不少难题。因此，需将人工智能的方法引入控制系统，从而实现系统的智能化，即通过采用仿人智能控制决策，迫使控制系统向期望的方向发展。
智能控制是一类无需（或尽可能少的）人的干预就能够独立自主地应付环境条件或加工对象的变化，有效地驱动智能机器实现其目标的自动控制，它是自动控制的最新发展阶段，对智能控制系统的研究和设计，重点放在对任务和世界模型的描述、符号和环境的识别以及知识库和推理机的设计开发上，即放在智能机模型上。
3发展前景
3.1人工智能的发展趋势
加强对人脑科学工业领域的应用，深入调研分析，掌握人工神经网络、机器人、新型人工智能产品等的发展和应用，整合现有资源，形成一些这方面的国家级或省级的技术中心和实验室，推动人工智能关联技术在医疗、工业、三网联合等方面快速发展。
人工智能的飞速发展，使越来越多的具有智能的机器进入了人类的生活，并且在人类生活中扮演着重要的角色。它们比血肉之躯的脆弱人类更灵活，甚至在智力的某些方面，它们已经超过了我们。机器宠物、智能电脑游戏、深海机器人、汉字识别系统、语音识别系统，这些智能机器让我们惊觉。
未来人工智能技术将进一步推动关联技术和新兴科技、新兴产业的深度融合，推动新一轮的信息技术革命，其人工智能技术将成为我国经济结构转型升级崭新的支撑点。
3.2智能控制的发展趋势
智能控制的应用领域已从工业生产渗透到生物、农业、地质、军事、空间技术、医疗、环境科学、社会发展等众多领域，在世界各国的高技术研究发展计划中有着重要的地位。由于这些任务的牵引，相信智能控制必将在控制理论的发展中引起新的飞跃。人工智能、大数据、云计算和物联网的未来发展值得重视，均为前沿产业，有兴趣的朋友，可以查阅多智时代，在此为你推荐几篇优质好文：
人工智能来势凶猛，人工智能最热门的技术趋势是什么？人工智能时代的研究热点是什么，主要应用领域是什么？人工智能培训就业的特点有哪些多智时代-人工智能和大数据学习入门网站|人工智能、大数据、物联网、云计算的学习交流网站