人工智能导论 第二章 搜索技术
2.1搜索的基本概念搜索：一种求解问题的一般方法
问题求解的基本方法：搜索法、归约法、归结法、推理法及产生式
基本问题：1、是否一定能找到一个解
2、找到的是否是最佳解
3、时间和空间复杂度
4、是否会终止运行or死循环
主要过程：1、从初始或目的状态出发，并将其作为当前状态
2、扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向父节点的指针
3、检查所生成的新状态是否满足结束状态。若满足，反向得出解答路径；否则将新状态定义为当前状态返回2
概念术语搜索方向（1）数据驱动：初始状态出发正向搜索
（2）目的驱动：从目的状态出发逆向搜索
（3）双向搜索找到汇合点
盲目搜索与启发式搜索（1）盲目搜索：不针对特定问题任何有关信息，按照固定步骤搜索
（2）启发式搜索：考虑特定问题可应用的知识，动态确定算子，优先选择合适算子，减少步骤
状态表示系统状态、事实等叙述性知识的一组变量或数组
操作表示引起状态变化的过程型知识的一组关系或函数
2.2状态空间的搜索策略状态空间：利用状态变量和操作符号，标识系统或问题的有关知识的符号体系，三元组（S、F、G）
S：状态集合F：操作算子的集合G：目的状态集合
求解路径从S0到G结点的路径，状态空间的一个解是一个有限的操作算子序列
表示方法：图描述八数码问题的图描述
TSP问题的图描述
2.3盲目搜索回溯策略从初始状态出发不停试探路径，直到到达目的或“不可解节点”。若遇到不可解节点就回溯到路径中最近的父节点上，查看该节点是否还有其他子节点未被扩展。
算法：
1、PS表：保存当前搜索路径上的状态，如果找到目的，PS就是解路径上的状态有序集
2、NPS表：新的路径状态表，包含等待搜索的状态，后裔状态还未被搜索到
3、NSS表：不可解状态集，列出找不到接替路径的状态。如果在搜索中扩展出他的元素，可立即排除
图搜索算法（DFSBFS最好优先搜索）的回溯思想
（1）用NPS使算法可以回归到任意状态
（2）用NSS避免算法重新搜索无解路经
（3）PS表中记录当前搜索路径状态，满足目的时可以将其作为结果返回
（4）为避免死循环，需要对子状态及性能检查，看是否在3张表中
广度优先搜索策略例题：机器人积木动作序列问题
算子MOVE（X，Y）的先决条件：
1、被搬动积木顶必为空
2、若Y是积木，Y顶部也必须为空
3、同状态下操作算子运用次数不得多于1次
深度优先搜索策略深度优先搜索中，当搜索到某一状态，其所有子状态及子状态的后裔状态必须先于该状态的兄弟状态被搜索。并且为了保证找到解，应选择合适的深度限制或不断加大深度限制值，反复搜索。
深度优先搜索并不能保证第一次搜索到某个状态时的路径是到这个状态的最短路径，如果算法多次搜索到同一个状态时应当保留最短路径
盲目搜索——代价树搜索代价树搜索：用于寻找最小代价路径问题，是推广版的BFS（如果权值都一致的话就是BFS）
比较图搜索与树搜索：
最短路径的图搜索：搜索算法认为一个状态只能对应搜索图中的一个节点
最短路径的树搜索：同一个状态可以多次出现在树中，相同状态可以同时出现在搜索中代表不同节点
实际操作中可以从搜索树构造搜索图搜索算法，从边缘集合中取出那些会导致搜索出现重复状态的节点。
搜索图是动机的角度，搜索树是实现的角度。
例题：卒子穿阵问题
2.4启发式图搜索启发式策略启发：关于发现和发明操作算子及搜索方法的研究
在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。
启发式策略：利用问题相关的启发信息进行搜索
运用启发策略的两种基本情况1、一个问题由于在问题陈述和数据获取方面的模糊性，可能使它没有确定解
2、虽有可能有确定解，但是状态空间特别大，生成扩展的状态数会随搜索深度指数级增长
启发信息和估价函数求解问题中利用的大多是非完备的启发信息
1、求解问题系统不能知道与实际问题有关的全部信息，无法知道所有状态空间，无法用一套算法求解所有问题
2、虽然理论上存在求解算法，但工程实践中不是效率太低就是无法实现
启发信息分类1、陈述性2、过程性
3、控制性（没有任何控制性知识作为搜索依据，所以每一步都是随意的；有充分的控制知识作为依据，因而搜索的每一步选择都是正确的）
估价函数：估计代搜索节点的有希望程度，并依次给它们拍定次序
估价函数f（n）从初始节点经过n节点到达目的节点的路径的最小代价估计值f=g+h（g越大先用宽度优先，h越大表示启发能力越强）
总结：利用知识来引导搜索，减少搜索范围，降低问题复杂度
启发信息的强度可以分为：强：降低搜索工作量，可能导致找不到最优解
弱：导致工作量加大，极限情况下可以盲目搜索，但可能找到最优解
引入启发知识，在保证找到最优解的情况下尽可能缩小搜索范围，提高搜索效率
例题：八数码的估价函数
A搜索算法启发式图搜索算法的基本特点：寻找并设计一个与问题相关的h（n）及构出f（n）=g+h，然后以f（n）的大小来排列待扩展状态的次序，每次选f值最小者进行
open表：保留所有已生成而未扩展的状态
closed表：记录已扩展过的状态
进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态进行扩展。
每次重复时，A搜索算法从open表中取出第一个状态。如果该状态满足目标条件，则算法返回到该状态的搜索路径。
如果open表的第一个状态非目的状态，则算法通过一系列操作算子进行相应操作来产生其子状态。若某子状态在open&closed表中出现过，即该状态再一次被发现时 ，通过刷新祖先状态的历史记录，使算法可能找到更短路径。
A搜索算法接着open表中每个状态的估价函数值，按照值大小重新排序，将值最小的状态放在表头，使其第一个被扩展。
例题：利用A搜索算法求解八数码问题的搜索树，估价函数定义为f=d+w
d：为状态深度，每步代价为单位代价。w：以“不在位”的将牌数作为启发信息的量度。
（A&A*搜索树）
A*搜索算法及其特性分析若某一问题有解，A*一定能搜索到解且一定能得到最优解。
A算法没有对估价函数f（n）作任何限制，实际上估价函数对搜索过程也十分重要
A*就是对估价函数加上一些限制后得到的一种启发式搜索算法
可容性：启发函数不会高估从节点n到终止节点所应付出的代价
一致性：三角不等式h(n)
【人工智能导论不挂科】期末考试重点知识点独家整理归纳
《人工智能导论》期末复习知识点
选择题知识点
1.人工智能、人工神经网络、机器学习等人工智能中常用词的英文及其英文缩写。
人工智能ArtificialIntelligence,AI
人工神经网络ArtificialNeuralNetwork，ANN
机器学习MachineLearning，ML
深度学习DeepLearning,DL
2.什么是强人工智能？
强人工智能观点认为有可能制造出真正能推理（Reasoning）和解决问题（Problem_solving）的智能机器，并且，这样的机器将被认为是有知觉的，有自我意识的。可以独立思考问题并制定解决问题的最优方案，有自己的价值观和世界观体系。有和生物一样的各种本能，比如生存和安全需求。在某种意义上可以看作一种新的文明。
3.回溯算法的基本思想是什么？
能进则进。从一条路往前走，能进则进，不能进则退回来，换一条路再试。
4.面向对象、产生式系统、搜索树的定义？
面向对象(ObjectOriented)是软件开发方法，一种编程范式。面向对象的概念和应用已超越了程序设计和软件开发，扩展到如数据库系统、交互式界面、应用结构、应用平台、分布式系统、网络管理结构、CAD技术、人工智能等领域。面向对象是一种对现实世界理解和抽象的方法，是计算机编程技术发展到一定阶段后的产物。面向对象是相对于面向过程来讲的，面向对象方法，把相关的数据和方法组织为一个整体来看待，从更高的层次来进行系统建模，更贴近事物的自然运行模式。
把一组产生式放在一起，让它们相互配合，协同工作，一个产生式生成的结论可以供另一个产生式作为前提使用，以这种方式求得问题的解决的系统就叫作产生式系统。
对于需要分析方法，诸如深度优先搜索和广度优先搜索（穷尽的方法）以及启发式搜索（例如最佳优先搜索和A*算法），这样的问题使用搜索树表示最合适。
5.机器学习的基本定义是什么？
机器学习是一门研究及其获取新知识和新技能，并识别现有知识的学问。
6.智慧地球的概念，智慧地球提出的背景是怎样的？
借助新一代信息技术（如传感技术、物联网技术、移动通信技术、大数据分析、3D打印等）的强力支持，让地球上所有东西实现被感知化、互联化和智能化。
背景为金融危机影响全球。
7.相关关系是怎么回事？
相关关系是客观现象存在的一种非确定的相互依存关系，即自变量的每一个取值，因变量由于受随机因素影响，与其所对应的数值是非确定性的。相关分析中的自变量和因变量没有严格的区别，可以互换。
8.盲目搜索是什么意思？
盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题，盲目搜索通常是按预定的搜索策略进行搜索，而不会考虑到问题本身的特性。常用的盲目搜索有宽度优先搜索和深度优先搜索两种。
填空题知识点。
1. Wiener在智能活动领域的理论贡献？
创立控制论，开创了一个全新的学科“控制科学”（ControlScience），也开创了人工智能中的行为主义学派。
2.常见的盲目搜素算法有哪些？
常用的盲目搜索有宽度优先搜索和深度优先搜索两种。
3.最佳优先搜索算法？
最佳优先搜索（BestFirstSearch），是一种启发式搜索算法（HeuristicAlgorithm）,我们也可以将它看做广度优先搜索算法的一种改进；最佳优先搜索算法在广度优先搜索的基础上，用启发估价函数对将要被遍历到的点进行估价，然后选择代价小的进行遍历，直到找到目标节点或者遍历完所有点，算法结束。
4.大类来分，主要有哪三类机器学习算法？
监督学习、无监督学习、强化学习
5.监督学习的主要类型？
分类和回归，详见书上127页
6.人工智能之父是指？图灵测试的含义？
图灵。它的意义在于推动了计算机科学和人工智能的发展。
7.大数据时代，相关性和因果性的异同？
异：因果关系很难被轻易证明，但证明相关关系实验耗资少，费时也少。
同：相关关系为研究因果关系奠定了基础。
8.产生式系统的形式规则集怎样表示的？
IF[条件]THEN[动作]
9.机器学习算法都是基于什么理论的？
机器学习(MachineLearning,ML)是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。
3.简答题知识点
1.大数据时代的思维转变？
1.样本=总体
2.接受数据的混杂性
3.数据的相关关系
2.人工智能领域的主要应用有哪些？
深度学习、自然语言处理、计算机视觉、智能机器人、自动程序设计、数据挖掘
3.知识表示法有哪些?
叙述式表示法、过程式表示法
4.线性回归与逻辑回归的比较。
参考一：在线性回归模型中，输出一般是连续的，对于每一个输入的x，都有一个对应的输出y。因此模型的定义域和值域都可以是无穷。
但是对于逻辑回归，输入可以是连续的[-∞,+∞]，但输出一般是离散的，通常只有两个值{0,1}。
参考二：逻辑回归的模型是一个非线性模型，sigmoid函数，又称逻辑回归函数。但是它本质上又是一个线性回归模型，因为除去sigmoid映射函数关系，其他的步骤，算法都是线性回归的。可以说，逻辑回归，都是以线性回归为理论支持的。
只不过，线性模型，无法做到sigmoid的非线性形式，sigmoid可以轻松处理0/1分类问题。
5.人工智能时代的重要工作岗位。
数据科学家、机器学习工程师、数据标签专业人员、AI硬件专家、数据保护专家
6.为什么在大数据时代更关注相关关系？
相关关系实验耗资少、费时也少。为我们提供新的视角，而且提供的视角都很清晰。
7.语义网络如何理解？
语义网络是知识表示中最重要的通用形式之一，是一种表达能力强而且灵活的知识表示方法。它通过概念及其语义关系来表达知识的一种网络图。
8.神经元与神经网络的关系？神经元的工作原理。
关系：神经网络从这种自然典范中汲取灵感，设计人工神经网络。
原理：神经元由一个细胞体和突两部分组成。突分两类，轴突和树突。 树突和轴突共同作用，实现神经元之间的信息传递。
轴突的末端与树突进行进行信号传递的界面成为突触，通过突触向其他神经元发送信息。学习发生在突触附近，而且突触把经过一个神经元轴突的脉冲转化为下一个神经元的兴奋信号或抑制信号。
对某些突触的刺激促使神经元触发，只有神经元所有输入的总效应达到阈值电平，它才开始工作。
综合应用题的知识点
1.常用的机器学习算法有哪些？各自的特点和适用领域是怎样的？
回归算法：是最快速的机器算法之一，分类，预测离散值。
KNN算法：最基础和简单的算法之一，用于分类，比较数据点的距离，并将每个点分配给它最接近的组。
决策树算法：将一组“弱”学习器集合在一起，形成一种强算法。主要用来分类，也有做回归，但更多的是作为弱分类器，用在model
贝叶斯算法：通过找到样本所属于的联合分步，然后通过贝叶斯公式，计算样本的后验概率。用于文本分析、分类
聚类算法：发现元素之间的共性并对它们进行相应的分组。
神经网络算法：通过找到某种非线性模型拟合数据，主要用在图像处理等
2.专家系统的概念、结构、各模块的作用怎样？。
专家系统是一种模拟人类专家解决领域问题的计算机程序系统。
人机交互界面、知识库、推理机、解释器、综合数据库、知识获取
人机界面：系统和用户进行交流的界面
知识库：存放专家提供的知识
推理机：对当前问题的条件或已知消息，仿佛匹配知识库中的规则，获取新理论，以得到问题求解结果
解释器：能根据用户的提问，对结论、求解过程做出说明
综合数据库：专门用于存储推理过程中所需要的原始数据、中间结果和最终结论
希望可以帮助到你，祝小可爱逢考必过，考试资料持续更新，感谢关注点赞支持哦~