十、算法分析与设计
10.1 算法分析
10.1.1 算法的特性
算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有5个重要特性：
-
有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步后结束，且每一步都在有穷时间内完成
-
确定下：算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出
-
可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现
-
输入：一个算法有零个或多个输入，这些输入来自某个特定的对象的集合
-
输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量
10.1.2 算法的复杂度
算法的时间复杂度分析：主要是分析算法的运行时间，即算法执行所需要的基本操作数。不同规模的输入所需要的基本操作数是不相同的。在算法分析中，可以建立以输入规模n为自变量的函数T(n)来表示算法的时间复杂度
即使对于相同的输入规模，数据分布不相同也影响了算法执行路径的不同，因此所需要的执行时间也不同。根据不同的输入，将算法的时间复杂度分析分为3中情况：最佳情况、最坏情况、平均情况
-
渐进符号：以输入规模n为自变量建立的时间复杂度时间上还是比较复杂的，例如an^2+bn+c，不仅与输入规模有关，还与系数a、b和c有关。此时可以对该函数做进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略式中的低阶项和高阶项的系数，仅考虑n^2.当输入规模大到只有与运行时间的增长量级有关时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着规模的无限增长而增长。
常用的标准方法：
O记号：定义为给定一个函数g(n)，O(g(n))={f(n):存在正常数c和n0，使得对所有的n>=n0,有0<=g(n)<=f(n)}。O(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界。
Ω记号：定义为给定一个函数g(n)，Ω(g(n))={f(n):存在正常数c和n0，使得对所有的n>=n0,有0<=g(n)<=f(n)}。Ω(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进下界。
θ记号：定义为给定一个函数g(n)，θg(n))={f(n):存在正常数c1、c2和n0，使得对所有的n>=n0,有0<=c1g(n)<=f(n)<=c2g(n)}。θ(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界和渐进下界，即渐进紧致界。
-
常数级、平方级、线性级、对数级
10.1.3 算法的复杂度递归
递归是指子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。递归有两个基本要素：边界条件，即确定递归到何时终止，也称为递归出口；递归模式，即大问题是如何分解为小问题的，也称为递归体
阶乘函数的自变量n的定义域是非负整数。递归式的第一式给出了这个函数的一个初始值，是递归的边界条件。递归式的第二式使用较小的自变量的函数值来表示较大自变量的函数值的方式来定义n的阶乘，是递归体。
-
递归算法的时间复杂度分析方法：将递归式中等式右边的项根据递归式进行替换，称为展开、展开后的项被再次展开，如此下去，直到得到一个求和表达式，得到结果。
10.2 算法设计
10.2.1 分治法
分治法的思想是讲一个难以直接解决的大问题分解成一些小规模的相同问题，以便各个击破，分而治之。如果规模为n的问题可分解成k个子问题1<=k<=n，这鞋子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。
一般来说，分支算法在每一层递归上都有3个步骤
-
分解：将原问题分解成一系列子问题
-
求解：递归地求解各子问题。若子问题足够小则直接求解
-
合并：将子问题的解合并成原问题的解
凡是涉及到分组解决的都是分治法，例如归并排序算法完全依照上述分治算法的3个步骤进行的
10.2.2 动态规划法
动态规划算法和分治法类似，其基本思想也是将带求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间
然而，不同字问题的数目尝尝只有多项式量级。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常有以及步骤：
-
找出最优解的性质，并刻画其结构特征
-
递归的定义最优解的值
-
以自底向上的方式计算出最优值
-
根据计算最优值时得到的信息，构造一个最优解。
对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解。
1.最优子结构：如果一个问题的最优解中包含了其子问题的的最优，也就是说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略也可能也是适用的
2.重叠子问题：指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断的调用同一个问题时，就说该问题包含重叠子问题
典型应用：0-1背包问题
当有n个物品，第i物品的价值为vi，重量为wi，其中vi和wi均为非负数，背包的容量为w，w为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大
1）刻画0-1背包问题的最优解的结构
可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即xn=1，那么其余x1,x2,...,xn-1一定构成子问题1,2,...,n-1在容量为W-wn时的最优解。如果这个最优解不包含物品n，即xn=0，那么其余x1,x2,...,xn-1一定构成子问题1,2,...,n-1在容量为W时的最优解
2）递归定义最优解的值
根据上述分析的最优解的结构递归地定义问题最优解。设c[i,w]表示背包容量为w时i个物品导致的最优解的价值，得到下式。显然，问题要求c[n,W]
| 0 | I=0或W=0 | |
|---|---|---|
| c[i,w]= | c[i-1,w] | Wi>W |
| max{c[i-1,w-wi]+vi,c[i-1,w]} | i>0且Wi<=W |
10.2.3 贪心法
和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换而言之，贪心法并不是从整体最优考虑，他所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。
贪心法问题一般具有两个重要的性质：
1.最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质
2.贪心选择性质：指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。
贪心法的典型应用：背包问题
背包问题的定义与0-1背包问题类似，但是每个物品可以部分装入背包，即在0-1背包问题中，xi=0或者xi=1；而在背包问题中，0<=xi<=1
为了得到最优解，必须把背包放满。现用贪心策略求解，首先要选出度量的标准。
-
按最大价值先放背包的原则
-
按最小重量先放背包的原则
-
按最大单位重量价值先放背包的原则
10.2.4 回溯法
有"通用的解题法"之称，可以系统的搜索一个问题的所有解或任一解。在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。搜索至任一节点时，总是先判断该节点是否肯定不包含问题的解，如果不包含，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。
可以理解为先进行深度优先搜索，一直向下探测，当此路不通时，返回上一层探索另外的分支，重复此步骤，这就是回溯。意为先一直探测，当不成功再返回上一层
-
一般用于解决迷宫类问题
10.2.5 分支限界法
在分支限界法中，每一个活节点只有一次机会成为拓展节点。活节点一旦称为拓展节点，就一次性产生其所有儿子节点。在这些儿子节点中，导致不可行解或导致非最优解的儿子节点被舍弃，其余儿子节点被加入活节点表中。此后，从活节点表中取出下一节点成为当前拓展节点，并重复上述节点扩展过程。这个过程一直持续到找到所需的解或活节点表为空位置
与回溯法的区别：
1.求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出某一目标函数值达到极大或极小的解，即在某种意义下的最优解
2.以广度优先或以最小耗费(最大收益)优先的方式搜索解空间树
从活节点表中选择下一个扩展节点的类型：
队列式(FIFO)分支限界法：按照队列先进先出的原则选择下一个节点为扩展节点
优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
10.2.6 概率算法
在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以最小的概率出现错误，并依次为代价，获得算法运行时间的大幅度减少(降低算法复杂度)
基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果
如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解
四类概率算法：数值概率算法(数值问题的求解)、蒙特卡洛算法(求问题的精确解)、拉斯维加斯算法(不会得到不正确的解)、舍伍德算法(总能求得问题的一个正确解)
概率算法的特征：
1.概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列
2.概率算法在运行过程中，包括一处或多出随机选择，根据随机值来决定算法的运行路径
3.概率算法的结果不能保证一定是正确的，但能限制其出错概率
4.概率算法在不同的运行过程中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同
10.2.7 近似算法
解决南街问题的一种有效策略，其基本思想是放弃求最优解，而用近似最优解代替最优解，以换区算法设计上的简化和时间复杂度的降低。
虽然它可能找不到一个最优解，但它总会给带求解的问题提供一个解
为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别或者比例的一个界限，它保证任意一个实例的近似最优解和最优解之间的相差程度。显然，这个差别越小，近似算法越具有实用性。
衡量近似算法的两个标准：
1.算法的时间复杂度：近似算法的时间复杂度必须是多项式阶的，这是近似算法的基本目标
2.解的近似程度：近似最优解的近似程度也是近似算法的重要目标。近似程度与近似算法本身、问题规模，乃至不同的输入实例有关。
10.3 其他算法
10.3.1 数据挖掘算法
频繁模式和关联规则挖掘
挖掘海量数据中的频繁模式和关联规则可以有效的指导企业发现交叉销售机会、进行决策分析和商务管理等（沃尔玛-啤酒尿布故事）
首先要求挖掘数据集中的频繁模式，然后由频繁模式产生关联规则
关联规则挖掘算法：类Apriori算法、基于频繁模式增长的方法如FP-growthh,使用垂直数据格式的算法，如ECLAT
聚类
是一种无监督学习过程。根据数据的特征，将近似的数据对象归为一类，不相似的数据对象归到不同的类中。物以类聚、人以群分
典型算法：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于统计模型的方法
10.3.2 智能优化算法
优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。
人工神经网络ANN：一个以有向图为拓扑结构的动态系统，通过对连续或断续的输入作状态响应而进行信息处理。从信息处理角度对人脑神经元网络进行抽象，建立某种简单模型，按不同的连接方式组成不同的网络。
遗传算法：源于模拟达尔文的"优胜劣汰、适者生存"的进化论和孟德尔·摩根的遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构，其本意实在人工适应系统中设计一种基于自然的演化机制
模拟退火算法SA：求解全局优化算法。基本思想来源于物理退火过程，包括三个阶段：加温阶段、等温阶段、冷却阶段。将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随文提升高变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小
禁忌搜索算法TS：模拟人类智力过程的一种全局搜索算法，是对局部邻域搜索的一种拓展。从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索采用了一种灵活的"记忆"技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立
蚁群算法
是一种用来寻找优化路径的概率型算法
单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。而又经进一步研究发现，蚂蚁会在经过的路径上释放一种称之为"信息素"的物质，蚁群内的蚂蚁对"信息素"具有感知能力，它们会沿着"信息素"浓度较高路径行走，而每只路过的蚂蚁都会在路上留下"信息素"，这就形成了一种类似于正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。
用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁的个数也愈来愈多。最终，整个蚁群会在正反馈的作用下集中到最佳路径上，此时对应的便是待优化问题的最优解
粒子群优化算法PSO：
一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物有多远。那么找到食物的最优策略，最简单有效的就是搜寻目前离食物最近的鸟的周围区域
POS从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为"粒子"。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索
