Data Structure 之 算法设计策略
1. 穷举法
基本思想：列举问题的所有可能解，并用约束条件逐一进行判定，找出符合约束条件的解。
穷举法的关键在于问题的可能解的列举和可能解的判别。
例如：凑数问题
2. 递归技术
定义：直接或间接调用自身的过程
递归三要素：
(1)问题形式：返回结果是什么？需要哪些入口参数？
(2)递归规则：问题如何进行分解？
(3)终结条件：什么情况下可以无需套用递归规则直接求解？
3. 分治法
基本思想：待解问题若可以被分解成若干个相互独立的、与原问题同类型的、规模小于原问题的子问题，则可以先求解子问题，再合并子问题的解来得到原问题的解。
4. 动态规划算法
基本思想：动态规划算法常用来求解最优化问题；
其思想是：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。
设计步骤：
5. 贪心算法
基本思想：通过做出当前看来最优的选择（贪心选择），将原问题规模缩小，如此反复，之道得到最终解；
贪心算法并非对所有问题都能得到整体最优解。
基本要素：
例如：迪杰斯特拉（Dijkstra)算法用于求解图上的单源点最短路径。
6. 回溯法
回溯法是一种通用性解法，可以看作是带优化的穷举法。
基本思想：在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子节点，搜索过程中每到达到一个结点时，判断该结点为根的子树是否含有问题的解，如果不含有问题的解，则放弃该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。
在回溯法中，并不是优先构造出整棵状态空间树，再进行搜索，而是在搜索过程中，逐步构造出状态空间树，即边搜索，边构造。
回溯法的使用：
(1).确定问题状态结构；
(2).分析问题状态空间树；
(3).确定深度搜索与回溯规则；
(4).确定解状态判别规则。
7. 限界剪枝法
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
