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

PAGE6PAGE《高级算法设计与分析》期末试卷（试卷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）如果替换成最短路径后生成的图不