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

PAGEPAGE6《高级算法设计与分析》期末试卷答案（试卷1）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共45分）BCBAB；DCAAD；BDACD二、计算、建模题（共40分）已知线性规划问题,其对偶问题的最优解为*=(y1,y2,y3,y4)=(0,0,4,4)，试用对偶的互补松弛性求原问题的最优解（10分）min8x1+12x2s.t.2x1+2x2≥22x2≥1x1+x2≥5x1+2x2≥6x1,x2≥0解：此问题的对偶问题为将(0,0,4,4)带入约束条件，约束条件都为等式，无法得出解因y3和y4大于0，所以x1+x2=5x1+2x2=6解得x1=4；x2=1某市下设八个区,下表给出救护车从一个区到另外一个区的车程时间(min)。该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内（包括8min），问至少建多少个救护中心，建于何处（只需要建立模型，无需计算）？（10分）解：参考答案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，则两个顶点之间有边，否则无边，建立图如下则原问题建模为求解最小覆盖集问题参考3合取范式归约团问题的过程，证明最大独立集问题是NPC问题。最大独立集是给一无向图，找出一个点集，使得任意两点之间都没有连边，这个点集就是独立集。而点最多的独立集，就是最大独立集。(10分)参考答案1:1..最大独立集是NP问题:给定某个独立集，很容易在二项式时间内验证独立集合中的点是否在原图中存在连接.2.规约：将每个子句对应于一组节点组，其各个节点之间都有连线，而各组之间只有相互取反的节点有连线（刚好和团的规约相反），如3合取范式规约为：则取使得3合取范式为1的一个解，则必然存在一组独立集，如上例中（x反，z）使得3合取范式成立，则图中存在（x反，z，z，x反）的4各元素独立集。反之，如果图中国存在4个元素的独立集，对着4个元素对应的变量赋值为1，则3合取范式成立。参考答案2（通过顶点覆盖可归约为最大独立集问题）设G=(V，E)为图，k为顶点覆盖集，则|V|-k为图G的独立集。对于任意两个顶点不属于顶点覆盖集，则这两个顶点必然没有边，所有这些顶点两两之间都没有边，所以这些顶点形成了独立集(V-k)。同理，如果存在(V-k)的最大独立集，取独立集外的任意一个点，这个点至少存在一条边和顶点覆盖集中的一个点连接。所有的这些点将覆盖:1.这些点和独立集的边(这些边是独立的，也就是说不存在两个顶点覆盖同一条边);2.所有的边(因为独立集没有边，显然，所有独立集外的点将覆盖所有的独立集外的边，即所有的边)4）简单描述如何用遗传算法实现旅行商问题的求解，描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作（10分）解：程序流程（参考答案）1、根据输入的城市初始化个体（染色体），并生成n个个体，即初始种群；2、计算每个基因序列的适应性，适应性与路径长度成反比（这里我使用路径长度的倒数表示个体适应性）；3、使用轮盘选择方式选择个体，形成父本；4、按照交叉概率，对父本两两进行交叉生成n个个体；6、对这n个个体按照变异概率进行变异；7、判断是否达到迭代次数，是，结束，返回最优解；否，转到第2步。三、算法设计题（共15分）装箱问题:设有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)参考答案:算法:将物品按顺序放入箱子,具体放法如下:如果第一个箱子能够放此物品,则放,否则考察一下一个箱子,如果已打开的所有箱子都不能放,则新开一个箱子.应用