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

PAGE6PAGE《高级算法设计与分析》期末试卷（试卷4）姓名：___________________学号：___________________要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号一、选择题（每题3分，共42分）下列描述，错误的是：线性规划可在多项式时间内求解；0-1规划可在多项式时间内求解；整数规划采用的算法是分支限界线性规划具有强对偶性设X∗是线性规划模型的最优解，Y∗是其对偶线性规划模型的最优解，则X∗与Y∗的关系是：CX∗>BY∗B.CX∗=BY∗C.CX∗<BTY∗D.CX∗=BTY∗在用原始-对偶算法求解顶点覆盖的近似解时，会随机选择一条边，并增加此边的y值，直到此边两个顶点中，某个顶点的约束条件等号约束成立，假设两个顶点的约束条件的等号约束都成立，应该选择哪个顶点加入顶点覆盖集：两个顶点都加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除第一个约束条件对应的顶点加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除第一个约束条件对应的顶点加入顶点覆盖集，但只和该顶点相连的边从Ey中删除第二个约束条件对应的顶点加入顶点覆盖集，且和这两顶点相连的边都需要从Ey中删除下图从s到t的最大流是多少：A.8B.7C.6D.5下图节点1，2,3,4，的中介中心性：1，2.5，2，1.5;1，1.5，2，1;0，1.5，3，1;0，2.5，3，1.5;关于规约有下面三种陈述，则：(b)对(a),(c)错B.(a),(b)对，(c)错C.(b),(c)对，(a)错D.(a),(c)对，(b)错以下问题不是NPC问题的是：团问题B.子集和问题C.最大流问题D.0-1整数规划在满足三角不等式的情况下，设G为完全图，G’也是完全图，且是G的子图，以下的描述错误的是：图G的最小生成树的权重小于其旅行商回路的权重。图G的旅行商回路的权重大于对其最小生成树按照先序遍历形成的回路。图G的旅行商回路的权重小于等于其最小生成树权重的2倍图G′上的旅行商回路小于等于图G的旅行商回路请计算下图两个无权图的模块度：20/196,36/196B.24/196,40/196C.40/196,36/196D.24/196,36/196下面对集合覆盖的近似算法描述错误的是：简单集合覆盖的近似算法是贪心算法。该不等式成立是因为最优集合覆盖R*中包含所有的元素，且有可能对某个（些）元素包含多次。该不等式成立是因为贪心选择。该等式成立，说明近似算法覆盖所有的元素一次且仅一次。对于最小圆覆盖，以下说法错误的是：在最小圆覆盖算法中，当增加一个新的点pi时，如果点pi没有被当前圆所覆盖，则可以通过增大最小圆，将这个点包含在圆的内部。最小圆覆盖的随机算法是为了避免落入最差的情况。最小圆覆盖的最差情况下，复杂度为n3。最小圆覆盖的期望复杂度为n。对于弗里瓦德算法，下面描述错误的是：弗里瓦德算法是蒙特卡洛算法。弗里瓦德算法需要生成一个包含0,1元素的随机向量，如果生成的是全1元素，判断A*B*r=C*r重新变成了判断A*B=C，所以结果一定是正确的弗里瓦德算法得出正确解的概率大于等于1/2.随机算法输出最小割的概率大于2/n2对外汇兑换问题的在线算法描述错误的是：当Φ较大时（如>100）小数兑换能够比整数兑换得到更好的竞争度（更好收益）；按照小数保守价格策略，如果第一天就达到最高的汇率，则收益最好；按照小数保守价格策略，最后一天之前兑换的比例是固定的（无论汇率如何变动）只要知道U和L的比值Φ，可得的在线算法在租卖问题的在线算法中，b=2为购买价格，l<=3为天数，则所有的确定性算法如下表，其中Ai为第i天购买，Ii为滑雪场最后一天开放为第i天，现有随机实例概率（I2=1/3,I3=2/3），以及随机算法概率（A2=2/3，A3=1/3），则在此随机实例下A2的竞争度，以及此随机算法在实例I3的竞争度分别为：（2/3,5/3）B.（4/3,4/3）C.（3/2,5/3）D.（5/3,5/3）二、计算、简答题（共42分）求如下线性规划的对偶问题(6分) 请用原始-对偶算法求图中的顶点覆盖近似解，写出具体的流程，如流程中涉及随机选择某个节点或者某条边，可做假设。（8分）LPA算法对图进行社群划分，设节点的遍历顺序为v4，v6，v1，v3，v7，v10，v8，v2，v9，v5。(注意：如需要，可做假设，8分)装箱问题:设有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分）集和对半分问题：给出一个正整数的集合{a1,a2,…,an}，问是否可以将集合的元素分成两部分P和Q，使得P集合中所有元素之和等于Q集合中所有元素之和。1）请证明该问题是NPC问题（注：PPT上的所有NPC问题都认为是已知的）；2）请设计一个近似算法求解集合对半分问题（给出思路和流程即可）。（10分）三、算法设计题（共16分）1.广义旅行商问题：是指某些城市只要访问其中任意一个即可。如有n个城市，某采购员需要采购m(m<n)件物品，每个城市刚好提供一件物品，所以存在某些城市提供相同的物品，因此，采购员只要访问这些城市中的一个即可。请用遗传算法实现广义旅行商问题的求解，算法设计要包含个体(染色体)设置，适应度函数定义，选择算子，交叉和变异操作。。《高级算法设计与分析》期末试卷答案（试卷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