分治法

---

(1)基本思想

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

(2)特征

分治法能解决的问题具有的特征

1.该问题的规模缩小到一定的程度就可以容易的解决。

2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3.分解出的子问题的解可以合并成该问题的解

4.该问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问

(3)解决问题的基本步骤

1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。

2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。

3.合并：将各个子问题的解合并为原问题的解。

贪心法

---

(1)基本思想

贪心算法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。一般来说，这种贪心原则在各种算法模式中都会体现，这里单独作为一种方法来说明，是因为贪婪法对于特定的问题是非常有效的方法。

(2)适用的问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

​ 实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

(3)解决问题的基本步骤

1.建立数学模型来描述问题。

​ 2.把求解的问题分成若干个子问题。

​ 3.对每一子问题求解，得到子问题的局部最优解。

​ 4.把子问题的解局部最优解合成原来解问题的一个解。

动态规划算法

---

(1)思想

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

(2)重要性质

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简 单地查看一下结果，从而获得较高的解题效率。

(3)基本步骤

1 、分析问题的最优解，找出最优解的性质，并刻画其结构特征；

2 、递归地定义最优值，即构造最优解值的递归表达式；

3 、采用自底向上的方式计算问题的最优值；

4 、根据计算最优值时得到的信息，构造最优解。

回溯法

---

(1)基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

      若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

      而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

(2)适用条件

算法思想、适用问题及求解步骤

多米洛性质：  前 k+1 个向量满足约束条件，那么 ，前 k 个向量必然满足约束条件。

(3)基本步骤

1.针对所给问题，确定问题的解空间：

            首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

2.确定结点的扩展搜索规则

3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

分支限界法

---

(1)基本思想

分支限界法常以广度优先或以最小耗费有限的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法和回溯法的主要区别在于它们对当前扩展节点所采用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展节点。活结点一旦成为扩展节点，就一次性产生其所有儿子节点。在这些儿子节点中，导致不可行解或导致非最优解的儿子节点被舍弃，其余儿子节点被加入活结点表中。此后，从活结点表中取下一节点为当前扩展节点。并重复上述节点扩展过程。这个过程移至持续到找到所需的解或活结点表为空为止。

(另一种说法是：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题的算法。但分支限界法的求解目标是找出满足约束条件的一个最优解。搜索策略是广度优先，既在扩展结点点，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。在每一个活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点队列中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上最优解的分枝推进，以便尽快找到一个最优解。 )

(2)常用的选择活结点的方法

1.先进先出(FIFO)

2.后进先出(LIFO)

3.优先队列式(LC)

(3)基本步骤

1.定义解空间 确定解空间包括解的组织形式和显约束(范围限定)

2.确定解空间的组织结构 通常用解空间树形象的表达(只是辅助理解并不是真的树)

3.搜索解空间 按照广度优先搜索或以最小耗费(最大收益)优先的方式搜索解空间，根据限制条件，搜索问题的解，即在搜索过程中用剪枝函数避免无效搜索