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

《高级算法设计与分析》期末试卷（试卷3）

姓名：学号：

要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号

一、选择题（每题3分，共45分）

1）求解整数规划，可通过先将整数规划进行松弛，之后采用下面的哪种算法:

A.动态规划B.分支限界C.回溯D.贪心

2）在近似算法中,可采用以下哪种算法：

A.动态规划B.分治C.回溯D.贪心

3）对于弱若对偶性,以下表达正确的是，x为原问题（最大化）的解，y为对偶问题

（最小化）的解：

〃八

mB.r

A.2>为“2〃』-工CjXjN**

j=lt=lJ=l;=l

-jn

C.£cjXj=£b*D.以上都不对

;=lf=l

4）线性规划问题如下，

max—2xi+3r2

s.t.—-2xi—勖=10

其对偶问题为：

X\—2g2—11

的>o

min-lli/2min10gi+llt/2

s.t.-2yl+血2-2s.t.-2yl+=-2

A.B.

-y\-2y2=3-yi—2g223

2/2<01/2<0

min10i/i-lll/2min10，l—1功2

s.t.—2yl—y2>—2〜s.t.—2Vl+=-2

A.D.

yi-2以=3-yi—2外N3

2/2<0?/2<0

5）下面描述正确的是：

A.整数规划问题是NPC问题，线性规划问题是NP问题

B.整数规划问题是NPC问题，线性规划问题是NPC问题

C.整数规划问题是NP问题，线性规划问题是NPC问题

D.整数规划问题是NP问题，线性规划问题是NP问题

6）设A问题可以归约到B问题，则以下说法错误的是：

A.如果A问题为NPC问题，则B问题必为NPC问题

B.A问题的任何一个实例x可以通过函数f转化为B问题的一个实例，且f为

多项式时间

c.B问题的任何一个实例X也可以通过函数「转化为A问题的一个实例，且r

为多项式时间

D.algoA代表A的算法,algoB代表B的算法,则algoB（f（x））=algoA（x）

7）在团问题（图G）规约为顶点覆盖问题（图6）中，以下说法错误的是：

A.设（u,v）为3的任意边，则（u,v）其中至少一个点不属于G的团

B.设（u,v）为不的任意边，则（u,v）其中至少一个点属于不的顶点覆盖

C.如果有两个顶点u,v都不属于3的顶点覆盖，则这两个顶点一定属于G的团

D.图G中有规模为k的团，当日.仅当图3有规模为k的顶点覆盖

8）下而对子集和的近似算法描述错误的足：

A.如已知集合｛XI,X2,X3,…,Xi）所有的子集和Pi,则｛XI,X2,X3,…,Xi,Xi+1｝所有的

子集和为”匕

B.在计算过程中，为了减少子集和的规模，算法通过去除大于目标值的子集和，

以及删除相似子集和的方法实现

C.如果算法不删除相似的子集和，是可以得到精确的结果的

D.子集和的近似算法只是一个多项式时间近似算法，而不是一个完全多项式时

间的近似算法

9）下面对旅行商问题（满足三角不等式）的近似算法描述错误的是：

A.算法的基本思想是:生成最小生成树，按对树进行后序遍历的顺序访问节点。

B.最小生成树的总代价小于等于旅行商回路的总代价

C.旅行商回路的总代价小于等于最小生成树代价的2倍

D.此近似算法是近似因子为2的近似算法

10）随机快速排序算法中，元素S⑴和元素S（j）进行比较的概率是多少（注：S为排序

好的元素序列）？

B.l/（j-/+l）B.C.D.2/（J-z+l）

11）对于拉斯维加斯和蒙特卡洛算法描述错误的是：

A.折斯维加斯算法不一定获得解，但如果获得解一定是正确的

B.蒙特卡洛算法可能给出错误解

C.拉斯维加斯算法找到解得概率与算法执行时间成正比

D.随机选择属于蒙特卡洛算法

12）G=（V,E）为多重图,C是最小割且|C|=k,以下描述错误的是：

A.G中任意顶点的度大于等于k

B.|E|>kn

C.最小割即为最少的变数集合，除去这些边数，原图变成不连通

D.随机算法输出最小割的概率大于2//

13)下面对最小生成树在线算法描述错误的是：

A.最小生成树在线算法是一种贪心算法

B.算法复杂度为O(n2)

C.算法竞争度为O(n)

D.生成树在线算法生成树中第k长的边长度小于等于2//k,其中/为最小生成树

的代价

14)在租卖问题的在线算法中，b=2为购买价格，1＜二3为天数，则所有的确定性算法

如下表，其中A为第i天购买，L为滑雪场最后一天开放为第i天，现有随机实

例概率(II=1/3J2=2/3)，以及随机算法概率(A2=2/3,A3=l/3),则在此随机实

例下A2的竞争度，以及此随机算法在实例12的竞争度分别为：

42434

Zi2111

Z21|11

1122

A.(4/3,5/3)B.(43,4/3)C.(5/3,4/3)D.(5/3,5/3)

15)下面对蚁群系统算法(AntColonySystem)描述错误的是：

A.采用利用和探索相结合，在利用时，选择最优路径，探索时，按选择概率选择

路径

B.全局更新只更新最优路径上的信息素

C.局部更新时，信息素并不挥发

D.在路径选择时，即考虑信息素，也考虑路径长度

二、计算、建模题(共40分)

1)设某指派问题的效率矩阵为:

