九大经典算法思想及其典型应用

欢迎大家来到IT世界,在知识的湖畔探索吧!

算法（Algorithm）是为了解决一个特定的问题而精心设计的一套数学模型以及在这套数学模型上的一系列操作步骤，这些操作步骤是将描述的输入数据逐步处理、转换，并最后得到一个确定的结果。当然，准确性是基本前提，时间和空间效率是衡量一个算法优劣的重要评估标准。算法通常在函数中使用控制结构来实现。

1 算法分类

算法是一个比较大的概念范畴，为便于理解，可以从算法思想，典型应用及与数据结构的关系，将算法分为三类：

1.1 经典算法思想

一般来说，算法设计没有什么固定的方法可循。但是通过大量的实践，人们也总结出算法某些共性的规律，包括穷举法(Enumeration)、递推法(Recurrence)、递归法、分治法(Divide and Conquer)、贪心法、回溯法(Backtracking)、动态规划法等。

1.2 经典算法思想在典型问题上的应用

如排序、查找（检索）等算法。尽管计算学科的整个发展可以很短，但前人们还是留下了很多非常经典的算法，仅就排序而言，就可以数出一大堆，如冒泡排序法、快速排序法、选择排序法、插入排序法、基数排序法等。

1.3 在数据结构上应用的算法

包括增、查、删、改、遍历、图的最路径、最小生成树、树的遍历方法，线性表的二分查找，以及数据类型的运算符，类类型的操作符重载。

有些算法充满着智慧，如Dijistra最短路径、Huffman树、蒙特卡洛方法、快速排序、堆排序、红黑树、A+树、字符串匹配的KMP算法等。

2 从算法中的分治思想来体现各类算法思想中的细微区别

复杂的问题可以分而治之。对于复杂的问题，通常都需要应用分治的思想，同时，很多算法中也有分治思想的体现。分治法所能解决的问题一般具有以下几个特征：

① 该问题的规模缩小到一定的程度就可以容易地解决；

② 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质

③ 利用该问题分解出的子问题的解可以合并为该问题的解；

④ 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。

递归的子问题之间是同类、纵向的关系，而枚举是横向的关系。

如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。

特征④涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。严格地说，用动态规划的问题一般都有前后重叠的，需要用前一阶段的结果局部贪心推出下一个阶段结果。贪心算法一般要得到最优解只能各个阶段没有重叠，以局部最优构造全局最优。

3 了解算法的8个要点

3.1 算法是程序设计的“熟语”（常见短语）,有大算法与有小算法；

3.2 算法中解决问题的步骤是明确且有限的；

3.3 计算机不靠直觉而是机械地解决问题（就是简单傻瓜式地一步一步做）；

3.4 了解并应用典型算法；

3.5 利用计算机的处理速度；无论是多么冗长繁琐的步骤，只要明确并且机械就是优秀的算法；

3.6 使用编程技巧提升程序执行速度；也就是说解决问题的方法是可以优化的，就像做事有方法，效率就会高一样，算法也是可以优化的；

3.7 找出数字间的规律；因为在计算机中所有的信息都可以用数字表示，因此构造算法，就可以利用到存在于数字间的规律。规律+逻辑；

3.8 先在纸上考虑算法；也就是先在纸上把步骤用文字或图形表示出来，用简单的数字先做验证；

4 九种基本算法思想简述

4.1枚举法Enumeration method

枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法。

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下。

① 确定枚举对象、枚举范围和判定条件。

② 逐一列举可能的解，验证每个解是否是问题的解。

枚举算法一般按照如下3 个步骤进行。

① 题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。

② 判断是否是真正解的方法。

③ 使可能解的范围降至最小，以便提高解决问题的效率。

4.2迭代法Iteration method

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。与迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似。

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

在使用迭代算法解决问题时，需要做好如下3 个方面的工作。

（1）确定迭代变量

在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。

（2）建立迭代关系式

迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。

（3）对迭代过程进行控制

在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：

① 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；

② 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。

4.3递推法Recurrence method

与枚举算法思想相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案。

递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推算法。

① 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。

② 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

4.4递归法Recursion method

因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。

在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3 个特点。

① 递归过程一般通过函数或子过程来实现。

② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。

③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

在使用递归算法时，应该注意如下4 点。

① 递归是在过程或函数中调用自身的过程。

② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。

③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。

④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

4.5分治法Divide and conquer

分治算法采取各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。

在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。

使用分治算法解题的一般步骤如下。

① 分解，将要解决的问题划分成若干个规模较小的同类问题。

② 求解，当子问题划分得足够小时，用较简单的方法解决。

③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

4.6动态规划Dynamic programming

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

(1) 基本概念

每次决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

(2) 基本思想

与分治法类似，也是将待求解的问题分解为若干个子问题，按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是初始问题的解。

与分治法最大的差别：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

(3) 适用的情况

① 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

② 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响，也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

④ 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

(4) 解题步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

① 划分阶段：按照问题的时间特征，把问题分为若干个阶段，在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

② 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来，当然，状态的选择要满足无后效性。

③确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

④ 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程。实际应用中可以按以下几个简化的步骤进行设计：

① 分析最优解的性质，并刻画其结构特征。

② 递归的定义最优解。

③ 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。

④ 根据计算最优值时得到的信息，构造问题的最优解。

(5) 算法实现的说明

动态规划的主要难点在于上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：

① 问题的阶段

② 每个阶段的状态

③ 从前一个阶段转化到后一个阶段之间的递推关系。

递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

4.7贪心法Greedy

贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。

贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3 个问题。

① 不能保证最后的解是最优的。

② 不能用来求最大或最小解问题。

③ 只能求满足某些约束条件的可行解的范围。

贪心算法的基本思路如下。

① 建立数学模型来描述问题。

② 把求解的问题分成若干个子问题。

③ 对每一子问题求解，得到子问题的局部最优解。

④ 把子问题的局部最优解合并成原来解问题的一个解。

实现该算法的基本过程如下。

（1）从问题的某一初始解出发。

（2）while能向给定总目标前进一步。

（3）求出可行解的一个解元素。

（4）由所有解元素组合成问题的一个可行解。

4.8回溯法Recursive search

回溯法也叫试探法，试探法的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

使用试探算法解题的基本步骤如下所示。

① 针对所给问题，定义问题的解空间。

② 确定易于搜索的解空间结构。

③ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

试探法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

4.9分支限界法Branch and Bound Method

分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法，但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

由于求解目标不同，导致分支限界法与回溯法在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解。

分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解。

－End－