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

技术  /  管理员 发布于 7年前   464

常见的算法设计策略：

1、分治

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

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

2、动态规划

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

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

最优子结构性质：

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

子问题重叠性质：

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

3、贪心

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

4、回溯

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

5、分支限界

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

以上就是常用的算法设计策略有哪些的详细内容，更多请关注其它相关文章！