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

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,0.7,0.6,0.1,0.4,0.2,0.2)参考答案:算法:将物品按顺序放入箱子,具体放法如下:如果第一个箱子能够放此物品,则放,否则考察一下一个箱子,如果已打开的所有箱子都不能放,则新开一个箱子.应用算法得出结果如下:精确度:设C*为最优个数,此算法得出的箱子个数为C则至少C-1个箱子是超过一半容量的(因算法不可能会得出同时两个箱子少于一半容量,否则算法会将这两个箱子合并)所以为2近似算法。《高级算法设计与分析》期末试卷（试卷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=max{vi:foralli}，如vk>V，则将背包内的物品替换成物品k精确度:设最优算法得出的总价值为Vopt，贪心算法得出的总价值为Vgreedy，设l为第一件未装入背包的物品，因物品按照性价比排序，所以：Vopt<=Vgreedy+vl<=Vgreedy+vmax<=2Vgreedy所以为2近似算法。复杂度：第一步排序的复杂度为nlogn第二步装物品的复杂度为n第三步的复杂度为n总复杂度为nlogn《高级算法设计与分析》期末试卷（试卷3）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共45分）求解整数规划，可通过先将整数规划进行松弛，之后采用下面的哪种算法：动态规划B.分支限界C.回溯D.贪心在近似算法中，可采用以下哪种算法：动态规划B.分治C.回溯D.贪心对于弱若对偶性,以下表达正确的是，x为原问题（最大化）的解，y为对偶问题（最小化）的解：B.D.以上都不对线性规划问题如下，其对偶问题为：B.D.下面描述正确的是：整数规划问题是NPC问题，线性规划问题是NP问题整数规划问题是NPC问题，线性规划问题是NPC问题整数规划问题是NP问题，线性规划问题是NPC问题整数规划问题是NP问题，线性规划问题是NP问题设A问题可以归约到B问题，则以下说法错误的是：如果A问题为NPC问题，则B问题必为NPC问题A问题的任何一个实例x可以通过函数f转化为B问题的一个实例，且f为多项式时间B问题的任何一个实例x也可以通过函数f’转化为A问题的一个实例，且f’为多项式时间algoA代表A的算法，algoB代表B的算法，则algoB(f(x))=algoA(x)在团问题(图G)规约为顶点覆盖问题(图)中,以下说法错误的是：设（u,v）为的任意边，则（u，v）其中至少一个点不属于G的团设（u,v）为的任意边，则（u，v）其中至少一个点属于的顶点覆盖如果有两个顶点u,v都不属于的顶点覆盖，则这两个顶点一定属于G的团图G中有规模为k的团，当且仅当图有规模为k的顶点覆盖下面对子集和的近似算法描述错误的是：如已知集合{x1,x2,x3,…,xi}所有的子集和Pi，则{x1,x2,x3,…,xi,xi+1}所有的子集和为。在计算过程中，为了减少子集和的规模，算法通过去除大于目标值的子集和，以及删除相似子集和的方法实现如果算法不删除相似的子集和，是可以得到精确的结果的子集和的近似算法只是一个多项式时间近似算法，而不是一个完全多项式时间的近似算法下面对旅行商问题（满足三角不等式）的近似算法描述错误的是：算法的基本思想是：生成最小生成树，按对树进行后序遍历的顺序访问节点。最小生成树的总代价小于等于旅行商回路的总代价旅行商回路的总代价小于等于最小生成树代价的2倍此近似算法是近似因子为2的近似算法随机快速排序算法中，元素S(i)和元素S(j)进行比较的概率是多少（注：S为排序好的元素序列）？B.C.D.对于拉斯维加斯和蒙特卡洛算法描述错误的是:拉斯维加斯算法不一定获得解,但如果获得解一定是正确的蒙特卡洛算法可能给出错误解拉斯维加斯算法找到解得概率与算法执行时间成正比随机选择属于蒙特卡洛算法G=(V，E)为多重图，C是最小割且|C|=k，以下描述错误的是：G中任意顶点的度大于等于k最小割即为最少的变数集合，除去这些边数，原图变成不连通随机算法输出最小割的概率大于2/n2下面对最小生成树在线算法描述错误的是：最小生成树在线算法是一种贪心算法算法复杂度为O（n2）算法竞争度为O（n）生成树在线算法生成树中第k长的边长度小于等于2l/k，其中l为最小生成树的代价在租卖问题的在线算法中，b=2为购买价格，l<=3为天数，则所有的确定性算法如下表，其中Ai为第i天购买，Ii为滑雪场最后一天开放为第i天，现有随机实例概率（I1=1/3,I2=2/3），以及随机算法概率（A2=2/3，A3=1/3），则在此随机实例下A2的竞争度，以及此随机算法在实例I2的竞争度分别为：（4/3,5/3）B.（4/3,4/3）C.（5/3,4/3）D.（5/3,5/3）下面对蚁群系统算法（AntColonySystem）描述错误的是：采用利用和探索相结合，在利用时，选择最优路径，探索时，按选择概率选择路径全局更新只更新最优路径上的信息素局部更新时，信息素并不挥发在路径选择时，即考虑信息素，也考虑路径长度二、计算、建模题（共40分）设某指派问题的效率矩阵为：其中第i行表示第i个人被指派各个任务的效率，而第j列第j个任务被分配到各个人的效率。试用匈牙利法求最大效率指派，以及在最大效率指派下的总费用。（10分）某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包括8min），问至少建多少个救护中心，建于何处？（只需要建立模型，不需要计算）证明0-1整数规划问题是NPC问题（提示可以用3合取范式的可满足性问题归约为0-1整数规划问题），需要描述一个具体的3合取范式实例转换为具体的0-1整数规划问题实例。（10分）简单描述如何用遗传算法对下面优化问题进行求解，要求精度达到小数点后5位，描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作（10分）三、算法设计题（共15分）1.斯坦纳最小树的定义如下：给定无向连通图G=(V,E)和边的权重w:E→R。同时，给出集合R为V的子集，R⊆V，要求在图中寻找一棵子树T=(V′,E′)，其中V′⊆V，E′⊆E，使得R⊆V′，且∑e∈E′w(e)最小。在下面的左图中，顶点（a,b,c,d）的斯坦纳最小树如右图所示。斯坦纳最小树是NP难问题，请设计一个近似算法求解（10分），并计算近似因子（5分）。《高级算法设计与分析》期末试卷答案（试卷3）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共45分）BDAAACDDADDBCBC二、计算、建模题（共40分）设某指派问题的效率矩阵为：其中第i行表示第i个人被指派各个任务的效率，而第j列第j个任务被分配到各个人的效率。试用匈牙利法求最大效率指派，以及在最大效率指派下的总费用。（10分）解：某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包括8min），问至少建多少个救护中心，建于何处？解：参考答案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，则两个顶点之间有边，否则无边，建立图如下则原问题建模为求解最小覆盖集问题证明0-1整数规划问题是NPC问题（提示可以用3合取范式的可满足性问题归约为0-1整数规划问题，需要描述一个具体的3合取范式实例转换为具体的0-1整数规划问题实例）。（10分）证:1.0-1整数规划是NP问题:给定某个0-1整数规划的解，很容易在二项式时间内验证这个解是否是0-1整数规划的解，即只要验证每个限制条件即可.2.归约证明简单描述如何用遗传算法对下面优化问题进行求解，要求精度达到小数点后5位，描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作（10分）解：a)需要将区间[-2,2]划分4×105等份，因为218<4×105<219，所以编码的长度应该设置为m=19比特，染色体x如下所示：b)适应度函数f(x)为目标函数c)采用轮盘的方式进行选择，即pd)单点交叉和随机选择一个基因进行变异即可，但可能会产生非法解，对非法解可以直接去除。三、算法设计题（共15分）1.斯坦纳最小树的定义如下：给定无向连通图G=(V,E)和边的权重w:E→R。同时，给出集合R为V的子集，R⊆V，要求在图中寻找一棵子树T=(V′,E′)，其中V′⊆V，E′⊆E，使得R⊆V′，且∑e∈E′w(e)最小。在下面的左图中，顶点（a,b,c,d）的斯坦纳最小树如右图所示。斯坦纳最小树是NP难问题，请设计一个近似算法求解（10分），并计算近似因子（5分）。解：近似算法：1）基于原图G，生成R={a,b,c,d}的一个完全图GR，其中任意一条边的权重为原图G中的最短路径；2）基于GR，生成最小生成树TMST3）将TMST中的边替换成原来的最短路径T’MST4）如果替换成最短路径后生成的图不是树，则需进一步生成最小生成树，结果为近似算法的斯坦纳树TSMT。上面得出的近似算法是2-近似算法。由上面的流程可得：TSMT<T’MST<TMST<GR上的旅行商回路；设T*SMT是最优斯坦纳树，根据此树生成完全图GSMT，则：GR上的旅行商回路<GSMT上的旅行商回路且GSMT上的旅行商回路<2*T*SMT（旅行商回路<先序回路<2*T*SMT）所以TSMT<2*T*SMT《高级算法设计与分析》期末试卷（试卷4）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共42分）下列描述，错误的是：线性规划可在多项式时间内求解；0-1规划可在多项式时间内求解；整数规划采用的算法是分支限界线性规划具有强对偶性设X∗是线性规划模型的最优解，Y∗是其对偶线性规划模型的最优解，则X∗与Y∗的关系是：CX∗>BY∗B.CX∗=BY∗C.CX∗<BTY∗D.CX∗=BTY∗在用原始-对偶算法求解顶点覆盖的近似解时，会随机选择一条边，并增加此边的y值，直到此边两个顶点中，某个顶点的约束条件等号约束成立，假设两个顶点的约束条件的等号约束都成立，应该选择哪个顶点加入顶点覆盖集：两个顶点都加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除第一个约束条件对应的顶点加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除第一个约束条件对应的顶点加入顶点覆盖集，但只和该顶点相连的边从Ey中删除第二个约束条件对应的顶点加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除下图从s到t的最大流是多少：A.8B.7C.6D.5下图节点1，2,3,4，的中介中心性：1，2.5，2，1.5;1，1.5，2，1;0，1.5，3，1;0，2.5，3，1.5;关于规约有下面三种陈述，则：(b)对(a),(c)错B.(a),(b)对，(c)错C.(b),(c)对，(a)错D.(a),(c)对，(b)错以下问题不是NPC问题的是：团问题B.子集和问题C.最大流问题D.0-1整数规划在满足三角不等式的情况下，设G为完全图，G’也是完全图，且是G的子图，以下的描述错误的是：图G的最小生成树的权重小于其旅行商回路的权重。图G的旅行商回路的权重大于对其最小生成树按照先序遍历形成的回路。图G的旅行商回路的权重小于等于其最小生成树权重的2倍图G′上的旅行商回路小于等于图G的旅行商回路请计算下图两个无权图的模块度：20/196,36/196B.24/196,40/196C.40/196,36/196D.24/196,36/196下面对集合覆盖的近似算法描述错误的是：简单集合覆盖的近似算法是贪心算法。该不等式成立是因为最优集合覆盖R*中包含所有的元素，且有可能对某个（些）元素包含多次。该不等式成立是因为贪心选择。该等式成立，说明近似算法覆盖所有的元素一次且仅一次。对于最小圆覆盖，以下说法错误的是：在最小圆覆盖算法中，当增加一个新的点pi时，如果点pi没有被当前圆所覆盖，则可以通过增大最小圆，将这个点包含在圆的内部。最小圆覆盖的随机算法是为了避免落入最差的情况。最小圆覆盖的最差情况下，复杂度为n3。最小圆覆盖的期望复杂度为n。对于弗里瓦德算法，下面描述错误的是：弗里瓦德算法是蒙特卡洛算法。弗里瓦德算法需要生成一个包含0,1元素的随机向量，如果生成的是全1元素，判断A*B*r=C*r重新变成了判断A*B=C，所以结果一定是正确的弗里瓦德算法得出正确解的概率大于等于1/2.随机算法输出最小割的概率大于2/n2对外汇兑换问题的在线算法描述错误的是：当Φ较大时（如>100）小数兑换能够比整数兑换得到更好的竞争度（更好收益）；按照小数保守价格策略，如果第一天就达到最高的汇率，则收益最好；按照小数保守价格策略，最后一天之前兑换的比例是固定的（无论汇率如何变动）只要知道U和L的比值Φ，可得的在线算法在租卖问题的在线算法中，b=2为购买价格，l<=3为天数，则所有的确定性算法如下表，其中Ai为第i天购买，Ii为滑雪场最后一天开放为第i天，现有随机实例概率（I2=1/3,I3=2/3），以及随机算法概率（A2=2/3，A3=1/3），则在此随机实例下A2的竞争度，以及此随机算法在实例I3的竞争度分别为：（2/3,5/3）B.（4/3,4/3）C.（3/2,5/3）D.（5/3,5/3）二、计算、简答题（共42分）求如下线性规划的对偶问题(6分) 请用原始-对偶算法求图中的顶点覆盖近似解，写出具体的流程，如流程中涉及随机选择某个节点或者某条边，可做假设。（8分）LPA算法对图进行社群划分，设节点的遍历顺序为v4，v6，v1，v3，v7，v10，v8，v2，v9，v5。(注意：如需要，可做假设，8分)装箱问题:设有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}（10分）集和对半分问题：给出一个正整数的集合{a1,a2,…,an}，问是否可以将集合的元素分成两部分P和Q，使得P集合中所有元素之和等于Q集合中所有元素之和。1）请证明该问题是NPC问题（注：PPT上的所有NPC问题都认为是已知的）；2）请设计一个近似算法求解集合对半分问题（给出思路和流程即可）。（10分）三、算法设计题（共16分）1.广义旅行商问题：是指某些城市只要访问其中任意一个即可。如有n个城市，某采购员需要采购m(m<n)件物品，每个城市刚好提供一件物品，所以存在某些城市提供相同的物品，因此，采购员只要访问这些城市中的一个即可。请用遗传算法实现广义旅行商问题的求解，算法设计要包含个体(染色体)设置，适应度函数定义，选择算子，交叉和变异操作。。《高级算法设计与分析》期末试卷答案（试卷4）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，