算法 | 分支限界法和回溯法的搜索策略&动态规划特性&贪心算法特性

分支限界法的搜索策略：

一次性生成当前扩展节点的所有儿子节点，然后从活节点表中选取要扩展的下一个结点，为了加快搜索速度，会计算节点的函数值，即限界函数。然后从活节点表中选取最有利的结点进行扩展。使搜索朝着最优解的方向进行，以便更快的找到最优解

---

 

回溯法的搜索策略：

在有问题所有可能解的状态空间树上进行深度优先搜索，解为叶子节点，当搜索到一个新节点时，先判断该节点的子树是否含有问题的解，如果没有就放弃搜索该节点，退回到父节点，再进行深搜。在整个回溯过程，不是事先构造好整颗状态空间树，而是逐步构造出整颗状态空间树，边搜索边构造

---

动态规划的特性：

最优子结构:是指问题的最优解可以通过求解子问题的解来得到

重叠子问题：在求解的过程中，有大量的子问题是重复的

无后效性：求解时只和前面阶段有关，和后面的阶段无关 

---

什么是贪心算法

通过当前的最优选择，期待通过局部的最优选择来得到全局的最优解

贪心算法的特性：

最优子结构：问题的最优解包括子问题的解

贪心选择策略 ：通过局部最优选择可以实现得到原问题的最优解

---