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

PAGEPAGE6《高级算法设计与分析》期末试卷答案（答案）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题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+v