常见的算法设计策略:
1、分治
分治法的设计思想是,将一个难以直接解决的大问题,分割成k个规模较小的子问题,这些子问题相互独立,且与原问题相同,然后各个击破,分而治之。
分治法常常与递归结合使用:通过反复应用分治,可以使子问题与原问题类型一致而规模不断缩小,最终使子问题缩小到很容易求出其解,由此自然导致递归算法。
2、动态规划
动态规划法与分治法类似,其基本思想也是将原问题分解成若干个子问题。与分治法不同的是,其分解出的子问题往往不是相互独立的。这种情况下若用分治法会对一些子问题进行多次求解,这显然是不必要的。动态规划法在求解过程中把所有已解决的子问题的答案保存起来,从而避免对子问题重复求解。
动态规划常用于解决最优化问题。对一个最优化问题可否应用动态规划法,取决于该问题是否具有如下两个性质:
最优子结构性质:
当问题的最优解包含其子问题的最优解时,称该问题具有最优子结构性质。
子问题重叠性质:
子问题重叠性质是指由原问题分解出的子问题不是相互独立的,存在重叠现象。
3、贪心
当一个问题具有最优子结构性质时,可用动态规划法求解。但有时会有比动态规划更简单更直接效率更高的算法——贪心法。贪心法总是做出在当前看来最好的选择,也就是说贪心法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。
4、回溯
回溯法是对问题的解空间树进行深度优先搜索 ,但是在对每个节点进行DFS之前,要先判断该节点是否有可能包含问题的解。如果肯定不包含,则跳过对以该节点为根的子树的搜索,逐层向其祖先节点回溯。如果有可能包含,则进入该子树,进行DFS。
5、分支限界
分支限界法的搜索策略是,在当前节点处,先生成其所有的子节点(分支),并为每个满足约束条件的子节点计算一个函数值(限界),再将满足约束条件的子节点全部加入解空间树的活结点优先队列。然后再从当前的活节点优先队列中选择优先级最大的节点(节点的优先级由其限界函数的值来确定) 作为新的当前节点。重复这一过程,直到到达一个叶节点为止。所到达的叶节点就是最优解。
以上是常用的算法设计策略有哪些的详细内容。更多信息请关注PHP中文网其他相关文章!