[toc]
软件设计师笔记08_算法设计与分析
第八章 算法设计与分析
算法被公认为是计算机科学的基石，算法理论研究的是算法的设计技术和分析技术。
本章知识点结构图 
算法的基本概念
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
算法的5个重要特性
有穷性、确定性、可行性、输入、输出。
一个“好”算法的要求
正确性、健壮性、高效性
算法的复杂度
时间复杂度
时间复杂度：是指程序运行从开始到结束所需要的时间。
通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作以该操作重复执行的次数作为算法的时间度量。
空间复杂度
空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。
分治法
对于一个规模为n的问题，若该问题可以容易地解决则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。
递归
指子程序（函数）直接调用自己活通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。
递归两个基本要素
- 边界条件（确定递归何时终止，即递归出口）
- 递归模式（大问题如何分解成小问题，即递归体）
回溯法
回溯法：可以系统地搜索一个问题的所有解或任一解。
在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点触发搜索解空间树。搜索至任一结点时，总是先判断该结点是否肯定不包含问题的解，如果不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树；继续按深度优先的策略进行搜索。
- 可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外的分支，重复此步骤，这就是回溯，意为先一直探测，当不成功时再返回上一层。
- 一般用于解决迷宫类的问题。
动态规划法
动态规划法：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解
- 本质也是将复杂的问题划分成一个个子问题，与分治法不同的是每个子问题间不是相互独立的，并且不全都相同。
- 常用于求解具有某种最优性质的问题
- 此算法会将大量精力放在前期构造表格上面，其会对每一步都列出各种可能的答案，这些答案会存储起来，最终要得出某个结果时，是通过查询这张表来得到的动态规划法不但每一步最优，全局也最优。
贪心法
贪心法：总是做出在当前来说是最好的选择,而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。
- 局部贪心，只针对当前的步骤取最优，而非整体考虑。
- 判断此类算法，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的。
分支限界法
分支限界法：与回溯法类似，同样是在问题的解空间树上搜索问题解的算法。
分支限界法的搜索原理
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
分支限界法与回溯法的区别
- 求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解
- 以广度优先或以最小耗费（最大收益）优先的方式搜索解空间树。
如何从活结点表中选择下一个扩展节点的类型
- 队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点
- 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
概率算法
概率算法：在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少（降低算法复杂度）
- 基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果
- 如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解。
概率算法的分类
- 数值概率算法（数值问题的求解）
- 蒙特卡洛算法（求问题的精确解）
- 拉斯维加斯算法（不会得到不正确的解）
- 舍伍德算法（总能求得问题的一个正确解）
概率算法的特征
- 概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行机选择的随机数序列
- 概率算法在运行过程中，包括一处或多处随机选择，根据随机值来决定算法的运路径
- 概率算法的结果不能保证一定是正确的，但能限制其出错概率
- 概率算法在不同的运行过程中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同
近似算法
近似算法：解决难解问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂度的降低。
- 虽然它可能找不到一个最优解，但它总会给待求解的问题提供一个解
- 为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间的相差成都。显然，这个差别越小，近似算法越具有实用性
数据挖掘算法
数据挖掘算法主要用于分析爆炸式增长的各类数据的技术，以发现隐含在这些数据中的有价值的信息和知识。
数据挖掘利用及其学习方法对多种数据进行分析和挖掘。其核心是算法，主要功能包括分类、回归、关联规则和聚类等。
分类
分类是指一种有监督的学习过程，根据历史数据预测未来数据的模型。
分类的数据对象属性：一般属性、分类属性或目标属性。
分类设计的数据：训练数据集、测试数据集、未知数据数据。
分类的两个步骤
- 学习模型（基于训练数据集采用分类算法建立学习模型）
- 应用模型（应用测试数据集的数据到学习模型中，根据输出来评估模型的好坏以及将未知数据输入到学习模型中，预测数据的类型）
分类算法有哪些？
决策树归纳（自顶向下的递归树算法）、朴素贝叶斯算法、后向传播BP、支持向量机SVM
智能优化算法
智能优化算法是一种以数学为基础，用于求解各种工程问题优化解的应用技术。
人工神经网络ANN 算法
人工神经网络ANN算法：一个以有向图为拓扑结构的动态系统，通过对连续或断续的输入作状态响应而进行信息处理。从信息处理角度对人脑神经元网络进行抽象，建立某种简单模型，按不同的连接方式组成不同的网络
遗传算法
遗传算法：源于模拟达尔文的“优胜劣汰、适者生存”的进化论和孟德尔.摩根的遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构。其本意是在人工适应系统中设计一种基于自然的演化机制。
模拟退火算法SA
模拟退火算法SA：求解全局优化算法。基本思想来源于物理退火过程，包括三个阶段：加温阶段、等温阶段、冷却阶段。
禁忌搜索算法TS
禁忌搜索算法TS：模拟人类智力过程的一种全局搜索算法，是对局部邻域搜索的一种扩展
蚁群算法
蚁群算法：是一种用来寻找优化路径的概率型算法
粒子群优化算法PSO （鸟群觅食算法）
粒子群优化算法PSO：又称为鸟群觅食算法，在鸟群觅食飞行时，在飞行过程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体总保持一致性，个体与个体间也保持着最适官的距离。通过对类似生物群体行为的研究，发现生物群体中存在着一种信息共享机制，为群体的进化提供了一种优势，这就是基本粒子群算法形成的基础