[toc]
软件设计师笔记08_算法设计与分析
下面的内容参考自《软件设计师教程(第5版)》 这本书的第8章 算法设计与分析。
算法被公认为是计算机科学的基石，算法理论研究的是算法的设计技术和分析技术。
前者回答的是“对特定的问题，如何提出一个算法来求解?”这样的问题。后者回答的是“该算法是否足够好?"。二者是互相依存的，设计出的算法需要检验和评价，对算法的分析反过来又可以帮助改进算法的设计。
本章知识点结构图 
算法分析与设计的基本概念
算法概念
算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
一个算法还具有下列5个重要特性。即有穷性、确定性、可行性、输入、输出。
- 有穷性。一个算法必须总是在执行有穷步之后结束，且每步都可在有穷时间内完成。
- 确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
- 可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
- 输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
算法分析
通常，求解一个问题可能会有多种算法可以选择，选择的主要标准首先是算法的正确性、可靠性、简单性和易理解性，其次是算法的时间复杂度和空间复杂度要低，这是算法分析技术的主要内容。
从基本概念上看，算法分析是指对一个算法所需要的资源进行估算，这些资源包括内存、通信带宽、计算机硬件和时间等，所需要的资源越多，该算法的复杂度就越高。而在计算机资源中，最重要的是时间和空间(存储器)资源，因此复杂度分析主要包括时间复杂度和空间复杂度分析。
一个“好”算法的要求
正确性、健壮性、高效性
算法表示
常用的表示算法的方法有自然语言、流程图、程序设计语言和伪代码等。
- 自然语言。其最大的优点是容易理解，缺点是容易出现二义性，并且算法通常很冗长
- 流程图。其优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言
- 程序设计语言。其优点是能用计算机直接执行，缺点是抽象性差，使算法设计者拘泥于描还算法的具体细节，忽略了“好”算法和正确逻辑的重要性。并且还要求算法设计者掌握程序设计语言及编程技巧。
- 伪代码。伪代码是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，同时结合自然语言来表达。计算机科学家从来没有对伪代码的书写形式达成过共识。在伪代码中，可以采用最具表达力的、最简明扼要的方法来表达一个给定的算法。
算法分析基础
复杂度
复杂度是指算法执行所需要的时间和空间资源的量。分为时间复杂度和空间复杂度。
如图是一些不同数量级的复杂度，复杂度由小到大排列。
时间复杂度
算法的时间复杂度分析主要是分析算法重复执行的次数，即算法从开始到结束所需要的执行次数作为算法的时间度量。
一般不必要精确计算出算法的时间复杂度，只需要大致计算出响应的数量级即可，例如O(1)、O(n)、O(n^2^)等。
空间复杂度
空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。
分治法
递归的概念
在计算机算法设计与分析中，递归技术是十分有用的。
递归是指子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。
递归两个基本要素
- 边界条件（即确定递归到何时终止，也称为递归出口。）
- 递归模式（即大问题是如何分解为小问题的，也称为递归体。）
分治法的基本思想
分治与递归就像一对孪生兄弟，经常同时应用于算法设计之中，并由此产生许多高效的算法。
例如，对于n个元素的排序问题，当n=1时，不需要任何比较;当n=2时，只要做一次比较即可，………… 而当n较大时，问题就不那么容易处理了。要想直接解决一个较大的问题，有时是相当困难的。
分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。如果规模为n的问题可分解成k个子问题(1 < k < n)，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。
一般来说，分治算法在每一层递归上都有3个步骤。
- (1)分解。将原问题分解成一系列子问题。(子问题互相独立且与原问题相同)
- (2)求解。递归地求解各子问题。若子问题足够小，则直接求解。
- (3)合并。将子问题的解合并成原问题的解。
动态规划法
动态规划法的基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
因为动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。
为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
设计一个动态规划算法，通常按照以下几个步骤进行。
- (1)找出最优解的性质，并刻画其结构特征。
- (2)递归地定义最优解的值。
- (3)以自底向上的方式计算出最优值。
- (4)根据计算最优值时得到的信息，构造一个最优解。
- 步骤(1)~(3)是动态规划算法的基本步骤。在只需要求出最优值的情形下，步骤(4)可以省略。若需要求出问题的一个最优解，则必须执行步骤(4)。
贪心法
贪心法的基本思想
贪心法和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。
换而言之,贫心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。
举一个简单的贪心法例子，平时购物找钱时，为使找回的零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑各雨种，先尽量用大面值的雨种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是在采用贪心法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1、5和 11单位的硬币，而希望找回总额为 15 单位的硬币，按贪心算法，应找1个 11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。
如何得知是否可以用贪心法来求解以及能否得到问题的最优解呢?这类问题一般具有两个重要的性质。
- (1)最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
- (2)贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。
贪心法思想总结
贪心法：总是做出在当前来说是最好的选择,而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。
回溯法
回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。
回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯;否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时要回溯到根，且根结点的所有子树都已被搜索遍才结束;而用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法，它适用于解一些组合数较大的问题。
简而言之，回溯法可以系统地搜索一个问题的所有解或任一解。一般用于解决迷宫类的问题。回溯法的基本思想
在确定了解空间的组织结构后，回法从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动(回)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回潮法即以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。
分支限界法
分支限界法类似于回溯法，也是一种在问题的解空问树T上搜索问题解的算法。
但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法在解空问树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法以广度优先或以最小耗费优先的方式搜索解空间树 T。
分支限界法的搜索策略是每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
通常利用分支限界法解决了大量离散最优化的实际问题。与回溯法相似，限界函数的设计是分支限界法的一个核心问题，也是一个很难的问题。如何设计限界函数来有效地减小搜索空间是应用分支限界法要考虑的问题。
根据从活结点表中选择下一扩展结点的不同方式，可将分支限界法分为几种不同的类型。最常用的有以下两种。
- 队列式(FFO，先进先出)分支限界法。将活结点表组织成一个队列，并按队列的先进先出原则选择下一个结点作为扩展结点。
- 优先队列式分支限界法。将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点作为扩展结点。
分支限界法与回溯法的区别
- 分支限界法的求解目标是找出满足约束条件的其中一个解，即在某种条件下的最优解。而回溯法的求解目标是找出满足约束条件的所有解。
- 分支限界法以广度优先的方式搜索解空间树。而回溯法以深度优先的方式搜索解空间树。
概率算法
前面讨论的算法对于所有合理的输入都给出正确的输出，概率算法将这一条件放宽，把随机性的选择加入到算法中。在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。
概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解。
一般情况下，概率算法具有以下基本特征。
- 概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行机选择的随机数序列
- 概率算法在运行过程中，包括一处或多处随机选择，根据随机值来决定算法的运路径
- 概率算法的结果不能保证一定是正确的，但能限制其出错概率
- 概率算法在不同的运行过程中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。
概率算法的分类
- 数值概率算法（用于数值问题的求解。这类算法得到的往往是近似解,且近似解的精度随计算时间的增加不断提高。）
- 蒙特卡洛算法（用于求问题的精确解。但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间，算法所用的时间越多，得到正确解的概率就越高。）
- 拉斯维加斯算法（该算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。找到正确解的概率随它所用的计算时间的增加而提高。）
- 舍伍德算法（该算法总能求得问题的一个解，且所求得的解总是正确的。）
近似算法
近似算法是解决难解问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解,以换取算法设计上的简化和时间复杂度的降低。
近似算法是这样一个过程:虽然它可能找不到一个最优解，但它总会给待求解的问题提供一个解。为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解与最优解之间相差的程度。显然，这个差别越小，近似算法越具有实用性。
衡量近似算法性能最重要的标准有以下两个。
- 算法的时间复杂度。近似算法的时间复杂度必须是多项式阶的，这是近似算法的基本目标。
- 解的近似程度。近似最优解的近似程度也是设计近似算法的重要目标。近似程度与近似算法本身、问题规模，乃至不同的输入实例有关。
数据挖掘算法
在当今的大数据时代，我们需要各种技术来分析爆炸式增长的各类数据，以发现隐含在这些数据中的有价值的信息和知识。
数据挖掘利用机器学习方法对多种数据，包括数据库数据、数据仓库数据、Web 数据等进行分析和挖掘。数据挖掘的核心是算法，其主要功能包括分类、回归、关联规则和聚类等。
智能优化算法
智能优化算法是一种以数学为基础，用于求解各种工程问题优化解的应用技术。
人工神经网络
人工神经网络是一个以有向图为拓扑结构的动态系统，通过对连续或断续的输入作状态响应而进行信息处理。
从信息处理角度对人脑神经元网络进行抽象，建立某种简单模型，按不同的连接方式组成不同的网络
遗传算法
遗传算法源于模拟达尔文的“优胜劣汰、适者生存”的进化论和孟德尔.摩根的遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构。其本意是在人工适应系统中设计一种基于自然的演化机制。
模拟退火算法
模拟退火算法是一种求解全局优化问题的概率型算法。基本思想来源于物理退火过程，包括三个阶段：加温阶段、等温阶段、冷却阶段。
禁忌搜索算法
禁忌搜索算法是模拟人类智力过程的一种全局搜索算法，是对局部邻域搜索的一种扩展。
蚁群算法
蚁群算法是一种用来寻找优化路径的概率型算法。
蚁群算法的原理
蚂蚁在寻找食物或者寻找回巢的路径中，会在它们经过的地方留下一些信息素，而信息素能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动(具体表现在后到的蚂蚁选择有信息素的路径的可能性，比选择没有信息素的路径的可能性大得多)，而后到者留下的信息素会对原有的信息素进行加强，并如此循环下去。
这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可能性就越大(因为残留的信息素浓度较大)。由于在一定的时间内,越短的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。
这种行为表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多，则后到者选择该路径的概率就越大，因此距离近的食物源会吸引越来越多的蚂蚁，信息素浓度的增长速度就会越快，同时通过这种信息的交流，蚂蚁也就寻找到食物与蚁穴之间的最短路径了。
粒子群优化算法（鸟群觅食算法）
粒子群优化算法PSO：又称为鸟群觅食算法，在鸟群觅食飞行时，在飞行过程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体总保持一致性，个体与个体间也保持着最适官的距离。通过对类似生物群体行为的研究，发现生物群体中存在着一种信息共享机制，为群体的进化提供了一种优势，这就是基本粒子群算法形成的基础