算法分析及设计期末

《算法分析及设计期末》由会员分享，可在线阅读，更多相关《算法分析及设计期末（4页珍藏版）》请在装配图网上搜索。

1、-1. 下面程序段的所需要的计算时间为 。int Ma*Sum(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;jsum)sum=thissum;besti=i;bestj=j;return sum;2. 有11个待安排的活动，它们具有下表所示的开场时间与完毕时间，如果以贪心算法求解这些活动的最优安排即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合，得到的最大相容活动子集合为活动 1，4，8，11 。1413121110987654fi1228

2、86535031Si1110987654321i3. 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来到达。4. 所谓最优子构造性质是指问题的最优解包含了其子问题的最优解。5. 回溯法是指具有限界函数的深度优先生成法。6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。7. 回溯法的算法框架按照问题的解空间一般分为子集树算法框架与排列树算法框架。8. 用回溯法解0/1背包问题时，该问题的解空间

3、构造为子集树构造。9.用回溯法解批处理作业调度问题时，该问题的解空间构造为排列树构造。10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入适宜的容：Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) b += pi/wi * cleft; return b;11. 用回溯法解布线问题

4、时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要O(L)时间。for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.ro

5、w) & (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 12. 用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时渐进时间上限Omn。Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(*j= =*k) return false;return true;13. 旅行售货员问题的解空间树是排列树。二、 证明题1. 一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题消耗1个单位时间。

6、再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得Tn的显式表达式为：试证明Tn的显式表达式的正确性。2. 举反例证明0/1背包问题假设使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解此题说明0/1背包问题与背包问题的不同。证明：举例如：p=7,4,4,w=3,2,2,c=4时，由于7/3最大，假设按题目要求的方法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2，3 个。3.求证

7、：O(f(n)+O(g(n) = O(ma*f(n),g(n) 。证明：对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。令c3=ma*c1, c2， n3 =ma*n1, n2，h(n)= ma*f(n),g(n) 。则对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 ma*f(n),g(n)= 2c3h(n)

8、= O(ma*f(n),g(n) .4. 求证最优装载问题具有贪心选择性质。最优装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。设集装箱已依其重量从小到大排序，(*1,*2,*n)是最优装载问题的一个最优解。又设。如果给定的最优装载问题有解，则有。证明：三、 解答题1. 机器调度问题。问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开场时间为si，完成时间为fi，si n) / 到达叶结点更新最优解best*,bestw;return; r -= wi;if (

9、cw + wi bestw) *i = 0; / 搜索右子树backtrack(i + 1); r += wi;5. 用分支限界法解装载问题时，对算法进展了一些改良，下面的程序段给出了改良局部；试说明斜线局部完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 参加活结点队列 if (i bestw & i 0 故Ew+rbestw总是成立。也就是说，此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找

10、到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。7. 最长公共子序列问题：给定2个序列*=*1,*2,*m和Y=y1,y2,yn，找出*和Y的最长公共子序列。由最长公共子序列问题的最优子构造性质建立子问题最优值的递归关系。用cij记录序列*i和Yj的最长公共子序列的长度。其中， *i=*1,*2,*i；Yj=y1,y2,yj。当i=0或j=0时，空序列是*i和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子构造性质可建立递归关系如下：在程序中，bij记录Cij的值是由哪一个

11、子问题的解得到的。（1） 请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。void LCSLength(int m，int n，char *，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函数LCS实现根据b的容打印出*i和Yj的最长公共子序列。请填写程序中的空格，以使函数LCS完成构造最长公共子序列的功能请将bij的取值与1中您填写的取值对应，否则视为错误。void LCS(int i，int j，char *，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，*，b); cout0 ) printf(%dn ,k); f(k-1); f(k-1); . z