算法设计与分析C

算法5_分治法

分治法——将一个复杂的问题分解成若干个规模较小、相互独立，但类型相同的子问题求解；然后再将各子问题的解组合成原始问题的一个完整答案，这样的问题求解策略就叫分治法。

分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题；
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
由分治法产生的子问题往往是原问题的较小模式。
直接或间接地调用自身的算法称为：递归算法。用函数自身给出定义的函数称为：递归函数。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

算法6_贪心法

• 可行解
  ——问题给定某些约束条件，满足约束条件的问题解，即称为可行解。
• 最优解
  ——问题给出目标函数衡量可行解的好坏，使目标函数取最大（或最小）值的可行解称为最优解。

1.最优子结构性质：

一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

2.贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

算法7_动态规划法

（1）子问题重叠性质
（递归算法求解问题时）每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题重叠性质。

动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格（通常用二维数组）中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式级时间，从而获得较高的解题效率。

（2）最优子结构性质——用动态规划法求解的前提。
当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

一个问题的活动过程可以分为若干个阶段，每个阶段可包含一个或多个状态，从初始阶段的初始状态出发做出每个阶段的决策，形成一个决策序列。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

用动态规划算法求解问题的步骤：

1、找出最优解的性质，并刻划其结构特征；

2、递归地定义最优解值；

3、自底向上求最优解值；

4、根据计算最优解值时得到的信息构造一个最优解（此步只在要求得到最优解时才需要做） 。

动态规划法是一种求解最优化问题的重要算法策略。

利用最优子结构性质及所获得的递推关系式（较小子问题最优解与较大子问题最优解之间存在的数值关系）去求取最优解，可以使计算量较之穷举法急剧减少。

共同点：
将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。
不同点：
1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。

2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。

备忘录方法与动态规划法比较

1、与动态规划法的共同点：用一个表格来保存已求解的子问题的答案，使下次需要解此子问题时，只简单地查看答案，不重新计算。

2、与动态规划法的区别：备忘录的递归方式是自顶向下，而动态规划法的递归方式是自底向上。

如何选择使用动态规划法或备忘录法？

★当一个问题的所有子问题都至少要解一次时，选用动态规划法较好，此时没有任何多余的计算，还可利用规则的表格存取方式，减少时间和空间需求。

★当一个问题只有部分子问题需要求解时，选用备忘录法较好，它只解那些确实需要求解的子问题。

备忘录方法与递归方法比较

1、与递归方法的共同点：递归方式均为自顶向下

2、与递归方法的区别：备忘录方法用一个表格来保存已求解的子问题的答案，使下次需要解此子问题时，只简单地查看答案，不重新计算；而递归方法在每次遇到子问题都要重新计算。

共同点：
都是求解最优化问题；都具有最优子结构性质。
不同点：
1、求解方式不同：
动态规划法：自底向上；
贪心法：自顶向下。以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

2、对子问题的依赖不同：
动态规划法：依赖于各子问题的解。只有在解出相关子问题后,才能作出选择；应使各子问题最优，才能保证整体最优；
贪心法：不依赖于子问题的解。仅在当前状态下作出最好选择，即局部最优选择。

算法8_回溯法

回溯法是比贪心法和动态规划法更一般的方法。
解为n-元组(x0,x1,…,xn-1)形式。
通过搜索状态空间树来求问题的可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。
使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数。
通常情况下，回溯法是为了找出满足约束条件的所有可行解。

• 显式约束：规定每个xi取值的约束条件。
  （显式约束规定了问题的候选解集——解空间）
• 隐式约束：给出了判定一个候选解是否为可行解的条件。为满足问题的解而对不同分量之间施加的约束。
• 目标函数（代价函数）：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的最优解。
  状态空间树：描述问题解空间的树形结构。

树中每个结点称为一个问题状态；
若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态；
若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态；
如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优值的最优答案结点。

回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。
事实上，状态空间树并不需要事先生成，而只需在求解的过程中，随着搜索算法的进展，逐个生成状态空间树的问题状态结点。

常用的剪枝函数：
用约束函数剪去已知不含答案状态（可行解）的子树；
用限界函数剪去得不到最优答案结点（最优解）的子树。

蒙特卡洛估计

用蒙特卡罗（Monte Carlo）方法估计回溯法处理实例时，实际生成的结点数：

在状态空间树中,从根开始随机选择一条路径(x0,x1,…,xn-1);
假定搜索树中这条随机选出的路径上，代表部分向量(x0,x1,…,xk-1)的结点X处不受限制的孩子数目,和其他路径上与X同层的的结点不受限制的孩子数目一样，都是mk;
则可以估计整个状态空间树上实际生成的结点数为: m=1+m0+m0m1+m0m1m2+......

算法9_分枝限界法

采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为——分枝限界法。
分枝限界法的基本做法是：
以广度优先的方式搜索问题的状态空间树。每一个活结点只有一次机会成为扩展结点。
按照广度优先的原则，活结点一旦成为扩展结点（E结点）R后，就依次生成它的所有孩子结点。在这些孩子结点中，导致不可行解或导致非最优解的孩子结点被舍弃，其余孩子结点被一一加入活结点表中。
此后，R自身成为死结点，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。

一、分枝限界法与回溯法的共同点
都是在问题的状态空间树上搜索问题解的算法,都通过活结点表实现。都用约束函数剪去不含答案结点的分枝,用限界函数剪去不含最优解的分枝.
二、分枝限界法与回溯法的区别
（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有可行解；而分枝限界法的求解目标则是找出满足约束条件的一个可行解，或某种意义下的最优解。

（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分枝限界法则以广度优先的方式搜索解空间树。

（3）对当前扩展结点的扩展方式不同：回溯法中的每个活结点可能多次成为当前扩展结点，纵深方向扩展其一个儿子，然后再回溯后扩展其他儿子；而分枝限界法中每一个活结点只有一次机会成为扩展结点，一次产生所有孩子结点，自身成为死结点，之后无需再返回该结点处。