首页  >  文章  >  常用的算法设计策略有哪些

常用的算法设计策略有哪些

尚
原创
2020-03-18 15:16:1212700浏览

常用的算法设计策略有哪些

常见的算法设计策略:

1、分治

分治法的设计思想是,将一个难以直接解决的大问题,分割成k个规模较小的子问题,这些子问题相互独立,且与原问题相同,然后各个击破,分而治之。

分治法常常与递归结合使用:通过反复应用分治,可以使子问题与原问题类型一致而规模不断缩小,最终使子问题缩小到很容易求出其解,由此自然导致递归算法。

2、动态规划

动态规划法与分治法类似,其基本思想也是将原问题分解成若干个子问题。与分治法不同的是,其分解出的子问题往往不是相互独立的。这种情况下若用分治法会对一些子问题进行多次求解,这显然是不必要的。动态规划法在求解过程中把所有已解决的子问题的答案保存起来,从而避免对子问题重复求解。

动态规划常用于解决最优化问题。对一个最优化问题可否应用动态规划法,取决于该问题是否具有如下两个性质:

最优子结构性质:

当问题的最优解包含其子问题的最优解时,称该问题具有最优子结构性质。

子问题重叠性质:

子问题重叠性质是指由原问题分解出的子问题不是相互独立的,存在重叠现象。

3、贪心

当一个问题具有最优子结构性质时,可用动态规划法求解。但有时会有比动态规划更简单更直接效率更高的算法——贪心法。贪心法总是做出在当前看来最好的选择,也就是说贪心法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。

4、回溯

回溯法是对问题的解空间树进行深度优先搜索 ,但是在对每个节点进行DFS之前,要先判断该节点是否有可能包含问题的解。如果肯定不包含,则跳过对以该节点为根的子树的搜索,逐层向其祖先节点回溯。如果有可能包含,则进入该子树,进行DFS。  

5、分支限界

分支限界法的搜索策略是,在当前节点处,先生成其所有的子节点(分支),并为每个满足约束条件的子节点计算一个函数值(限界),再将满足约束条件的子节点全部加入解空间树的活结点优先队列。然后再从当前的活节点优先队列中选择优先级最大的节点(节点的优先级由其限界函数的值来确定) 作为新的当前节点。重复这一过程,直到到达一个叶节点为止。所到达的叶节点就是最优解。                                                           

以上是常用的算法设计策略有哪些的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn