1. 算法概述
- 算法是指满足下列性质的指令序列
- 输 入：有零个或多个外部量作为算法的输入。
- 输 出：算法产生至少一个量作为输出。
- 确定性：组成算法的每条指令清晰、无歧义。
- 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
- 输 入：有零个或多个外部量作为算法的输入。
2. 递归与分治策略
- 分治总体思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
- 直接或间接地调用自身的算法称为递归算法。
- 用函数自身给出定义的函数称为递归函数。
- 分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
-
可解问题
- 二分搜索
- 大整数的乘法
- trassen矩阵乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点问题
- 循环赛日程表
3. 动态规划
-
动态规划的基本思想和分治相似，也是将待求解问题分解成若干个字问题，先求解子问题，然后从这些子问题的解得到原问题的解。
-
它与分治的区别是，动态规划针对的是分解子问题不是互相独立的，即子问题会发生重叠。所以，这类问题如果采用分治法来解决时，分解的子问题数目会过多，最后导致解决原问题需要耗费指数时间。
-
它最重要的两个特性：
- 最优子结构性质：当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
- 重叠子问题：若使用递归算法自顶向下解问题时，其产生的很多子问题是重复的，不总是新的。也就是说很多子问题会被反复计算多次，那么就称这是子问题重叠。针对这种情况，动态规划的优势就来了。只需要通过一个表保存这些子问题的解，下次求解时，若碰到重复的子问题，只需要查表获得子问题的解，而不需要重复计算。这也是为什么动态规划一般自底向上解决问题。
-
递归算法为自顶向下，而动态规划问题为自底向上。
-
动态规划变形＝》备忘录方法
备忘录方法是自顶向下的，它为每个解过的子问题建立了备忘录以备需要时查看，避免相同子问题的重复求解。（每一次递归完，对这次递归过程中解决的问题纪录，为后面计算减轻负担）
-
当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录好。有部分子问题可不必求解时，用备忘录法比较有效。
-
解题步骤
- 找出最优解的性质，并刻划其结构特征。 . 递归地定义最优值。 . 以自底向上的方式计算出最优值。
- 根据计算最优值时得到的信息，构造最优解。
-
可解问题：
- 矩阵连乘问题
- 最长公共子序列
- 最大子段和
- 凸多边形最优三角剖分
- 多边形游戏
- 图像压缩
- 电路布线
- 流水作业调度
- 0-1背包问题
- 最优二叉搜索树
4. 贪心算法
- 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
- 用贪心算法来解，需要满足两个性质：
- 贪心选择性质：指所求问题的最优解可以通过一系列局部最优的选择来得到（自顶向下选择）
- 最优子结构性质:当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质
- 贪心算法与动态规划的区别
- 都具有最优子结构性质
- 但另一个性质，一个为贪心选择，一个是子问题重叠。这也是为什么0-1背包问题只能用动态规划来解的重要原因。
-
可解问题
- 活动安排问题
- 最优装载问题
- 哈夫曼编码
- 单源最短路径
- 最小生成树
- 多机调度问题
5. 回溯法
-
针对什么问题： 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。
-
基本原理 回溯法主要采用搜索，深度优先搜索算法。从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
-
一些名词
- 扩展结点：一个正在产生儿子的节点称为扩展结点
- 活结点：一个自身已生成但其儿子还没有全部生成的节点称作活结点
- 死结点：一个所有儿子已经产生的结点称为死结点
-
深度优先问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
-
广度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
-
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法
- 基本过程：
- 针对所给问题，定义问题的解空间；
- 确定易于搜索的解空间结构；
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
-
一般有两种回溯方式
-
使用递归方式
void backtrack (int t){ if (t>n) output(x); else for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) backtrack(t+1); } } -
使用迭代方式（采用树的非递归深度优先遍历算法）
void iterativeBacktrack (){ int t=1; while (t>0) { if (f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) { x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++; } } else t--; } }
-
-
解空间构造方式有两种
-
子集树
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。 搜索子集树代码：
void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } -
排列树
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } } -
-
可解问题：
- 装载问题
- 批处理作业调度
- 符号三角形问题
- n后问题
- 0-1背包问题
- 最大团问题
- 图的m着色问题
- 旅行售货员问题
- 圆排列问题
- 电路板排列问题
- 连续邮资问题
6. 分支限界法
-
分支限界法与回溯法的不同
- 搜索模型的不同
- 回溯使用递归栈作为辅助，按既定顺序逐条搜索每一条从树根到叶子的路径。
- 分支限界法使用优先级队列作为辅助，寻找“最优”路径。
- 目标不同：回溯法更为通用，而分支限界法用于寻找最优解
- 时间效率：单就搜索最优解问题
- 回溯法搜索的时间正比于搜索解空间的大小
- 分支限界法的时间敏感于最优解所在位置，当最优解偏树根，则时间相对于搜索整个解空间树非常少。
- 空间效率
- 回溯法的空间消耗与解空间（最大）树高有关
- 分支限界法的空间消耗一般表现出广度优先搜索的特点，与解空间的宽度有关。 一般树高远小于树宽（E.g. 满二叉树：h « 2 ^ h），所以可以认为分支限界法是回溯法的一种空间换时间的技术
- 搜索模型的不同
-
基本思想
- 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
- 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
-
常见的两种分支限界法- 队列式(FIFO)分支限界法
-
按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
-
优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
-
-
可解问题：
- 装载问题
- 布线问题
0-1背包问题- 最大团问题
- 旅行售货员问题
- 电路板排列问题
- 批处理作业调度问题
参考：
- 《计算机算法设计与分析（第四版）》 王晓东
