算法分析及设计期末

1. 下面程序段的所需要的计算时间为（

O(n2) ）。

2.

int MaxSum(int n, int *a, int &besti, int &bestj) { int sum=0; for(int i=1;i<=n;i++){ int thissum=0; for(int j=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } return sum; } 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。

i S[i] f[i]

1 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 2 13

11 12 14

3. 4. 5.

所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。 回溯法是指（具有限界函数的深度优先生成法）。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。 7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。 8. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。 9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。

10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的容：

...

Typep Knap::Bound(int i) {// 计算上界 Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 结点的上界 // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } // 装满背包 if (i <= n) （b += p[i]/w[i] * cleft）; return b; } 11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为n?m的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。

for (int i = 0; i < NumOfNbrs; i++) {

nbr.row = here.row + offset[i].row;

nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 该方格未标记 grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布线 Q.Add(nbr);} 12. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐 } 进时间上限）（O（mn））。

13. 旅行售货员问题的解空间树是（排列树）。

Bool Color::OK(int k) {// for(int j=1;j<=n;j++) if((a[k][j]= =1)&&(x[j]= =x[k])) return false; return true; } 二、 证明题

...

1. 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用

T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：T(n)O(1)n?1? ???kT(n/m)?f(n)n?1通过迭代法求得T（n）的显式表达式为：

T(n)?nlogmk?logmn?1?j?0kjf(n/mj)

试证明T（n）的显式表达式的正确性。

2. 举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。

证明：举例如：p={7,4,4},w={3,2,2},c=4时，由于7/3最大，若按题目要求的方法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2，3 个。

3.求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。

证明：对于任意f1(n)? O(f(n)) ，存在正常数c1和自然数n1，使得对所有n

类似地，对于任意g1(n)

?n1，有f1(n)? c1f(n) 。

? O(g(n)) ，存在正常数c2和自然数n2，使得对所有n?n2，有g1(n) ?c2g(n) 。

令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。 则对所有的 n

? n3，有

f1(n) +g1(n)

? c1f(n) + c2g(n) ? c3f(n) + c3g(n)

= c3(f(n) + g(n))

? c32 max{f(n),g(n)}

= 2c3h(n) = O(max{f(n),g(n)}) .

4. 求证最优装载问题具有贪心选择性质。

（最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装

载体积不受限制的情况下，将尽可能多的集装箱装上轮船。设集装箱已依其重量从小到大排序，(x1,x2,…,xn)是最优装载问题的一个最优解。又设k） ?min{i|xi?1}。如果给定的最优装载问题有解，则有1?k?n。

1?i?n...