1、1/8第 1章 算法概述算法是若干指令的有穷序列，满足性质：(1)输入(2)输出 (3)确定性 (4)有限性。算法复杂性分析主要包括空间复杂性和时间复杂性。算法复杂性分析（1）渐近上界记号 OO(g(n) = f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有：0 f(n) cg(n) （2）渐近下界记号 (g(n) = f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有：0 cg(n) f(n) （3）紧渐近界记号 (g(n) = f(n) | 存在正常数 c1,c2和 n0使得对所有 n n0有： c1g(n) f(n) c2g(n) 定理 1： (g(n) =
2、 O (g(n) (g(n) 最常见的多项式时间算法的渐近时间复杂度 O(1)O(log n)O( n)O( nlog n)O( n2)O( n3)最常见的指数时间算法的渐近时间复杂度 O(2n)O( n！)O( nn)通用分治递推式大小为 n 的原问题分成若干个大小为 n/b 的子问题，其中 a 个子问题需要求解，而 cnk 是合并各个子问题的解需要的工作量。NP 完全性理论P 是所有可在多项式时间内用确定算法求解的判定问题的集合。NP 是所有可在多项式时间内用不确定算法求解的判定问题的集合。（NP 难度）对于问题 Q以及任意问题 Q1NP，都有 Q1Q，则 Q是 NP难度（NP hard）
3、的。其中表示约化，Q1Q，表示 Q1可以在多项式时间转化为问题 Q，从而可通过调用问题 Q的算法求解。（NP 完全）对于问题 QNP，Q 是 NP难度的，则称 Q是 NPC（NP complete）的。P NP NPC 的关系2/8第 2章 递归与分治策略分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2.2 分治法的基本思想divide-and-conquer(P)if ( | P | 1)(/(31)( nOT3/8void QuickSort (Type a, int p, int r)if (pType RandomizedSele
4、ct(Type a,int p,int r,int k)if (p=r) return ap;int i=RandomizedPartition(a,p,r),j=i-p+1;if (k2n时，算法需要 (n2 n)计算时间。 第 4章 贪心算法4.1 活动安排问题掌握算法 GreedySelector()4.2 贪心算法的基本要素1.贪心选择性质贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，xCwini1,0iixv1ma6/8即贪心选择来达到。这是贪心算法可行的第一个基本要素。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式
5、作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。掌握背包问题的贪心算法 Knapsack。4.5 单源最短路径掌握 Dijkstra算法思想，复杂度分析。4.6 最小生成树掌握 Prim算法和 Kruskal算法思想，复杂度分析。第 5章 回溯法5.1 回溯法的算法框架 回溯法的基本步骤： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足
6、约束的子树； 用限界函数剪去得不到最优解的子树。 关于复杂性： 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。子集树的回溯算法 O(2n)void backtrack (int t) if (tn) output(x); else for (int i=0;in) output(x); else for (int i=t;i=n;i+) swap(xt,xi); if (legal(t) backtrack(t+1); swap(xt,xi) 5.6 0-1
7、背包问题 解空间：子集树 可行性约束函数: wixiC 上界函数：Bound()掌握 Bound函数的思想。掌握 Knapsack回溯算法思想。计算时间复杂度为为 O(n2n)。5.7 最大团问题 解空间：子集树 可行性约束函数：顶点 i到已选入的顶点集中每一个顶点都有边相连。 上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。掌握最大团问题的回溯算法 backtrack思想。计算时间复杂度为为 O(n2n)。5.9 旅行售货员问题 解空间：排列树 上界函数: 是否优于已找到的当前最优回路。 复杂度分析：算法 backtrack在最坏情况下可能需要更新当前最优解 O(n-1)
8、!)次，每次更新 bestx需计算时间 O(n)，从而整个算法的计算时间复杂性为 O(n!)第 6章 分支限界法6.1 分支限界法的基本思想分支限界法与回溯法的区别：8/8（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 分支限界法的搜索策略：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次
9、机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 两种分支限界法：队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式(priority queue)分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。在算法实现时通常用堆来表示。6.2 单源最短路径解单源最短路径问题的优先队列式分支限界法用一极小
10、堆来存储活结点表。其优先级是结点所对应的当前路长。掌握剪枝策略。掌握用分支限界法求解单源最短路径的算法思想。6.3 装载问题掌握用优先队列式分支限界法求解装载问题：存储活结点的方式: 最大堆存储活结点表。活结点 x在优先队列中的优先级定义: 从根结点到结点 x的路径所相应的载重量再加上剩余集装箱的重量之和。扩展结点的选择： 优优先级最大的活结点成为下一个扩展结点。算法终止条件： 子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。掌握 MaxLoading方法。6.5 0-1背包问题活结点优先队列中结点元素 N的优先级由该结点的上界函数 Bound计算出的值uprofit给出。以结点 N为根的子树中任一结点的价值不超过 N.profit。掌握 MaxKnapsack方法。
