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

PAGEPAGE6《高级算法设计与分析》期末试卷（试卷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′