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

PAGEPAGE6《高级算法设计与分析》期末试卷答案（试卷4）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共42分）B，D，A，A，C；D，C，B，B，D；A，B，D，C二、计算、简答题（共42分）求如下线性规划的对偶问题(6分) 请用原始-对偶算法求图中的顶点覆盖近似解，写成具体的流程，如流程中涉及随机选择某个节点或者某条边，可做假设。（8分）解：答案做参考，随机选择的边不一样，导致过程不相同和结果不一致。LPA算法对图进行社群划分，设节点的遍历顺序为v4，v6，v1，v3，v7，v10，v8，v2，v9，v5。(注意：如需要，可做假设，8分)答：各个节点v4，v6，v1，v3，v7，v10，v8，v2，v9，v5的标签为第一轮后：5，5，3，3，9，9，9，3，9，5第二轮后：5，5，3，3，9，9，9，3，9，5结束装箱问题:设有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分）参考答案:算法:将物品按顺序放入箱子,具体放法如下:如果第一个箱子能够放此物品,则放,否则考察一下一个箱子,如果已打开的所有箱子都不能放,则新开一个箱子。应用算法得出结果如下:•箱子1:0.4，0.5，0.1•箱子2:0.8，0.1•箱子3:0.7，0.2•箱子4:0.6，0.4•箱子5:0.2设C∗为最优个数,此算法得出的箱子个数为C。则至少C−1个箱子是超过一半容量的(因算法不可能会得出同时两个箱子少于一半容量,否则算法会将这两个箱子合并)，可得:集和对半分问题：给出一个正整数的集合{a1,a2,…,an}，问是否可以将集合的元素分成两部分P和Q，使得P集合中所有元素之和等于Q集合中所有元素之和。1）请证明该问题是NPC问题（注：PPT上的所有NPC问题都认为是已知的）；2）请设计一个近似算法求解集合对半分问题。（10分）答：1）集合对半分问题就是求子集和问题，即求（a1+a2+…+an）/2的子集和。因子集和是NPC问题，所以集合对半分也是NPC问题。2）可以按照ppt上的消除相近元素的方法求解近似结三、算法设计题（共16分）1.广义旅行商问题：是指某些城市只要访问其中任意一个即可。如有n个城市，某采购员需要采购m(m<n)件物品，每个城市刚好提供一件物品，所以存在某些城市提供相同的物品，因此，采购员只要访问这些城市中的一个即可。请用遗传算法实现广义旅行商问题的求解，算法社交要包含个体(染色体)设置，适应度函数定义，选择算子，交叉和变异操作。参考答案:设有m个城市群，每个城市群只要访问其中一个城市即可，设T(i)代表第i个城市群中所有的城市。1)染色体由头部和身体组成，如图20，其中头部(从1到m)表示在访问第i个城市群具体城市(如头部的第i(1≤i≤m)个元素4，表示访问了第i个城市群中的第4个城市)，身体(从m+1到2m)表示对城市群访问的顺利。随机初始化n个染色体。图：广义旅行商遗传算法2)对n个染色体进行局搜索，即针对每个染色体，改变头部的值，使得在此染色体城市群访问顺序下，对每个城市群选择最优的城市。计算局部搜索后每个染色体的适应度值(这里使用路径长度的倒数表示个体适应性)。3)使用轮盘选择方式选择个体，形成父染色体。4)按照交叉概率