一.分治法
分治法思想：将原问题分成n个规模较小的而结构与原问题相似的子问题，递归地解这些问题，然后合并其结果就得到原问题的解。
- 分解：原问题分为若干个子问题，这些子问题是原问题的规模较小的实例。
- 解决：递归地求解各个子问题。若子问题足够小，则直接求解。
- 合并：将子问题的解合并成原问题的解。
递归算法通常包含：
①递归地调用该算法本身并传入较小的参数
②中止条件（处理基本情况，基本情况不可以有任何递归周期）
二.动态规划法
动态规划思想：动态规划的思想实质是分治思想和解决冗余。
与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，经分解的子问题往往不是互相独立的，若用分治法来解，有些共同部分（子问题或者子子问题）被重复计算了很多次。
- 找出最优解的性质，并刻画其结构特征
- 递归地定义最优值
- 以以自底向上的方式计算出最优值
- 根据计算最优值时记录得信息，构造最优解
三.贪心算法
贪心算法思想：从问题的某一个初始解出发，通过一系列的贪心选择——当前状态下的局部最优选择，逐步逼近给定的目标，尽可能地求的最好的解。基于贪心选择准则，每次得到局部最优的选择，希望利用局部最优得到全局最优解。
因此，找到正确的贪心选择准则是设计贪心算法的关键，并且不同的贪心选择准则可以得到不同的结果。
一般有以下几种贪心选择准则：
- 最大价值优先
- 最小体积优先
- 最大体积优先
- 最大单位体积优先
贪心算法不能对所有问题都得到全局最优解，但对许多问题是可行的，如：单源最短路径问题，最小生成树问题等。通常是以自顶向下的方式进行，每次选择后将问题转化为规模更小的子问题。
四.回溯法
回溯法思想：搜索树中某个特定目标节点。从起点出发，以深度优先的法则依次遍历备选解，若备选解不是有效解则舍弃该解并返回上次出现分支的位置继续遍历。
- 给定问题有一个约束集合以及目标函数
- 可以用状态空间树来表示解空间（①状态空间树的根代表0个选择的状态②深度为1的节点代表第一次选择后的状态......状态空间树上一条从根到叶子的路径代表备选解）
- 逐步构建部分备选解
- 如果备选解不能成为一个有效的解，则立即放弃该分支
- 通常用排除法（剪枝），减少搜索空间
解空间：问题所有解的总和，包括错误解。
可行解：满足约束条件的解，解空间的一个子集。
最优解：使目标函数取极值（极大或极小）的可行解。
五.分支限界法
分支限界法思想：由于回溯法在求最优解的过程中效率不是很高，因此我们可以选择先访问那些有可能得出最优解的节点。分支限界法在访问一个节点时，会生成这个节点所有的子节点，也就是生成所有分支，而界表示通过此节点生成的解所能到达的一个下限或者上限，也就是这些节点。
分支限界的基本流程如下：
- 从根节点出发，生成根节点的所有子节点，并生成这些节点的界，这些子节点组成了活跃节点
- 在所有活跃节点中，选取一个界最小（或最大）的节点（此节点访问完毕后不再是活跃节点），生成此节点所有的子节点及其界，这些子节点也成为活跃节点
- 重复以上步骤，直到没有活跃节点
标签：递归,思想,问题,算法,最优,数据结构,节点,贪心 From： https://blog.csdn.net/m0_62823517/article/details/142415720