最新算法设计与分析实验报告

本科实验报告课程名称： 算法设计与分析 实验项目： 递归与分治算法 实验地点： 计算机系实验楼110 专业班级： 物联网1601 学号： 2016002105 学生姓名： 俞梦真 指导教师： 郝晓丽 2018年 05月 04 日实验一 递归与分治算法1.1 实验目的与要求1进一步熟悉C/C+语言的集成开发环境；2通过本实验加深对递归与分治策略的理解和运用。1.2 实验课时2学时1.3 实验原理分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。1.4 实验题目1上机题目：格雷码构造问题Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。对于给定的正整数n，格雷码为满足如下条件的一个编码序列。（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。（2）序列中无相同的编码。（3）序列中位置相邻的两个编码恰有一位不同。 2设计思想：根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。3代码设计：#include#include#include #includeusing namespace std;/求格雷码 递推式子：G(n-1)=B(n-1) G(i)=B(i+1)异或B(i) (0in-2)/输出n位GRad码-普通方法vector My_grad;void get_grad(int n)/cout11)/cout1endl;for(int i=2;i=n;i+)vector tmp;for(int j=0;j=0;j-)string s=1;s+=tmpj;My_grad.push_back(s);int main()int n;while(cinn)get_grad(n);for(int i=0;iMy_grad.size();i+)coutMy_gradi0，T=(t1,t2,tn)，客户i希望的服务完成时刻为di0，D=(d1,d2,dn)；一个调度f:AN，f(i)为客户i的开始时刻。如果对客户i的服务在di之前结束，那么对客户i的服务没有延迟，即如果在di之后结束，那么这个服务就被延迟了，延迟的时间等于该服务的实际完成时刻f(i)+ti减去预期结束时刻di。一个调度f的最大延迟是所有客户延迟时长的最大值maxiAf(i)+ti-di。附图2所示是不同调度下的最大延迟。使用贪心策略找出一个调度使得最大延迟达到最小。2设计思想：贪心思想，按照他们的截止时间从小到大排序，如果截止时间相同按照花费时间从小到大排序。然后按照f_min（所有客户延迟时长的最大值）=max(worksi.cost+time-worksi.deadline,f_min);寻找最所有客户延迟时长的最大值。3代码设计：/最小延迟调度问题/输入包含：任务，任务完成需要的时间，完成改任务的截止时间#include#include#include#includeusing namespace std;const int maxn=1000+10;int n;struct nodeint id;int cost;int deadline;worksmaxn;bool cmp(node a,node b)if(a.deadline!=b.deadline)return a.deadlineb.deadline; else return a.costb.cost;int dpmaxnmaxn;int main()while(scanf(%d,&n)!=EOF)for(int i=0;in;i+)scanf(%d,&worksi.cost);for(int i=0;in;i+)scanf(%d,&worksi.deadline),worksi.id=i+1;sort(works,works+n,cmp);int f_min=0;int time=0;for(int i=0;iworksi.deadline)f_min=max(worksi.cost+time-worksi.deadline,f_min);/coutf_minendl;time+=worksi.cost;printf(Maximum delay:n);printf(%dn,f_min);printf(Complete the order of tasks:n);for(int i=0;in;i+)coutworksi.id ;coutendl;return 0;/*样例输入：55 8 4 10 310 12 15 11 20*/运行结果：2.5 思考题（1）哈夫曼编码问题的编程如何实现？答：哈夫曼树，又名最优树，给定n个权值作为n的叶子结点，构造一颗二叉树，若带权路径长度达到最小，成这样的二叉树为最优二叉树，也称哈夫曼树。实现步骤：1、初始化: 根据给定的n个权值w1，w2,.wn.构成n棵二叉树的集合F=T1,T2.Tn,其中每棵二叉树中只有一个带权Wi的根结点，左右子树均空。2、 找最小树:在F中选择两棵根结点权值最小的树作为左右子树构造一-棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树，上根结点的权值之和。 3、删除与加入: 在F中删除这两棵树，并将新的二叉树加入F中。 4、判断:重复前两步(2和3)，直到F中只含有一棵树为止。该树即为哈夫曼树。（2）使用贪心策略求解背包问题。答：首先计算每种物品单位重量的价值viwi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未达到w，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去直到背包满重为止。算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O(nlogn)。（3）分析普里姆算法和克鲁斯卡尔算法中的贪心策略。答：1、普里姆算法贪心策略：要记录到S中的下一条边（u，v）是一条不在S中，且使得SUu,v的权值之和也是最小的边 时间复杂度：O(n2) 空间复杂度：O(n2)2、克鲁斯卡尔算法中的贪心策略：选取属于不同联通分量且构成权值最小且不形成回路的两个顶点组成的边、本科实验报告课程名称： 算法设计与分析 实验项目： 动态规划 实验地点： 计算机系实验楼110 专业班级： 物联网1601 学号： 2016002105 学生姓名： 俞梦真 指导教师： 郝晓丽 2018年 05月 07日实验三 动态规划算法3.1 实验目的与要求1理解动态规划算法的基本思想；2运用动态规划算法解决实际问题，加深对贪心算法的理解和运用。3.2 实验课时4学时（课内2学时+课外2学时）3.3 实验原理动态规划（Dynamic Programming）算法思想：把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解。动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始反复求解。动态规划求解问题的关键在于获得各个阶段子问题的递推关系式：（1）分析原问题的最优解性质，刻画其结构特征；（2）递归定义最优值；（3）自底向上（由后向前）的方式计算最优值；（4）根据计算最优值时得到的信息，构造一个最优解。3.4 实验题目1上机题目：最大子段和问题给定n个整数（可以为负数）组成的序列(a1,a2,an)，使用动态规划思想求该序列的子段和的最大值。注：当所有整数均为负整数时，其最大子段和为0。例如，对于六元组(-2, 11, -4, 13, -5, -2)，其最大字段和为：a2 + a3 + a4 = 20。除了动态规划，该问题可以使用顺序求和+比较（蛮力法）和分治法求解，思考其求解过程。2设计思想动态规划思想：dpi,表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值。状态转移方程：dpi=max(dpi,dpi-1+ai);3代码设计#include#include#include#includeusing namespace std;const int maxn=1000+10;int dpmaxn;int amaxn;/动态规划思想：dpi,表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值/dpi=max(dpi,dpi-1+ai);int main()int n;while(cinn)memset(dp,0,sizeof(dp);for(int i=0;iai,dpi=ai;int ans=0;for(int i=1;ians)ans=dpi;coutansendl;return 0;3.5 思考题（1）深刻理解动态规划与递归求解问题的区别是什么？、答：动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。（2）动态规划思想解题的步骤是什么？答：第一步：确定子问题。 在这一步重点是分析那些变量是随着问题规模的变小而变小的， 那些变量与问题的规模无关。 第二步：确定状态：根据上面找到的子问题来给你分割的子问题限定状态 第三步：推到出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件， 注意不要遗漏。 第四步：确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出， 如果不行也可以尝试从边界条件反推（举个例子：a(n)a(2)有递推关系， 但是a(2)a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)， 然后将递推的终点设置为a(2)）; 第五步：确定实现方式：这个依照个人习惯 就像是01背包的两层for循环的顺序 第六步：确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存）， 优先队列、四边形不等式（优化时间）等等。（3）动态规划思想和贪心算法在求解问题时的区别是什么？答：共同点: 求解的问题都具有最优子结构性质区别点:动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。（4）使用动态规划算法求解最长公共子序列（LCS）问题。答：LCS问题的最优子结构性质，得其状态转移方程或者说递归式： dpij 表示记录ai bj的LSC的长度 时间复杂度： O(m+n);ai=bj dpi-1j-1+1;ai!=bj max(dpi-1j,dpij-1);（5）使用动态规划算法求解最长最大字段和问题。答：动态规划思想：dpi,表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值。dpi=max(dpi,dpi-1+ai)本科实验报告课程名称： 算法设计与分析 实验项目： 回溯算法 实验地点： 计算机系实验楼110 专业班级： 物联网1601 学号： 2016002105 学生姓名： 俞梦真 指导教师： 郝晓丽 2018年 05 月 07 日实验四 回溯算法4.1 实验目的与要求1通过回溯算法的示例程序理解回溯算法的基本思想；2运用回溯算法解决实际问题，进一步加深对回溯算法的理解和运用。4.2 实验课时4学时（课内2学时+课外2学时）。4.3 实验原理回溯算法（Backtrack）的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯算法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯算法的基本步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：（1）用约束函数在扩展结点处剪去不满足约束的子树；（2）用限界函数剪去得不到最优解的子树。4.4 实验题目1上机题目：排兵布阵问题某游戏中，不同的兵种处于不同的地形上时，其攻击能力也一样，现有n个不同兵种的角色(1, 2, ., n)，需安排在某战区n个点上，角色i在j点上的攻击力为Aij，使用回溯法设计一个布阵方案，使总的攻击力最大。注：个人决定A矩阵的初始化工作。该问题求解算法的输入数据形如附图4所示。2设计思想：利用回溯法搜索寻找解空间树。深度优先搜索，设立访问标记进行剪枝，并将总共的攻击力作为参数不断传入。寻找最大的攻击力。数值的存储用的是二位数组，用ans_pos记录过程。3代码设计/角色i在j点上的攻击力为Aij#include#include#includeusing namespace std;const int maxn=100+10;int n,ans=0;int mapmaxnmaxn;bool vismaxn;int posmaxn,ans_posmaxn;void dfs(int cnt,int u)if(cnt=n)if(uans)ans=u;memcpy(ans_pos,pos,sizeof(pos);return;for(int i=0;in;i+)if(!visi)visi=1;poscnt=i+1;dfs(cnt+1,u+mapcnti);visi=0;int main()while(scanf(%d,&n)!=EOF&n)ans=0;for(int i=0;in;i+)for(int j=0;jn;j+)scanf(%d,&mapij);memset(vis,0,sizeof(vis);dfs(0,0);printf(Max ATC:%dn,ans);printf(Postion: );for(int i=0;in;i+)printf(%d ,ans_posi);printf(n);return 0;/*560 40 80 50 6090 60 80 70 2030 50 40 50 8090 40 30 70 9060 80 90 60 50*/运行结果：4.5 思考题（1）什么是启发式搜索问题？启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（2）搜索算法的解空间树的如何定义？答：解决一个问题的所有可能的决策序列就构成了该问题的解空间。通常将解空间画成树的形状，称为解空间树。（3）0-1背包问题的动态规划算法如何求解？答：声明一个 大小为 mnc 的二维数组，m i j 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 mij 的计算方法，（1） j =wi 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。状态转移方程：if(j=wi) mij=max(mi-1j,mi-1j-wi+vi);else mij=mi-1j;（4）n皇后问题使用回溯法如何求解？答：首先找出解空间：给棋盘的行和列都编上1到N的号码，皇后也给编上1到N的号码。由于一个皇后应在不同的行上，为不失一般性，可以假定第i个皇后将放在第i行上的某列。因此N皇后问题的解空间可以用一个N元组（X1，X2，.Xn）来表示，其中Xi是放置皇后i所在的列号。这意味着所有的解都是N元组（1，2，3，.，N）的置换。解空间大小为N！。其次我们看约束条件：因为解空间已经给我们排除了不在同一行（因为每个皇后分别已经对应不同的行号）的约束条件。我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号，所以第k个皇后和第i个皇后同列的判断条件是X（k）=X（i）。所以不同列的判段条件是X（k）！=X（i），1ki 。又因为同一斜线的特征是要么行号和列号之和不变（右高左低）要么是行号和列号只差相等（左高右低），所以第k个皇后和第i个皇后在同斜线的判断条件是 i+X（i）= k+X（k) 或 i-X(i) =k-X(k),两式合并得 |X(i)-X(k)|=|i-k| 。（5）使用回溯法求解装载问题。答：基本思路： 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。本科实验报告课程名称： 算法设计与分析 实验项目： 分支限界算法 实验地点： 计算机系实验楼110 专业班级： 物联网1601 学号： 2016002105 学生姓名： 俞梦真 指导教师： 郝晓丽 2018年 05 月 14 日实验五 分支限界算法5.1 实验目的与要求1通过分支限界算法的示例程序进一步理解分支限界算法的基本思想；2运用分支限界算法解决实际问题，进一步加深对分支限界算法的理解和运用。5.2 实验课时4学时（课内2学时+课外2学时）。5.3 实验原理分枝限界（Branch-and-Bound）算法是另一种系统地搜索解空间的方法，它与回溯算法的主要区别在于对E-结点的扩充方式。每个活结点有且仅有一次机会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出（最优）可行解的结点，其余结点加入活结点表，然后从表中选择一个结点作为下一个E-结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充过程才结束。有两种常用的方法可用来选择下一个E-结点（虽然也可能存在其他的方法）：（1）先进先出（F I F O）即从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同。（2）（优先队列）最小耗费（LC）或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活结点表可用最小堆来建立，下一个E-结点就是具有最小耗费的活结点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活结点表，下一个 E-结点是具有最大收益的活结点。5.4 实验题目1上机题目：运动员最佳配对问题羽毛球队有男女运动员各n人。给定两个nn矩阵P和Q；Pij表示男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势，Qij表示女运动员i和男运动员j配对组成混合双打的女运动员竞赛优势（注意：由于多种原因，Pij 未必等于Qji），男运动员i和女运动员j配对组成混合双打的男女运动员双方总体竞赛优势为Pij* Qji。用分支限界法设计一个算法，计算男女运动员的最佳配对，即各组男女运动员双方总体竞赛优势的总和达到最大。2设计思想对于n个男运动员，从第1个开始搭配女运动员：第1个有n种搭配方法，第2个有n-1种搭配方法第n个有n-(n-1)种搭配方法；根据问题给出的示例：输入n的值为3，表示男女运动员各有3名；男运动员 1 2 3按顺序搭配女运动员，他们分别对应的女运动员可以是：女运动员 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1所以其解空间是(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)，整个问题可看成是1,2,3的全排列问题，将解空间组织成一棵排列树。解空间树的第i层到第i+1层边上的标号给出了变量的值。从树根到叶的任一路径表示解空间中的一个元素。用LC分支界限法的搜索策略搜索整个解空间3代码设计/运动员最佳配对-效益最大/分支限界法#include#include#include#include#includeusing namespace std;const int maxn=100+10;int n;int pmaxnmaxn,qmaxnmaxn;int ans_xmaxn;int vismaxn;struct nodeint dep;int win;int *x;node(int d,int w)x=new i