常用算法介绍

男娘i 2022-06-15 06:59 223阅读 0赞

**递归法**  
算法定义：递归法是指一个过程或函数在定义或说明中又直接或间接调用自身的一种方法。在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。在递归调用的过程中系统为每一层的返回点、局部量开辟了栈来存储。  
算法原理：递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。  
特征和典型应用场合：  
场合1：数据的定义是按照递归定义的(Fibonacci函数)；  
场合2：问题解法按递归算法实现（回溯）；  
场合3：数据的结构形式是按照递归定义的（树的遍历，图的搜索）

**贪心法**  
算法定义：贪心法是一种不追求最优解，只希望得到较为满意解得方法。贪心法常以当前情况为基础作为最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。  
算法原理：贪心法通常以自顶向下的方式进行，分阶段工作，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更新的子问题。在每一个阶段总是选择认为当前最好的方案，然后从小的方案推广到大的方案的解决办法，他只需要随着过程的进行保持当前最好方案，采用“有好处就先占着”的贪心者的策略。  
特征和典型应用场合：  
这类问题一般具有2个重要的性质：贪心选择性质；最优子结构性质。  
贪心算法经典应用有背包问题、活动安排问题等；

**回溯法**  
算法定义：回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。  
算法原理：回溯法是一种满足某些约束条件的穷举搜索法。它要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。  
特征和典型应用场合：  
回溯是递归的一个特例，但它又别于一般的回溯法，用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。经典的应用有迷宫搜索、N皇后问题、骑士巡游、正则表达式匹配等。

**分治法**  
算法定义：分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解。而原问题的解就是子问题的解得合并。  
算法原理：将一个规模较大的问题分解为若干规模较小的子问题，找出各个子问题的解，然后把各个子问题组合成整个问题的解，在求解子问题的过程中，往往采用同样的策略进行，即继续分解问题，逐个求解，最后合并解。这种不断用同样的策略求解规模较小的子问题，在程序设计语言实现时往往采用递归调用的方式实现。  
特征和典型应用场合：  
问题模式缩小到一定的程度就可以容易地解决，可以分解为若干个规模较小的相同问题，利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出各个子问题是相互独立的。

**动态规划法**  
算法定义：动态规划法用于求解包含重叠子问题的最优化问题的方法。其基本思想是将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划实质是一种以空间换时间的技术，它在实现过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。  
算法原理：动态规划法通常采用以自底向上的方式解各子问题，分多阶段进行决策，其基本思路是：按时空特点将复杂的问题划分为相互联系的若干个阶段，在特定系统行进方向之后，逆着这个方向进行，从终点向始点计算，逐次对每个阶段寻找某种决策，使整个过程达到最优，故又称为逆序决策过程。  
特征和典型应用场合：  
不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略；将各个阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态；最后，考虑采用动态规划的关键在于解决冗余。