算法分析与设计课程实验报告.doc

算法分析与设计课程实验报告班 级： 131213 学 号： 13121XXX 姓 名： XXX 指导老师： 邓 凡 目录算法分析与设计课程实验报告1实验一 排序11. 课本练习2.3-712. 实现优先队列23.快速排序24. 第k大元素3实验二 动态规划41. 矩阵链乘42. 最长公共子序列53. 最长公共子串74. 最大和95. 最短路径10实验三 贪心策略111. 背包问题112. 任务调度143. 单源点最短路径154. 任意两点间最短路径16实验四 回溯法181. 0-1背包问题182. 8-Queen问题21实验一 排序1. 课本练习2.3-7(1) 问题描述描述一个运行时间为(nlgn)的算法，给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好是x的元素。(2)问题分析该问题首先要进行排序，然后用二分查找法判断S中是否存在两个其和刚好是x的元素，因为时间复杂度为(nlgn)，所以可以采用归并排序。(3) 算法分析 归并排序的思想是将n个元素分成各含n/2个元素的子序列，然后对两个子序列递归地进行排序，最后合并两个已排序的子序列得到排序结果。二分查找的思想是对于集合中的每一个数字，用二分法找到x-Si的位置，若存在且不为其本身，则输出S中存在有两个和等于x的元素；否则，不存在。(4) 实验结果2. 实现优先队列(1) 问题描述实现优先队列，维护一组元素构成的集合S。(2) 问题分析 优先队列是基于堆排序的。首先将集合S中的元素进行堆排序。当进行操作时，要不断维护集合S的有序性，即要不断地调整堆。(3) 算法分析本程序中主要的函数有INSERT()：需要调用INCREASE_KEY()来维护堆，其时间复杂度为O（lgn），函数MAXIMUM()仅需要返回S1，时间复杂度为(1)，函数EXTRACT_MAX()需要调用堆排序中的MAX_HEAPIFY，时间复杂度为O(lgn)，函数INCREASE_KEY()更新结点到根结点的路径长度为O(lgn)，时间复杂度为O(lgn)。3.快速排序(1) 问题描述 实现快速排序(2) 问题分析快速排序采用了分治策略。数组Ap.r被划分成两个子数组Ap.q-1和Aq+1.r，使得Ap.q-1中的每个元素都小于等于A(q)，而且，小于等于Aq+1.r中的元素。然后通过递归调用快速排序，对子数组Ap.q-1和Aq+1.r排序。最后将两个数组合并。(3) 算法分析 快速排序不需要额外的辅助空间，其时间复杂度在平均情况下为O(nlgn)，最坏情况下为O()。快速排序是不稳定的排序算法。(4) 实验结果4. 第k大元素(1) 问题描述 给定两个大小分别为m和n的有序序列，采用分治法求解两个序列合起来的第k大元素，使得时间复杂度为O(lgm+lgn)。(2) 问题分析将A平均分为前后两个部分，前半部分有x个元素，后半部分有m-x个元素。因为A有序，所以后半部分的所有元素均大于前半部分。Ax为后半部分的第一个元素。将B也平均分为前后两个部分，前半部分有y个元素，后半部分有n-y个元素。By是后半部分的第一个元素。(3) 算法分析由于两个数组都是平均划分的，我们可以近似地认为x=m/2, y=n/2。假设Ax=By,则有a.By前面至少有x+y个元素，如果kx+y，合并后第k大元素必然在Ax后面。所以，原来在A数组中前半部分可以排除掉。实验二 动态规划1. 矩阵链乘(1) 题目要求给定n个矩阵链，矩阵Ai的规模为pi-1*pi（1in），求完全括号化方案，使得A1A2,.An所需标量乘法次数最小。(2) 题目分析本问题满足最优子结构性质（矩阵链乘AiAi+1.Aj的最优化括号方案包含其子问题AiAi+1.Ak和Ak+1Ai+1.Aj的最优括号方案）：假设AiAi+1,.Aj所的最优括号化方案的分割点在Ak和Ak+1之间。那么，继续对前缀子链AiAi+1,.Ak优化我们应该采用独立求解它时所得的最优化方案。同理，在子链Ak+1Ak+2,.Aj进行括号化的方法，就是它自身的最优化括号方案。所以可以用动态规划来求解。(3) 算法分析 为了构造一个矩阵链乘问题的最优解，我们可以将问题划分为两个子问题（AiAi+1.Ak和Ak+1Ai+1.Aj的最优括号化问题），求出子问题的解，然后将子问题的最优解组合起来，同时必须保证考察了所以的可能的分割点。设mi,j表示计算AiAi+1.Aj所需标量乘法次数的最小值，则原问题的最优解就是m1,n。AiAi+1.Aj的最小代价括号方案的递归求解公式为：本程序的主要函数是基于上述递归式的函数MatrixChainOrder(),它采用自底向上表格法,根据输入的矩阵规模数组，计算mi,j，同时构造一个辅助数组si,j用来记录最优值mi,j对应的分割点k，最后可以根据si,j的值构造最优解(调用函数PrintOptimal(),该算法的时间复杂度是O(n3)。(4) 实验结果实验结果如图所示：2. 最长公共子序列(1) 问题描述用动态规划方法求两个字符序列X和Y的最长公共子序列。(2) 问题分析LCS问题的最优子结构是：设X=和Y=为两个序列，Z=为X与Y的任一LCS。a. 如果xm=yn,则zk=xm=yn且Zk-1是Xm-1与Yn-1的一个LCS。b. 如果xmyn,则zkxm意味着Z是Xm-1与Y的一个LCS。c. 如果xmyn,则zkyn意味着Z是X与Yn-1的一个LCS。上述最优子结构意味着在求解X与Y的一个LCS时，需要求解一个或两个子问题，如果xm=yn,求解Xm-1与Yn-1的一个LCS；如果xmyn,需要求解Xm-1与Y的一个LCS和X与Yn-1的一个LCS。用ci,j表示序列X1.i与Y1.j的最长公共子序列的长度，则cm,n为X与Y的最长公共子序列长度。根据最优子结构的性质，ci,j的递归式为：(3) 算法分析本程序的主要函数是基于递归式的LCSLength()，它的作用是构造ci,j表，用来存储LCS的长度，同时构造一个辅助数组bi,j存储计算ci,j时指向所选择的子问题最优解，用来帮助构造最优解（调用函数printLCS()），该算法的时间复杂度为O(n3).(4) 实验结果实验结果如下图所示：所遇到的问题：定义函数printLCS()时出现错误 type of formal parameter 1 is incomplete,通过在参数列表中添加二维数组的大小来解决的。3. 最长公共子串(1) 问题描述给定两个字符串X和Y，求X和Y的最长公共子串。(2) 题目分析本问题与LCS问题相似，不同之处在于LCS问题不要子序列是连续的，但子串要求是连续的。最长公共子串问题满足最优子结构性质：设X=和Y=为两个字符串，Z=为X与Y的任一子串。如果xm=yn,则zk=xm=yn且Zk-1是Xm-1与Yn-1的一个子串。上述最优子结构意味着在求解X与Y的一个子串时，需要求解一个：如果xm=yn,求解Xm-1与Yn-1的一个子串。用ci,j表示字符串X1.i与Y1.j的最长公共子串的长度，则cm,n为X与Y的最长公共子串长度。根据最优子结构的性质，ci,j的递归式为：(3) 算法分析本程序的主要函数是基于递归式的LCSSubLength()，它的作用是构造ci,j表，用来存储子串的长度，同时构造一个辅助数组bi,j存储计算ci,j时指向所选择的子问题最优解，用来帮助构造最优解（调用函数printLCS()），该算法的时间复杂度为O(n3).(4) 实验结果4. 最大和(1) 问题描述给定n个整数（可能为负数）组成的序列A=，求该序列连续的子段和的最大值。(2) 问题分析 由上述问题可以将最大字段和定义为： 设bj=max(sum(i,j),即以aj为结束元素的连续数组的最大和。则X=max（bj），则原问题所求为bn，bj的递归式为：(3) 算法分析 基于上述递归式的函数DPMaxSum()是本程序的主要函数，它用来计算最大字段和，时间复杂度为O(n).(4) 实验结果5. 最短路径(1)题目要求根据输入的带权有向图G的n*n矩阵W，求图中源点到目的顶点的最短路径。 (2)题目分析 这个问题需要用动态规划来解决，可以用Floyd-Warshall算法来实现。(3) 算法分析首先考虑其最优子结构特性。总结如下： 设G的两个不同的顶点i,jV=1,2,.,n,p是从i到j期间不经过k+1,k+2,.,n的最短路径。则有： a.若p不经过顶点k，则p也是从i到达j期间不经过k,k+1,.,n的最短路径。b若p经过顶点k，即p:ikj。我们将前半段ik记为p1,后半段kj记为p2,。则p1是从i到k期间不经过k,k+1,.,n的最短路径，p2是从k到j期间不经过k,k+1,.,n的最短路径。定义di,jk为i到j且期间不通过k+1,k+2,.,n中任一顶点的最短路径长度，显然，di,jk为i到j的最短路径长度。根据上述的最优子结构特性，有关di,jk为的递归式为： 由此递归式可知子问题具有重叠性。记为： Dk=（di,jk）n*n则Dn将记录G的所有顶点对(i,j)的最短路径长度。 Floyd-Warshall算法是一种动态规划方法，时间复杂度为O（n3）。本程序中，用矩阵W来表示带权有向图，用一维数组存储这个图的矩阵，用float.h中的宏DBL_MAX来表示。本程序的主要函数是floyd()，参数为表示图的矩阵w和图的顶点个数n,该函数主要用来计算任意两点间的最短路径长度，存入数组d中，并调用了函数printAll()，其作用是打印出任意节点到其它所有节点的最短路径及其长度。(4) 实验结果实验结果如下图所示：实验三 贪心策略1. 背包问题 1.1分数背包 (1)题目要求 给定n种物品和一个背包。物品i的重量为wi其价值为vi，背包的容量为C,求如何装载背包，使得装入背包中的物品总价值最大。选择装入的物品时，可以选择物品的一部分。 (2)题目分析因为物品可以分割成块，单位块的价值越大，显然总价值越大,所以它的局部最优满足全局最优，可以用贪心法来解决。 (3)算法分析 把n种物品的取舍状态用一个向量表示x1,x2,.,xn,其中xi0,1.首先，应该计算每种物品的单位价值vi/wi，然后按照单位价值从大到小进行排序，根据贪心选择策略，将尽可能多的单位价值最高的物品装入背包，如果该物品全部装入背包而没有超重时，继续装入单位价值第二大的物品，以此类推，直到达到背包容量上界C。该程序的主要函数是GreedyKnapsack(),其作用是构造xi,最后根据xi的状态可以确定装入背包的方案.贪心算法的时间复杂为O(nlgn).1.2 0/1背包(1) 题目要求给定n种物品和一个背包。物品i的重量为wi其价值为vi，背包的容量为C,求如何装载背包，使得装入背包中的物品总价值最大。选择装入的物品时，不可以选择物品的一部分。(2) 题目分析 把n种物品的取舍状态用一个向量表示x1,x2,.,xn,其中xi只有两种可能取值0或1。当xi=1时，表示将第i个物品装入背包，当xi=0时，表示不将第i个物品装入背包，那么这个0-1背包问题就可以形式化地描述为： maxvixi结束条件为 wixiC，xi0,1，1in也就是说0-1背包问题实际上就是求这样一个向量x1,x2,.,xn,xi0,1，1in，使得vixi最大，同时满足 wixiC。(3) 算法分析 对于0-1背包问题，贪心算法不能得到最优解，无法保证最后将背包装满。贪心策略中，采用多步过程来完成背包的装入，在每一步中，都是利用固定的贪心准则（从剩下物品中选择价值最大的物品）来选择物品。为了求解最优解，该问题可采用动态规划方法。 用ci,j表示背包剩余容量为j，剩余物品为i，i+1，.，n时的最优解的值，我们的目标是求解cn,C。ci,j的递归式是：其最优子结构为：一，如果当前最优解包含物品n，那么剩下的选择中方案是从1,2，.，n-1，容量为C-wn；二，如果当前最优解不包含物品n，那么剩下的选择中方案是从1,2，.，n-1，容量为C。该程序的主要函数是基于递归式的Knapsack01()，它的作用是填写ci,j，遍历所有物品，直到得到cn,C即为所求，它的时间复杂度为O(nC).2. 任务调度(1) 题目要求给定n个任务及每个任务的运行时间ti，要求按顺序执行，求一种最佳的调度方案，使平均完成时间最小。(2) 题目分析该题可以采用短任务优先调度算法，使用贪心策略来实现(3) 算法分析贪心算法是通过一系列选择来求出问题的最优解，每个决策点做出当前情况下的最佳选择。贪心选择性质是指所求问题的最优解可以通过一系列局部最优的选择来到。贪心算法通常以自顶向下的方式进行。该题中要得到所有任务的平均最小完成时间，只需要将各个任务按运行时间从小到大排序，任务完成时间为它等待的时间与自身完成时间之和。主要的调度算法包含三部分：一，排序，按照运行时间从小到大的顺序将任务排序；二，计算总的平均完成时间；三，输出调度结果。(4) 实验结果实验结果如下图所示：3. 单源点最短路径(1)题目要求给定带权有向图G=的权重矩阵W。求从源点s到其他结点的最短路径。(2)题目分析这是一个求单源点最短路径问题，因为给定的权重矩阵中存在负值，即存在负权值的边，所以可以用bellmanFord算法求解。(3)算法分析 最短路径的最优子结构性质是最短路径的子路径也是最短路径，如下所述：给定带权有向图G=及其权重函数w：ER。设p=1,2,.,k为从结点1到结点k的一条最短路径，并且对于任意的i和j，1ijk，设pij=i，i+1，.，j为路径p中从结点i到j的子路径，那么pij是从结点i到j的最短路径Bellman-Ford算法解决的是一般情况下的单源点最短路径问题，克服了Dijkstra算法不能处理图中存在负权值的情况。在这里，边的权值可以为负值，给定带权有向图G=及其权重矩阵W。bellmanFord算法返回一个布尔值，表示是否存在一个从源点可以到达的权重为负值的环路，如果存在，算法将告知我不不存在解决方案，否则，算法将给出最短路径以及它们的权重。BellmanFord算法通过对边进行松弛操作来渐近地降低从源点s到每个结点v的最短路径的估计值d，直到该估计值与实际的最短路径权重相同。该算法返回true当且仅当输入图不包含从源点到达的权重为负值的环路。BellmanFord算法大致可以分为三个部分：一，初始化所有的点，每一个点保存一个值，表示从源点到这个点的距离，将源点的值设为0，其他值设为无穷大；二，循环，遍历所有的边，进行松弛操作；三，遍历途中所有的边，判断途中是否存在回路。BellmanFord算法的时间复杂度是O(VE)。4. 任意两点间最短路径 (1)题目要求根据输入的带权有向图G的n*n矩阵W，求图中每一个顶点到其他所有顶点的最短路径。 (2)题目分析 这个问题需要用动态规划来解决，Floyd-Warshall算法来实现。(3)算法分析首先考虑其最优子结构特性。总结如下： 设G的两个不同的顶点i,jV=1,2,.,n,p是从i到j期间不经过k+1,k+2,.,n的最短路径。则有： a.若p不经过顶点k，则p也是从i到达j期间不经过k,k+1,.,n的最短路径。b若p经过顶点k，即p:ikj。我们将前半段ik记为p1,后半段kj记为p2,。则p1是从i到k期间不经过k,k+1,.,n的最短路径，p2是从k到j期间不经过k,k+1,.,n的最短路径。定义di,jk为i到j且期间不通过k+1,k+2,.,n中任一顶点的最短路径长度，显然，di,jk为i到j的最短路径长度。根据上述的最优子结构特性，有关di,jk为的递归式为： 由此递归式可知子问题具有重叠性。记为： Dk=（di,jk）n*n则Dn将记录G的所有顶点对(i,j)的最短路径长度。 Floyd-Warshall算法是一种动态规划方法，时间复杂度为O（n3）。本程序中，用矩阵W来表示带权有向图，用一维数组存储这个图的矩阵，用float.h中的宏DBL_MAX来表示。本程序的主要函数是floyd()，参数为表示图的矩阵w和图的顶点个数n,该函数主要用来计算任意两点间的最短路径长度，存入数组d中，并调用了函数printAll()，其作用是打印出任意节点到其它所有节点的最短路径及其长度。(4)实验结果实验结果如下图所示：实验四 回溯法1. 0-1背包问题(1)题目要求 给定n种物品和一个背包。物品i的质量为wi，其价值为vi，背包的容量为C,求如何装载背包，使得装入背包中的物品总价值最大。(2)题目分析 把n种物品的取舍状态用一个向量表示x1,x2,.,xn,其中xi只有两种可能取值0或1。当xi=1时，表示将第i个物品装入背包，当xi=0时，表示不将第i个物品装入背包，那么这个0-1背包问题就可以形式化地描述为： maxvixi结束条件为 wixiC，xi0,1，1in也就是说0-1背包问题实际上就是求这样一个向量x1,x2,.,xn,xi0,1，1in，使得vixi最大，同时满足 wixiC。要找到这样的向量，可以应用回溯法在由0-1构成的解空间树中进行查找。在搜索解空间树的过程中，只要其孩子是可行节点，搜索就进入该孩子节点继续搜索，否则通过剪枝操作减掉不可行节点以下分支。为了节省空间，可以分两次回溯搜索解空间树，第一次搜索计算出背包可以装载的最大价值量，第二次搜索计算出满足这个最大价值量的全部装包方案。(3) 算法分析该算法主要的函数时knap1()和knap2(),knap1()的作用是递归地回溯搜索解空间树，计算出背包装载物品的最大价值量，其中参数n的作用是作为数组x的下标，每递归调用knap1()一次，n的值都会加1传递，通过这种方法在数组x中记录搜索的路径。flag为物品的数量，当n=flag时表示找到一条可能解的路径，即找到了一种可行的背包装载方案，但不一定是最佳的。参数c是装载的上界，函数isOverLoad()的作用是判断当前x中记录的搜索路径对应的物品重量是否超过装载上界c，一旦物品的当前重量超过c，则本次返回递归调用，相当于搜索二叉树的剪枝操作，这样后续的分支就不再搜索了。参数*price为一个指针型变量，其返回背包可装载物品的最大值。当n=flag时，表明找到一种可行的背包方案，这时调用函数getValue()获得此背包装载方案对应的物品价值总量，如果该值大于*price，则将该价值总