《高级算法设计与分析》试卷及答案 卷2_第1页
《高级算法设计与分析》试卷及答案 卷2_第2页
《高级算法设计与分析》试卷及答案 卷2_第3页
《高级算法设计与分析》试卷及答案 卷2_第4页
《高级算法设计与分析》试卷及答案 卷2_第5页
已阅读5页,还剩5页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

PAGE6PAGE《高级算法设计与分析》期末试卷(试卷2)姓名:___________________学号:___________________要求:所有题目的解答均写在答题纸上,需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题(每题3分,共45分)下面问题不能用动态规划求解的是:A:0-1背包问题B:矩阵连乘问题C:两点之间最长路径问题D:最大子数组问题贪心算法能够获得最优解的是:A:旅行商问题B:0-1背包问题C:最大团问题D:最小生成树问题对如图所示的旅行商问题,用分支限界法求解时,其最优下界为:A:16B:18C:13D:15将下面非标准型的线性规划转化为标准型:B.C.D.线性规划问题如下,其对偶问题为:B.D.对于随机算法的描述,以下描述错误的是:A.算法运算很快B.算法有一定的概率产生错误的结果C.算法的输出是确定的D.随机快速排序的期望时间复杂度为O(nlogn)在随机快速排序算法中,设S(i)表示集合S中阶为i的元素,下面描述错误的是(注:j>i):只有S(i)和S(j)这两个元素其一被选为主元素的时候,他们才进行比较当元素S(k)(i<k<j)被选为主元素时,S(i)和S(j)肯定不会进行比较S(i)和S(j)比较的概率为:pij=2/(j-i+1)当元素S(k)(k>j)被选为主元素时,S(i)和S(j)肯定会进行比较以下对规约的描述错误的是:,如果B是P问题,则A一定也是P问题,如果A是NPC问题,则B一定也是NPC问题如果A问题可以归约为B问题,则A问题和B问题必须是一一对应关系规约函数必须是多项式时间复杂度的函数以下问题不是NPC问题的是:A.小数背包问题B.最大团问题C.旅行商问题D.整数规划问题在团问题的NP难证明过程中,以下说法错误的是:3合取范式可以归约为团问题归约的过程中,3合取范式会归约为一个特殊的图,所以我们只能说明这个特殊的图的团问题是NP难的,而无法证明所有的图的团问题都是NP难的在规约的过程中,一个子句对应一组顶点,对于任意两个在不同组的顶点,如果满足“这两个顶点不是‘否’的关系”这一条件,就用一条边连接如果3合取范式如果有k个子句,则需要证明图中有规模为k的团针对集合覆盖问题,设wi为子集Si的权重,xi=0表示没有选中子集Si,xi=1表示选中子集Si。则集合覆盖问题建模成整数规划形式为(注:n为元素的个数,m为子集的个数):B.C.D.下面对旅行商问题(满足三角不等式)的近似算法描述错误的是:算法的基本思想是:生成最小生成树,按对树进行先序遍历的顺序访问节点。最小生成树的总代价小于等于旅行商回路的总代价对T进行按先序往返遍历,其总代价小于等于2倍的旅行商回路的总代价算法的总代价大于等于对T进行按先序往返遍历的总代价下面对在线算法和离线算法比较,以下描述错误的是:即使数据在计算时都已知,也可以采用在线算法来达到更好的结果在线算法通常是近似算法通常通过和离线最优算法的比较来判断在线算法的好坏,如果在线算法的代价Con和离线算法的代价Coff有关系,则称在线算法在实例IA上为α竞争度算法最小生成树在线算法可通过贪心算法实现在租卖问题的在线算法中,b=2为购买价格,l<=3为天数,则所有的确定性算法如下表,其中Ai为第i天购买,Ii为滑雪场最后一天开放为第i天,其中错误的是:最好的确定性算法为A2和AØ,都是3/2竞争度在线算法中,以1/3的概率执行A1策略,2/3的概率执行A2策略,可以实现竞争度4/3在线算法中,以2/3的概率执行A1策略,1/3的概率执行A2策略,也可以实现竞争度4/3本例子在线算法的最优竞争度为4/3下面对禁忌表搜索(Tabusearch)算法描述错误的是:算法的基本思想是标记已经解得的局部最优解或求解过程,并在进一步的迭代中避开这些局部最优解或求解过程那些目前在禁忌表的解或者求解过程是无条件被禁止的进入禁忌表的解或者求解过程在一定的时间后会被解禁禁忌表搜索每次迭代总是在前一次迭代的领域中进行搜索二、计算、建模题(共40分)设某指派问题的费用矩阵为:其中第i行表示第i个人被指派各个任务的费用,而第j列第j个任务被分配到各个人的费用。试用匈牙利法求最优指派,以及在最优指派下的总费用。(10分)已知下面的线性规划问题,其对偶问题的最优解为y*=(y1,y2)=(4,1),试用对偶的互补松弛性求原问题的最优解(10分)集合覆盖的问题如下:X为元素的集合,Si为X的一个子集,F为Si的集合,集合覆盖就是找到F的一个最小子集C,使得X中的所有元素都C覆盖。试证明集合覆盖是NPC问题(10分)简单描述如何用遗传算法实现广义旅行商问题的求解,描述要包含个体(染色体)设置,适应度函数定义,选择算子,交叉和变异操作(10分)三、算法设计题(共15分)1.0-1背包问题:设有n个物品,其重量为w1,w2,…,wn,价值为v1,v2,…,vn,背包的承重为C(wi<C)。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大。请用近似算法求解此问题(描述此算法的思路),并计算此算法的复杂度和近似度。《高级算法设计与分析》期末试卷答案(答案)姓名:___________________学号:___________________要求:所有题目的解答均写在答题纸上,需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题(每题3分,共45分)C,D,A,B,CC,D,C,A,BA,D,A,C,B二、计算、建模题(共40分)设某指派问题的费用矩阵为:其中第i行表示第i个人被指派各个任务的费用,而第j列第j个任务被分配到各个人的费用。试用匈牙利法求最优指派,以及在最优指派下的总费用。解:将每行减去最小值得到:每列减去最小值得到:将所有还没有被划线覆盖的元素减去最小值由以上矩阵可知:任务3指派给人员1;任务1指派给人员3;任务2指派给人员2;最下总费用为:7+10+9=26已知下面的线性规划问题,其对偶问题的最优解为y*=(y1,y2)=(4,1),试用对偶的互补松弛性求原问题的最优解解:原问题的对偶问题为将(4,1)带入约束条件,1,2为严格不等式,所以X1=0,x2=0;有因为y1,y2>0,故约束条件解得x3=4,x4=4.集合覆盖的问题如下:X为元素的集合,Si为X的一个子集,F为Si的集合,集合覆盖就是找到F的一个最小子集C,使得X中的所有元素都C覆盖。试证明集合覆盖是NPC问题(10分)参考答案:1.顶点覆盖可归约为集合覆盖;2.顶点覆盖是NP问题。给定某个图G=(V,E)以及一个点集P,很容易在多项式时间内验证这个集合P是否覆盖图G中的所有边;3.归约证明:设G=(V,E)为图,另X=E,Si为顶点i所覆盖边的集合,F为Si的集合,则形成(X,F)的一个集合覆盖问题3.1图G具有大小为k的一个顶点覆盖P,因P中所有点覆盖图G中所有的边,所以P中点对应的Si必然覆盖X中的所有元素,也就是Si成的集合S必然会覆盖X中的所有边,所以S是(X,F)的一个大小为k的集合覆盖。3.2设S是(X,F)的一个大小为k的集合覆盖,则S中所有的集合必然覆盖X中的所有点,所以S所对应的点集合P必然覆盖G中所有的点,且S是一个规模为k的集合。4)简单描述如何用遗传算法实现广义旅行商问题的求解,描述要包含个体(染色体)设置,适应度函数定义,选择算子,交叉和变异操作(10分)参考答案:设有m个城市群,每个城市群只要访问其中一个城市即可,设T(i)代表第i个城市群中所有的城市1、染色体由头部和身体组成,如下图,其中头部(从1到m)表示在访问第i个城市群访问的具体城市(如头部的第i(1<=i<=m)个元素4,表示访问了第i个城市群中的第4个城市),身体(从m+1到2m)表示对城市群访问的顺利。随机初始化n个染色体。2、对n个染色体进行局搜索,即针对每个染色体,改变头部的值,使得在此染色体城市群访问顺序下,对每个城市群选择最优的城市。计算局部搜索后每个染色体的适应度值(这里我使用路径长度的倒数表示个体适应性);3、使用轮盘选择方式选择个体,形成父染色体;4、按照交叉概率,对父染色体的身体部分进行两两交叉生成n个染色体;6、对这n个染色体的身体部分按照变异概率进行变异;7、判断是否达到迭代次数,是,结束,返回最优解;否,转到第2步。三、算法设计题(共15分)0-1背包问题:设有n个物品,其重量为w1,w2,…,wn,价值为v1,v2,…,vn,背包的承重为C(wi<C)。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大。请问近似算法求解此问题,(描述此算法的思路),并计算此算法的复杂度和近似度.参考答案:算法:1.将所有的物品按照性价比排列2.按顺序考察物品,只要能够装入背包装入此物品,得总价值为V3.求vk=ma

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论