常用算法思想

  1. 分治法
    将复杂问题分解成两个或多个子问题,再将子问题又分为两个或多个更小的子问题……直到到达了有解的基本问题。最后,将子问题的解合并成原文题的解。如排序算法、傅里叶变换等。

  2. 动态规划
    每次决策依赖于当前的状态,然后会引起状态的转移。一个决策序列就是在变化的状态中产生出来的,这种多阶段最优化决策解决问题的过程就称之为动态规划。如最短路径等。

  3. 贪心算法
    求解问题时,不考虑全局情况,只贪心于当前的最好的解,所做出的仅仅是某种意义上局部最优解。如Prim算法等。

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

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