《高级算法设计与分析》试卷及答案 卷1

PAGEPAGE4《高级算法设计与分析》期末试卷（试卷1）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共45分）目前比较排序所能够达到的最优计算复杂度为：A：Θ(n)B:Θ(nlogn)C:Θ(n2)D:Θ(n2logn)哪两个算法需要最优子结构性质A:分治和动态规划B:分治和贪心C:动态规划和贪心D:动态规划和回溯线性规划的标准形式是：B.C.D.下列标准型化转化为松弛型:B.C.D.对于随机快速排序,以下描述错误的是:A.随机快速排序消除或减少了一般快速排序的最坏时间复杂度B.随机快速排序属于舍伍德算法C.随机快速排序的时间复杂度一定比一般快速排序的时间复杂度好D.随机快速排序的期望时间复杂度为O(nlogn)对于拉斯维加斯和蒙特卡洛算法描述错误的是:A.拉斯维加斯算法不一定获得解,但如果获得解一定是正确的B.蒙特卡洛算法可能给出错误解C.拉斯维加斯算法找到解得概率与算法执行时间成正比D.随机选择属于蒙特卡洛算法以下对规约的描述错误的是：，如果B是P问题，则A一定也是P问题，如果A是NPC问题，则B一定也是NPC问题，如果B是NP问题，则A一定也是NP问题L1代表A的算法,L2代表B的算法,则L1(x)=L2(f(x)),其中f为规约函数对NPC问题,以下说法正确的是：A.这个问题是一定是NP问题B.这个问题一定不是NP问题C.已经证明这个问题一定是P问题D.已经证明这个问题一定不是P问题以下问题不是NPC问题的是：A.欧拉回路问题B.最大团问题C.3合取范式D.0-1背包问题在团问题(图G)规约为顶点覆盖问题(图)中,以下说法错误的是：设（u,v）为的任意边，则（u，v）其中至少一个点不属于G的团设（u,v）为的任意边，则（u，v）其中至少一个点属于的顶点覆盖如果有两个顶点u,v都不属于的顶点覆盖，则这两个顶点一定属于G的团图G中有规模为k的团，当且仅当图有规模为k的顶点覆盖在旅行商问题的NP难证明过程中,以下说法错误的是：通常通过哈密顿回路来规约旅行商问题在规约的过程中,目的是找一条成本为n(n为边数)的旅行线路在规约的过程中,需要将原图扩展成一个完全图扩展成完全图后,原来的边设成本为0,扩展的边设成本为1下面对子集和的近似算法描述错误的是：如已知集合{x1,x2,x3,…,xi}所有的子集和Pi，则{x1,x2,x3,…,xi,xi+1}所有的子集和为。在计算过程中，为了减少子集和的规模，算法通过去除大于目标值的子集和，以及删除相似子集和的方法实现如果算法过程中，不删除相似的子集和（仅仅去除大于目标值的子集和），是可以得到精确的结果的子集和的近似算法只是一个多项式时间近似算法，而不是一个完全多项式时间的近似算法下面对在线算法和离线算法比较，以下描述错误的是：即使数据在计算时都已知，也可以采用在线算法来达到更好的结果在线算法通常是近似算法通常通过和离线最优算法的比较来判断在线算法的好坏，如果在线算法的代价Con和离线算法的代价Coff有关系，则称在线算法在实例IA上为α竞争度算法最小生成树在线算法可通过贪心算法实现下面对最小生成树在线算法描述错误的是：最小生成树在线算法是一种贪心算法算法复杂度为O（n2）算法竞争度为O（n）生成树在线算法生成树中第k长的边长度小于等于2l/k，其中l为最小生成树的代价下面对模拟退火描述错误的是：Greedy算法，但是加入随机因素若目标函数在第i+1步移动后比第i步更优，则总是被接受以一定的概率来接受一个比当前解要差的解，用于跳出局部最优解这个概率随着温度的降低，变的更大，以便更快的跳出局部最优解二、计算、建模题（共40分）已知线性规划问题,其对偶问题的最优解为*=(y1,y2,y3,y4)=(0,0,4,4)，试用对偶的互补松弛性求原问题的最优解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包括8min），问至少建多少个救护中心，建于何处（只需要建立模型，无需计算）？（10分）参考3合取范式归约团问题的过程，证明最大独立集问题是NPC问题。最大独立集是给一无向图，找出一个点集，使得任意两点之间都没有连边，这个点集就是独立集。而点最多的独立集，就是最大独立集。(10分)4）简单描述如何用遗传算法实现旅行商问题的求解，描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作（10分）三、算法设计题（共15分）装箱问题:设有n个物品,其大小为a1,a2,a3,…,an(0<ai<=1),现需要将这n个物品装入大小为1的箱子,求装完物品最少的箱子个数。此问题为NPC问题，请用近似算法求解(给出此算法的思路,并用算法来实现如下具体例子)，还需要计算此算法的精确度（α）.例子:10个物品其大小分别为(0.4,0.8,0.5,0.1,0.7,0.6,0.1,0.4,0.2,0.2)，这十个物品的标号分别为1，2，3…10，按照你设计的算法将这个10个物品放入箱子。《高级算法设计与分析》期末试卷答案（试卷1）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共45分）BCBAB；DCAAD；BDACD二、计算、建模题（共40分）已知线性规划问题,其对偶问题的最优解为*=(y1,y2,y3,y4)=(0,0,4,4)，试用对偶的互补松弛性求原问题的最优解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0解：此问题的对偶问题为将(0,0,4,4)带入约束条件，约束条件都为等式，无法得出解因y3和y4大于0，所以x1+x2=5x1+2x2=6解得x1=4；x2=1某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包括8min），问至少建多少个救护中心，建于何处（只需要建立模型，无需计算）？（10分）解：参考答案1:根据上表，如救护中心建在某区，其能覆盖的区域如下：1：1，2，72：1，23：3，4，5，64：3，4，5，65：3，4，5，66：3，4，5，6，87：1，78：6，8设：其中1表示设在某区，0表示不设则建模为：参考答案2:建立图：每个区域为一个顶点，如果区域之间的车程小于等于8min，则两个顶点之间有边，否则无边，建立图如下则原问题建模为求解最小覆盖集问题参考3合取范式归约团问题的过程，证明最大独立集问题是NPC问题。最大独立集是给一无向图，找出一个点集，使得任意两点之间都没有连边，这个点集就是独立集。而点最多的独立集，就是最大独立集。(10分)参考答案1:1..最大独立集是NP问题:给定某个独立集，很容易在二项式时间内验证独立集合中的点是否在原图中存在连接.2.规约：将每个子句对应于一组节点组，其各个节点之间都有连线，而各组之间只有相互取反的节点有连线（刚好和团的规约相反），如3合取范式规约为：则取使得3合取范式为1的一个解，则必然存在一组独立集，如上例中（x反，z）使得3合取范式成立，则图中存在（x反，z，z，x反）的4各元素独立集。反之，如果图中国存在4个元素的独立集，对着4个元素对应的变量赋值为1，则3合取范式成立。参考答案2（通过顶点覆盖可归约为最大独立集问题）设G=(V，E)为图，k为顶点覆盖集，则|V|-k为图G的独立集。对于任意两个顶点不属于顶点覆盖集，则这两个顶点必然没有边，所有这些顶点两两之间都没有边，所以这些顶点形成了独立集(V-k)。同理，如果存在(V-k)的最大独立集，取独立集外的任意一个点，这个点至少存在一条边和顶点覆盖集中的一个点连接。所有的这些点将覆盖:1.这些点和独立集的边(这些边是独立的，也就是说不存在两个顶点覆盖同一条边);2.所有的边(因为独立集没有边，显然，所有独立集外的点将覆盖所有的独立集外的边，即所有的边)4）简单描述如何用遗传算法实现旅行商问题的求解，描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作（10分）解：程序流程（参考答案）1、根据输入的城市初始化个体（染色体），并生成n个个体，即初始种群；2、计算每个基因序列的适应性，适应性与路径长度成反比（这里我使用路径长度的倒数表示个体适应性）；3、使用轮盘选择方式选择个体，形成父本；4、按照交叉概率，对父本两两进行交叉生成n个个体；6、对这n个个体按照变异概率进行变异；7、判断是否达到迭代次数，是，结束，返回最优解；否，转到第2步。三、算法设计题（共15分）装箱问题:设有n个物品,其大小为a1,a2,a3,…,an(0<ai<=1),现需要将这n个物品装入大小为1的箱子,求装完物品最少的箱子个数。此问题为NPC问题，请用近似算法求解(给出此算法的思路,并用算法来实现如下具体例子)，还需要计算此算法的精确度（α）.例子:10个物品其大小分别为(0.4,0.8,0.5,0.1