20605055、

60308075

801009080

\65807570/

其中第i行表示第i个人被指派各个仟务的效率,而第j列第j个仟务被分配到各

个人的效率。试用匈牙利法求最大效率指派，以及在最大效率指派下的总费用。

(10分)

2)某市下设八个区，下表给出救护车从一个区到另外一个区的车程时间(min)。该市

拟建救护中心，要求各区离救护中心的车程时间必须在8min之内(包括8min),

问至少建多少个救护中心，建于何处？(只需要建立模型，不需要计算)

3）证明0・1整数规划问题是NPC问题（提示可以用3合取范式的可满足性问题归

约为0-1整数规划问题），需要描述一个具体的3合取范式实例转换为具体的0-

1整数规划问题实例。（10分）

4）简单描述如何用遗传算法对下面优化问题进行求解，要求精度达到小数点后5位,

描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作

（10分）

maxx-sm（107r•n）+5

s.t.2>x>—2

三、算法设计题（共15分）

1.斯坦纳最小树的定义如下：给定无向连通图G=（V,E）和边的权重w:E-R。同

时，给出集合R为V的子集，Rev,要求在图中寻找一棵子树T=（Vf,EZ）,其

中V'cv,E'CE,使得RGV',且EeeEw（e）最小。在下面的左图中，顶点

（a,b,c,d）的斯坦纳最小树如右图所示。斯坦纳最小树是NP难问题，请设计一个近

似算法求解（10分），并计算近似因子（5分）。

《高级算法设计与分析》期末试卷答案（试卷3）

姓名：学号:

要求：所有题目的解答均写在答题纸上，需写清楚题目序号。每张答题纸都要写上姓名和学号

一、选择题（每题3分，共45分）

BDAAACDDADDBCBC

二、计算、建模题（共40分）

5）设某指派问题的效率矩阵为：

/20605055\

60308075

801009080

\65807570/

其中第i行表示第i个人被指派各个任务的效率，而第j列第j个任务被分配到各

个人的效率。试用匈牙利法求最大效率指派，以及在最大效率指派下的总费用，

（10分）

解：

将这个效率矩阵的北大元素加〃减去这个矩阵的每个元素，得轲新的矩阵为：

r80405045、

40702025

2001020

、35202530；

针对这个矩阵求最小化指派。将每行每列减去最小值得到:

-15-0-0-5

-40/400105'(250100

0555000

=>

-02001020501015

-20150510,10055

此矩阵已经可以得出技优指派为：1.根据第S行，任务2分配给人贵3,酬除第

3行和第2列。2.根据第1ft,任务4分配给人员/,都除第1行和第4列。3.

根据第2行，任务8分纪给人员2,*除第2行和第3列。4-根据第4行，任务

/分纪给人员4・结合原始的效率矩阵，最大效率为：55+80+100+65=300.

6）某市下设八个区，下表给出救护车从一个区到另外一个区的车程时间（min）。该市

拟建救护中心,要求各区离救护中心的车程时间必须在8min之内（包括8min）,

问至少建多少个救护中心，建于何处？

2345678

189111314815

2101213111714

37781210

487109

581416

6107

712

解：

参考答案1:根据上表，如救护中心建在某区，其能覆盖的区域如下：

1：2,7

2：1,2

3：3,4,5,6

4：3,4,5,6

5：3,4,5,6

6：3,4,5,6,8

7：1,7

8：6,8

设：

其中1表示设在某区，0表示不设

则建模为：

十8

mmz=Z”

s.r.x]+x2>\

x3+x4+x5+x6>1

x3+x4+x5+.r6+Ag>1

xt+x7>\

%+玉之|

%W{O,1}

参考答案2:

建立图：每个区域为一个顶点，如果区域之间的车程小于等于Smin,则两个顶点之间有边，否则

无边，建立图如下

则原问题建模为求解最小覆盖集问题

7）证明0・1整数规划问题是NPC问题（提示可以用3合取范式的可满足性问题归

约为0-1整数规划问题，需要描述一个具体的3合取范式实例转换为具体的0-1

整数规划问题实例）。（10分）

证：1.0-1整数规划是NP问题：给定某个0-1整数规划的解，很容易在二项式时

间内验证这个解是否是0-1整数规划的解，即只要验证每个限制条件即可.

2.归约证明

•对于每个clause,我们都对应于ILP中的一^constraint,比如3SAT中有4个变量，x\,

X2,M和心，贝!JILP中也有同样的这4个变量，并且我们要求他们都是只能取0或1,对于

—^clause,如（xiV犬2VM3）,我们对应的constraint是

"1+（1—M）+（1—工3）=L很显然了，ILP中的变量选0对应于3SAT中的变量

选0,ILP中的变量选1对应于3SAT中的变量选1.

•3SAT问题（修Vi2Vi3）A（X!Vx2V&）对应的ILP如下:

(X1+(1-X2)+(1-X3)=1

IXI++大4=1

8）简单描述如何用遗传算法对下面优化问题进行求解，要求精度达到小数点后5位,

描述要包含个体（染色体）设置，适应度函数定义，选择算子，交叉和变异操作

（10分）

maxx-sin（IOTT•%）+5

s.t.2>x>—2

解：

a）需要将区间［-2,2］划分4x105等份，因为218<4X105<219,所以编码的长

度应该设置为m=19比特，染色体x如下所示：

12345678910111213M1516171819

0I1)1I0I1I00I11101I