简单区分五大算法分析策略（分治、动态规划，阿里面试题java

作者：知新_RL | 2024-04-06 16:27:24

踩

对一个最优化问题可否应用贪心法，取决于该问题是否具有如下两个性质：

1) 贪心选择性质

贪心选择性质是指原问题总有一个整体最优解可通过当前的局部最优选择，即贪心选择来达到。

对于一个具体问题，要确定它是否具有贪心选择性质，通常可考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。由此证明该问题总有一个最优解可通过贪心选择得到，即具有贪心选择性质。

2) 最优子结构性质

这一点与动态规划相同。做出贪心选择后，由于最优子结构性质，原问题简化为规模更小的类似子问题。如果将子问题的最优解和之前所做的贪心选择合并，则可得到原问题的一个最优解。

3、与动态规划法的区别

贪心问题的整体最优解可通过一系列局部的最优选择，即贪心选择来达到。这也是与动态规划的主要区别。
在动态规划中，每步所做出选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。
在贪心法中，仅做出当前状态下的最好选择，即局部最优选择。然后再去解做出这个选择之后产生的相应的子问题。贪心法所做出的贪心选择可以依赖于以往所做过的选择，但绝不依赖于将来所做的选择，也不依赖于子问题的解。
正是由于这种差别，动态规划通常以自底向上的方式解各子问题，而贪心法通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做出一次贪心选择就将所求问题简化为规模更小的子问题。

四、回溯法

===============================================================

1、设计思想

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

2、解题步骤

回溯法通常的解题步骤如下：

(1) 定义问题的解空间。

(2) 将解空间组织成便于进行DFS的结构，通常采用树或图的形式。

(3) 对解空间进行DFS，并在搜索过程中用剪枝函数避免无效搜索。

用回溯法解题时并不需要显式地存储整个解空间，而是在DFS过程中动态地产生问题的解空间。在任何时刻，算法只保存从根节点到当前节点的路径。如果解空间树的高度为h，则回溯法的空间复杂度通常为O(h)

五、分支限界法

=================================================================

1、设计思想

回溯法是对解空间进行深度优先搜索，事实上任何搜索遍整个解空间的算法均可解决问题。所以采用通用图搜索(树可抽象为特殊的图)的任何实现作为搜索策略均可解决问题，只要做到穷举即可。除了深度优先搜索之外，还可采用广度优先搜索，而分支限界法则是对解空间进行广度优先搜索。

2、搜索策略

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

3、层序遍历

树的层序遍历就是广度优先

把树从根节点开始，依次入栈，再弹栈，弹栈时如果当前节点有子节点，再依次入栈，弹出栈的节点，进入队列中；当树的节点，全部通过栈，进入到队列后，队列中的节点就是层序遍历的顺序

六、区别

==============================================================

| 算法策略 | 特征 | 备注 |

| — | — | — |

小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Java工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Java开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。