算法设计与分析_总结1.pdf

《算法设计与分析_总结1.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析_总结1.pdf（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一些概念一些概念递归递归： 直接或间接的调用自身算法称为递归算法； 用函数自身给出定义的函数称为递归函数。分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题， 以便各个击破，分而治之。分治法（分治法（divide-and-conquerdivide-and-conquer）的基本思想）的基本思想：A 分割成 k 个更小规模的子问题。B 对这 k 个子问题分别求解。如果子问题的规模仍然不够小， 则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。C 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。设

2、计动态规划算法的步骤设计动态规划算法的步骤(1)找出最优解的性质， 并刻划其结构特征。 (2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。最优子结构性质最优子结构性质：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。递归算法求解问题时，每次产生的子问题并不总是新问题， 有些子问题被反复计算多次。 这种性质称为子问题的重叠性质贪心算法贪心算法: 贪心算法总是作出在当前看来最好的选择,它并不从整体最优考虑， 它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合， 是可以用贪心算法有效求

3、解的很好例子。贪心算法贪心算法： 贪心算法求解的这类问题一般具有2 个重要的性质： 贪心选择性质和最优子结构性质。 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质贪心算法与动态规划算法的差异：贪心算法和动态规划算法都要求问题具有最优子结构性质，这是 2 类算法的一个共同点。 动态规划算法通常以自底向上的方式解各子问题， 而贪心算法则通常以自顶向下的方式进行， 以迭代的方式作出相继的贪心选择， 每作一次贪心选择就将所求问题简化为规模更小的子问题。0-10-1 背包问题背包问题：给定 n

4、种物品和一个背包。物品 i 的重量是 Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?单源最短路径基本思想是，单源最短路径基本思想是，设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时， S 中仅含有源。设u 是G 的某一个顶点， 把从源到 u 且中间只经过 S 中顶点的路称为从源到u 的特殊路径， 并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S中取出具有最短特殊路长度的顶点 u，将u 添加到 S 中，同时对数组dist 作必要

5、的修改。一旦S 包含了所有 V 中顶点，dist 就记录了从源到所有其它顶点之间的最短路径长度。回溯法的基本思想回溯法的基本思想：(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常见的两种分支限界法：常见的两种分支限界法： （1）队列式(FIFO)分支限界法。按照队列先进先出（ FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法。 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。布线问题算法思想：布线问题算法思想： 解此问题的队列式分支限界法从起始位置a 开始将它作为

6、第一个扩展结点。 与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中， 并且将这些方格标记为 1，即从起始方格 a 到这些方格的距离为 1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。 这个过程一直继续到算法搜索到目标方格b 或活结点队列为空时为止。 即加入剪枝的广度优先搜索。随机存储机 RAM 它描述的形式计算机是一台带累加器计算机，他不允许程序修改其自身，RAM 由只读输入带、 只写输入带、 程序存储部件、 内存储器和指令计数器5 个部分组成。 P类和 NP 类语言的定义 P=L|L 是一个能在多项式

7、时间内被一台DTM 所接受的一眼 NP+L|L 是一个能在多项式时间内被一台 NDTM 所接受的语言 由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被非确定性图灵机接受。故 P 属于NP PNP P类问题：类问题：是确定性计算模型下的易解问题类。NPNP 类问题类问题：是非确定性计算模型下的易验证问题类。NPNP 完全类问题：完全类问题：即多项式复杂度的非确定性问题类；简单的写法是 NP=P？问题就在这个问号上，到底是 NP 等于 P，还是 NP 不等于 P。算法的渐进时间复杂性的含义？算法的渐进时间复杂性的含义？答：当问题的规模 n 趋向无穷大时，影响算法效率的重要因

8、素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用 T(n)的数量级(阶)评价算法。时间复杂度 T(n)的数量级(阶)称为渐进时间复杂性。最坏情况下的时间复杂性和平均时间复杂性有什么不同？最坏情况下的时间复杂性和平均时间复杂性有什么不同？答： 最坏情况下的时间复杂性和平均时间复杂性考察的是n 固定时， 不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n，I) ,IDn A(n) =P(I)T(n，I)IDn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：采用回溯法求解的问题，其解如何表示？有什么规定？采

9、用回溯法求解的问题，其解如何表示？有什么规定？问题的解可以表示为 n 元组： （x1,x2,xn） ，xiSi, Si 为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（x1,x2,xi）(in)一定合理。简述渐进时间复杂性上界的定义。T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数 No 和 C，nNo，有 T(n)f(n)，这种关系记作 T(n)=O(f(n)。快速排序的基本思想是什么。快速排序的基本思想是什么。快速排序的基本思想是在待排序的N 个记录中任意取一个记录， 把该记录放在最终位置后，数据序列被此记录分成两部分。 所有关

10、键字比该记录关键字小的放在前一部分， 所有比它大的放置在后一部分，并把该记录排在这两部分的中间， 这个过程称作一次快速排序。 之后重复上述过程，直到每一部分内只有一个记录为止。什么是直接递归和间接递归？什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分， 既调用它自己本身，这称为直接递归。如果过程或者函数 P 调用过程或者函数Q，Q 又调用 P，这个称为间接递归。消除递归一般要用到栈这种数据结构。哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。 其压缩率通常在 20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表

11、来建立一个用0，1 串表示各字符的最优表示方式。前缀码：对每一个字符规定一个0,1 串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。二、递归与分治：二、递归与分治：二分搜索算法：二分搜索算法：public static int binarySearch(int a, int x, int n) left = 0;right = n - 1;while (left amiddle) left = middle + 1;elseright = middle - 1;return -1;棋盘覆盖棋盘覆盖public void chessBoard(int tr, int tc, int

12、dr, int dc, int size)if (size = 1) return;int t = tile+,s = size/2;if (dr tr + s & dc tc + s)chessBoard(tr, tc, dr, dc, s);else boardtr + s - 1tc + s - 1 = t;chessBoard(tr, tc, tr+s-1, tc+s-1, s);if (dr = tc + s)chessBoard(tr, tc+s, dr, dc, s);else boardtr + s - 1tc + s = t;chessBoard(tr, tc+s, tr+s

13、-1, tc+s, s);if (dr = tr + s & dc = tr + s & dc = tc + s)chessBoard(tr+s, tc+s, dr, dc, s);else boardtr + stc + s = t;chessBoard(tr+s, tc+s, tr+s, tc+s, s);三、动态规划三、动态规划最长公共子序列最长公共子序列void LCSLength(int m，int n，char x，char y，intc，int b)int i，j;for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i

14、= 0;for (i = 1; i = m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3; 构造最长公共子序列构造最长公共子序列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b);else LCS(i，j-1，x，b);最优装载最优装载void Loading(int x,Type w, Type c, i

15、nt n)int *t = new int n+1;Sort(w, t, n);for (int i = 1; i = n; i+) xi = 0;for (int i = 1; i = n & wti n)r -= wi;if (cw + wi bestw)xi = 0;backtrack(i + 1);r += wi; 批处理问题：批处理问题：void Flowshop:Backtrack(int i)if (i n) for (int j = 1; j = n; j+)bestxj = xj; bestf = f;elsefor (int j = i; j f1)?f2i-1:f1)+M

16、xj2;f+=f2i;if (f bestf) Swap(xi, xj);Backtrack(i+1);Swap(xi, xj);f1- =Mxj1;f- =f2i;六、分支限界法六、分支限界法单源最短路径问题单源最短路径问题while (true) for (int j = 1; j = n; j+)if (cE.ijinf)&(E.length+cE.ijdistj) / 顶点 i 到顶点 j 可达，且满足控制约束distj=E.length+cE.ij;prevj=E.i;MinHeapNode N;N.i=j;N.length=distj;H.Insert(N);try H.Delet

17、eMin(E);catch (OutOfBounds) break;第一章第一章 绪论绪论1 1、重要特性、重要特性1. 1.输入输入2. 2.输出输出3. 3.有穷性有穷性4. 4.确定性确定性5. 5.可行性可行性2 2、描述算法的方法、描述算法的方法1. 1.自然语言：优点是直观易懂，缺点是容易出现二义性自然语言：优点是直观易懂，缺点是容易出现二义性2. 2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言3. 3.程序设计语言：优点是计算机直接运行，缺点是抽象性差程序设计语言：优点是计算机直

18、接运行，缺点是抽象性差4. 4.伪代码伪代码：3 3、递归算法分析、递归算法分析1. 1.猜测技术猜测技术2. 2.扩展递归技术扩展递归技术3. 3.通用分治递归推式通用分治递归推式第二章第二章 NPNP 完全理论完全理论第三章第三章 蛮力法蛮力法3.13.1 蛮力法的设计思想蛮力法的设计思想蛮力法依赖的基本技术扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键依次处理所有元素。3.23.2 查找问题中的蛮力法查找问题中的蛮力法3.2.13.2.1 顺序查找顺序查找 O(n)O(n)3.2.23.2.2 串匹配问题串匹配问题BF O(n*m)BF O(n*m)

19、BMP O(n+m)BMP O(n+m)BM O(n*m)BM O(n*m)3.33.3 排序问题中的蛮力法排序问题中的蛮力法2 23.3.13.3.1 选择排序选择排序O(nO(n ) )2 23.3.23.3.2 起泡排序起泡排序O(nO(n ) )3.43.4 组合问题中的蛮力法组合问题中的蛮力法3.4.13.4.1 生成排列对象生成排列对象O(n!)O(n!)n n3.4.23.4.2 生成子集生成子集O(2O(2 ) )n n3.4.3 0/13.4.3 0/1背包问题背包问题O(2O(2 ) )3.4.43.4.4 任务分配问题任务分配问题O(n!)O(n!)3.53.5 图问题中

20、的蛮力法图问题中的蛮力法3.5.13.5.1 哈密顿回路问题哈密顿回路问题O(n!)O(n!)3.5.2 TSP3.5.2 TSP 问题问题O(n!)O(n!)3.63.6 几何问题中的蛮力法几何问题中的蛮力法2 23.6.13.6.1 最近对问题最近对问题O(nO(n ) )3 33.6.23.6.2 凸包问题凸包问题O(nO(n ) )3.73.7 实验项目串匹配问题实验项目串匹配问题第四章第四章 分治法分治法4.14.1 分治法的设计思想分治法的设计思想设计思想：将要求解的原问题划分成 k 个较小规模的子问题，对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为

21、 k 个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。步骤： （1）划分（2）求解子问题（3）合并4.24.2 排序问题中的分治法排序问题中的分治法4.2.14.2.1 递归排序递归排序O(nlogO(nlog2 2n)n)4.2.24.2.2 快速排序快速排序O(nlogO(nlog2 2n)n)4.34.3 组合问题中的分治法组合问题中的分治法4.3.14.3.1 最大字段和问题最大字段和问题O(nlogO(nlog2 2n)n)k k4.3.24.3.2 棋盘覆盖问题棋盘覆盖问题O(4O(4

22、 ) )k k4.3.34.3.3 循环赛日程安排问题循环赛日程安排问题O(4O(4 ) )4.44.4 几何问题中的分治法几何问题中的分治法4.4.14.4.1 最近对问题最近对问题O(nlogO(nlog2 2n)n)4.4.24.4.2 凸包问题凸包问题O(nlogO(nlog2 2n)n)4.54.5 实验项目最近对问题实验项目最近对问题第五章第五章 减治法减治法5.15.1 减治法的设计思想减治法的设计思想原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。5.25.2 查找问题中的减治法查找问题中的减治法5.2.15.2.1 折

23、半查找折半查找O(logO(log2 2n)n)5.2.25.2.2 二叉查找树二叉查找树O(logO(log2 2n)n)5.35.3 排序问题中的减治法排序问题中的减治法5.3.15.3.1 堆排序堆排序O(logO(log2 2n)n)5.3.25.3.2 选择问题选择问题O(logO(log2 2n)n)5.45.4 组合问题中的减治法组合问题中的减治法5.4.15.4.1 淘汰塞冠军问题淘汰塞冠军问题O(n)O(n)5.4.25.4.2 假币问题假币问题O(logO(log2 2n)n)5.55.5 实验项目实验项目8 8 枚硬币问题枚硬币问题第六章第六章 动态规划法动态规划法6.1

24、6.1 动态规划法的设计思想动态规划法的设计思想将待求解问题分解成若干个相互重叠的子问题， 每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。步骤：将原始问题分解为相互重叠的子问题，确定动态规划函数；求解子问题，填表；根据表，自底向上计算出原问题的解。6.26.2 图问题中的动态规划法图问题中的动态规划法6.2.1 TSP6.2.1 TSP 问题问题O(2O(2 ) )n n6.2.26.2.2 多段图的最短路径问题多段图的最短路径问题O(n+m)6.36.3 组合问题中的动态规划法组合问题中的动态规划法6.

25、3.16.3.10/0/1 1 背包问题背包问题 O(n*C)O(n*C)6.3.26.3.2 最长公共子序列问题最长公共子序列问题 O(n*m)O(n*m). .6.46.4 查找问题中的动态规划法查找问题中的动态规划法6.4.16.4.1 最优二叉查找树最优二叉查找树 O(n3)O(n3)6.4.26.4.2 近似串匹配问题近似串匹配问题6.56.5 实验项目最大子段和问题实验项目最大子段和问题第七章第七章 贪心法贪心法7.17.1 贪心法的设计思想贪心法的设计思想贪心法在解决问题的策略上目光短浅， 只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都

26、不会改变。贪心法的关键在于决定贪心策略。7.27.2 图问题中的贪心法图问题中的贪心法7.2.1 TSP7.2.1 TSP 问题问题O(2O(2 ) )7.2.27.2.2 图着色问题图着色问题n n7.2.37.2.3 最小生成树问题最小生成树问题O(2O(2 ) )7.37.3 组合问题中的贪心法组合问题中的贪心法7.3.17.3.1 背包问题背包问题O(nlogO(nlog2 2n)n)7.3.27.3.2 活动安排问题活动安排问题O(nlogO(nlog2 2n)n)7.3.37.3.3 多机调度问题多机调度问题 O(n*m)O(n*m)7.47.4 实验项目哈夫曼编码实验项目哈夫曼编

27、码第八章第八章 回溯法回溯法8.18.1 回溯法的设计思想回溯法的设计思想n n从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时， 先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（ Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。步骤：确定解向量和分量的取值范围，构造解空间树；确定剪枝函数；对解空间树按深度优先搜索，搜索过程中剪枝；从所有的可能解中确定最优解。8.28.2 图问

28、题中的回溯法图问题中的回溯法8.2.18.2.1 图着色问题图着色问题8.2.28.2.2 哈密顿回路问题哈密顿回路问题8.38.3 组合问题中的回溯法组合问题中的回溯法8.3.18.3.1 八皇后问题八皇后问题8.3.28.3.2 批处理作业调度问题批处理作业调度问题8.48.4 实验项目实验项目0/0/1 1 背包问题背包问题第九章第九章 分支界限法分支界限法9.19.1 分支限界法的设计思想分支限界法的设计思想1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up ，并确定限界函数；2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结

29、点，分别估算这些孩子结点的限界函数的可能取值；3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表 PT）中；4）依次从表 PT 中选取使限界函数的值是极值的结点成为当前扩展结点；5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。步骤：确定解空间树确定限界函数按广度优先搜索解空间树，计算限界函数的值，填入 PT 表从 PT 表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。9.29.2 图问题中的分支限界法图问题中的分支限界法9.2.1 TSP9.2.1 TSP 问题问题9.2.29.2.2 多段图的最短路径问题多段图的最短路径问题9.39.3 组合问题中断饿分支限界法组合问题中断饿分支限界法9.3.19.3.1 任务分配问题任务分配问题9.3.29.3.2 批处理作业调度问题批处理作业调度问题9.49.4 实验项目电路布线问题实验项目电路布线问题第十章第十章 概率算法概率算法