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

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