五大经典算法（分治算法、动态规划法、贪心算法、回溯法、分支限界法）

系统管理员 2021-10-12 20:47 378阅读 0赞

**1.分治算法**

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

它的一般的算法设计模式如下：

Divide-and-Conquer(P)
    
    1. if |P|≤n0
    
    2. then return(ADHOC(P))
    
    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
    
    4. for i←1 to k
    
    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
    
    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
    
    7. return(T)
    
    其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

原文：https://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741370.html

**2.动态规划法**

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

https://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741374.html

**3.贪心算法**

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。  
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。  
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

https://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741375.html

**4.回溯法**

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

https://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741376.html

**5.分支限界法**

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

https://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741378.html