如何设计一个好的算法？

Question

如题所述

Answer 1

算法设计策略如下：

1、分治html

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

2、动态规划spa

动态规划法与分治法相似，其基本思想也是将原问题分解成若干个子问题。这种状况下若用分治法会对一些子问题进行屡次求解，这显然是没必要要的。动态规划法在求解过程当中把全部已解决的子问题的答案保存起来，从而避免对子问题重复求解。

3、贪心

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

4、回溯

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

5、分支限界      

回溯法是对解空间进行深度优先搜索，事实上任何搜索遍整个解空间的算法都可解决问题。因此采用通用图搜索的任何实现做为搜索策略都可解决问题，只要作到穷举便可。除了深度优先搜索以外，咱们还可采用广度优先搜索，而分支限界法则是对解空间进行优先级优先搜索。