算法思想
创建:2025-04-19 23:03
更新:2025-04-19 23:03

常见的算法思想有很多,以下详细介绍 10 种:

  1. 分治法:将一个复杂的问题分解成若干个规模较小、相互独立且与原问题形式相同的子问题,然后分别求解这些子问题,最后将子问题的解合并得到原问题的解。例如归并排序算法,它将待排序的数组不断分成两半,分别对左右子数组进行排序,再将排好序的子数组合并成一个有序数组。
  2. 动态规划法:把多阶段决策过程在每一步的决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。动态规划常常用于求解具有最优子结构和重叠子问题的问题,通过保存子问题的解避免重复计算。如斐波那契数列,一般递归求解会有大量重复计算,而使用动态规划可以通过数组记录已经计算过的结果,从而提高效率。
  3. 贪心算法:在对问题求解时,总是做出在当前看来是最好的选择,也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心算法在一些情况下可以得到全局最优解,比如最小生成树的 Prim 算法和 Kruskal 算法,背包问题中的部分背包问题等。
  4. 回溯法:一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。例如在八皇后问题中,需要在 8×8 的棋盘上放置 8 个皇后,使得它们互不攻击,通过回溯法可以依次尝试在每一行放置皇后,当发现当前放置方式导致冲突时,就回溯到上一行重新选择位置。
  5. 枚举法:也叫穷举法,是指在一个有穷的可能的解的集合中,枚举出集合中的每一个元素,用题目给定的检验条件来判断该元素是否符合条件,若满足条件,则该元素即为问题的一个解;否则,该元素就不是该问题的解。例如在计算两个整数之间所有素数的问题中,可以通过枚举法遍历这个区间内的每一个数,然后判断每个数是否为素数。
  6. 递归算法:直接或间接地调用自身的算法。递归算法需要有明确的终止条件,否则会导致无限递归。例如计算阶乘的函数 n! = n * (n - 1) * (n - 2) *... * 1,可以用递归实现,factorial(n) = n * factorial(n - 1),当 n = 0n = 1 时终止递归,返回 1
  7. 迭代法:迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法。例如求解方程 x = cos(x) 的根,可以使用迭代法,先给定一个初始值 x0,然后通过 x(n+1) = cos(xn) 不断迭代,直到满足一定的精度要求。
  8. 分支限界法:类似于回溯法,也是一种在问题的解空间树 T 上搜索问题解的算法。分支限界法与回溯法的求解目标不同,回溯法的求解目标是找出 T 中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。例如在解决 0-1 背包问题的最优解时,可以使用分支限界法进行求解。
  9. 概率算法:概率算法允许算法在执行的过程中随机选择下一个计算步骤。在很多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择要省时,因此概率算法可以在很大程度上降低算法的复杂度。例如在一些大规模数据的抽样统计、蒙特卡罗算法求解近似值问题等场景中,概率算法都有广泛的应用。
  10. 模拟退火算法:模拟退火算法来源于固体退火原理,将固体加热至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。在求解优化问题时,模拟退火算法从一个初始解出发,通过迭代搜索更好的解,同时以一定的概率接受较差的解,从而避免陷入局部最优解,逐步逼近全局最优解。常用于求解旅行商问题等组合优化问题。