Java教程

常见的算法思想

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

分而治之

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

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

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

动态规划

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

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

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

贪心算法

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

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

回溯算法

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

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

分支限界

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

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