常见的算法思想

本文主要是介绍常见的算法思想，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

分而治之

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题小到可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)，大数据中的MR，现实中如汉诺塔游戏。

分治法对问题有一定的要求：

• 该问题缩小到一定程度后，就可以轻松解决
• 问题具有可拆解性，不是一团无法拆分的乱麻
• 拆解后的答案具有可合并性。能组装成最终结果
• 拆解的子问题要相互独立，互相之间不存在或者很少有依赖关系

动态规划

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

与分治法最大的不同在于，分治法的思想是并发，动态规划的思想是分步。该方法经分解后得到的子问题往往不是互相独立的，其下一个子阶段的求解往往是建立在上一个子阶段的解的基础上。动态规划算法同样有一定的适用性场景要求：

• 最优化解：拆解后的子阶段具备最优化解，且该最优化解与追踪答案方向一致
• 流程向前，无后效性：上一阶段的解决方案一旦确定，状态就确定，只会影响下一步，而不会反向影响
• 阶段关联：上下阶段不是独立的，上一阶段会对下一阶段的行动提供决策性指导。这不是必须的，但是如果具备该特征，动态规划算法的意义才能更大的得到体现

贪心算法

同样对问题要求作出拆解，但是每一步，以当前局部为目标，求得该局部的最优解。那么最终问题解决时，得到完整的最优解。也就是说，在对问题求解时，总是做出在当前看来是最好的选择，而不去从整体最优上加以考虑。从这一角度来讲，该算法具有一定的场景局限性。

• 要求问题可拆解，并且拆解后每一步的状态无后效性（与动态规划算法类似）
• 要求问题每一步的局部最优，与整体最优解方向一致。至少会导向正确的主方向。

回溯算法

回溯算法实际上是一个类似枚举的搜索尝试过程，在每一步的问题下，列举可能的解决方式。选择某个方案往深度探究，寻找问题的解，当发现已不满足求解条件，或深度达到一定数量时，就返回，尝试别的路径。回溯法一般适用于比较复杂的，规模较大的问题。有“通用解题法”之称。

• 问题的解决方案具备可列举性，数量有限
• 界定回溯点的深度。达到一定程度后，折返

分支限界

与回溯法类似，也是一种在空间上枚举寻找最优解的方式。但是回溯法策略为深度优先。分支法为广度优先。分支法一般找到所有相邻结点，先采取淘汰策略，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从存活表中选择一个结点作为下一个操作对象。

这篇关于常见的算法思想的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！