算法分析与设计作业参考答案

1、算法分析与设计作业参考答案作业一一、名词解释：1 .递归算法：直接或间接地调用自身的算法称为递归算法。2 .程序：程序是算法用某种程序设计语言的具体实现。二、简答题：1 .算法需要满足哪些性质？简述之。算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。2）输出：算法产生至少一个量作为输出。3）确定性：组成算法的每条指令清晰、无歧义。4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2 .简要分析分治法能解决的问题具有的特征。分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小

2、的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。3 .简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2）用递推来实现递归函数。3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。三、算法编写及算法

3、应用分析题:1 .冒泡排序算法的基本运算如下:fori-1ton-1doforj-1ton-idoifaj<aj+1then交换aj、aj+1;分析该算法的时间复杂性。解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。1）设比较一次花时间1;(n i)i)殳n 1)2）内循环次数为：n-i次，（i=1,n）,花时间为：1nj13）外循环次数为：n-1,花时间为：T（n）（n2 .设计一个分治算法计算一棵二叉树的高度。i1解答：算法思想：对于二叉树T,若为空树，则其高度为0;否则，分别求其左子树和右子树的高度，最大者加1即为树T勺高度。其描述如下：in

4、tBTLength（BTT）/为了便于描述，假定二叉树类型为BT。T的左子树为T.lchild,右子树为T.rchildif(T=NULL)return0;/T为空树returnmax(BTLength(T.lchild),BTLength(T.rchild)+13 .设计一个分治算法来判定给定的两棵二叉树T1和T2是否相同。解答：算法思想：对于两棵二叉树T1和T2,若其根结点值相同，且其左右子树分别对应相同，则T1=T2;否则T1WT2。其描述如下：booleanBTEQUAL(BTT1，BTT2)/为了便于描述，假定二叉树类型为BT。二叉树T的左子树为T.Ichild,右子树为T.rchi

5、ld。二叉树T的根结点值T.data。if(T1=NULL&&T2=NULL)returnTrue;/均为空树if(T1&&T2&&T1.data=T2.data&&BTEQUALT(1.lchild,T2.lchild)&&BTEQUAL(T1.rchild,T2.rchild)returnTrue;returnFalse;4 .给出一个分治算法来找出n个元素的序列中的第2大元素，并分析算法的时间复杂度。解答：算法思想：当序列A1.n中元素的个数n=2时，通过直接比较即可找出序列的第2大元素。当n>2时，先

6、求出序列A1.n-1中的第1大元素x1和第2大元素x2；然后，通过2次比较即可在三个元素x1x2和An中找出第2大元素，该元素即为A1.n中的第2大元素。算法描述如下：SecondElement(Alow.high,max1,max2)/假设主程序中调用该过程条件为high-low>=2if(hight-low=2)if(Alow<Ahight)max2=Alow;max1=Ahigh;elsemax2=Ahigh;max1=Alow;elseSecondElement(Alow.high,x1,x2);if(x1<=An)max2=max1;max1=An;elseif(x

7、2>=An)max2=x2;max1=x1;elsemax2=An;max1=x1;该算法的时间复杂度满足如下递归方程：T(n)=T(n-1)+2；T(2)=1。解得T(n)=2n-3。作业二一、名词解释：1、MST性质：G=(V,E)是连通带权图，U是V的真子集。如果(u,v)巳且uU,vV-U,且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质称为MST性质。2、子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。二、简答题：1、简述动态规划算法求

8、解的基本要素。动态规划算法求解的基本要素包括：1)最优子结构是问题能用动态规划算法求解的前提；2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。2、备忘录方法和动态规划算法相比有何异同？简述之。备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构

9、相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。3、贪心算法求解的问题主要具有哪些性质？简述之。贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。三、算法编写及算法应用分析题：1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。最大子段和问题：给定由n个整数(可能为负整数)组成的序列a1a2an,求该序列形如2i<k<jak的子段和的最大值。当所有整数均为负整数

10、时定义其最大子段和为0。依次定义，所求的最优值为max0,maxiwiwjwnNiwkwjak。解答：下面给出求解该问题的动态规划算法中的递推计算公式。记b(j)=max1<i<j2i<k<jak,iwjwn,则所求最大子段和为maxiwjwnb(j)。而计算bj的递推计算公式为：b(0)=0，b(j)=maxb(j-1)+aj,aj,iwjwn。该算法的时间复杂度为O(n);空间复杂度为O(n)。2、关于多段图问题。设G=(V,E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi：1ik,其中，Vi和Vk分别只有一个顶点s(称为源)和一个顶点t(称为

11、汇)，图中所有的边(u,v),uVi,vMi。求由s到t的最小成本路径。a) 给出使用动态规划算法求解多段图问题的基本思想。b) 使用上述方法求解如下多段图问题。V1V2V3V4V57,7 29,67,1024,126 : 9516,2/3彳 3s 17318,8115,101142,12 41,122 12 t111解：(1)基本思想：设P(i,j)是从Vi中的节点j到汇点t的最小成本路径，Cost(i,j)是其成本。则C0st0Amimc(j,h)+C0st(i+1,h)|hVi+1,(j,h)E。边界条件是(1)若八工,则cost(h,t)=0；(2)cost(k-1,j)=c(j,t)

12、°(2)求解过程可以表示为:V1V2V3V4V5其中每个节点标示的序偶(p,q)中，p表示节点到t的成本，q表示后继节点的编号。从而，最优路径为:1271012和1361012,成本为16。3、最优二元归并问题：已知将两个分别包含a个和b个记录的已分类文件归并在一起得到一个分类文件需作a+b次记录移动。现有n个已分类文件F1,F1,?,Fn,它们的记录个数分别为l1,l2,?,ln。现在考虑使用二元归并模式将这n个文件归并成一个分类文件，要求记录移动次数最少。设计一个贪心算法来求解一种最优的二元归并(即记录移动次数最少的二元归并)。解答：(1)贪心准则：依次将文件序列中记录最少的两个

13、文件进行归并成一个文件，直到文件序列中只剩下一个文件为止。(2)贪心算法：AlgorithmBINARYTREE输入：n个单结点二元树列表L,这些棵树的根结点的权分别为l1,l2,?,lno输出：一棵最优二元归并树LBeginFori-1Ton-1DoGETNODE(T)/该过程产生一个新结点TLCHILD(T)-LEAST(L)将表L中其根权最小的树取出并作为T的左孩子RCHILD(T)-LEAST(L)将表L中其根权最小的树取出并作为T的右孩子WEIGHT(T)-WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T)RepeatReturn(L)End.4、带限期的作业调度问题

14、：n个作业需要在一台机器上处理，每个作业可在单位时间内完成。每个作业i都有一个截止期限di>0(di为整数)，当且仅当作业i在它的截止期限之前被完成，获得pi>0的效益。一种可行的调度方案为n个作业的一个子集J，其中J中的每个作业都能在各自的截止期限内完成。该可行调度方案的效益是J中作业的效益之和。试设计贪心算法求效益最大的可行调度方案(即最优调度方案)。解答：(1)贪心准则：从J=开始，不断添加作业到J中。每次加入J的作业是保证J是可行的前提下使得J中效益达到最大。即，按照pi由大到小的次序来考虑作业。(2)贪心算法：AlgorithmJOBSCHEDULE输入：n个作业的截至期

15、限d1,d2,?,dn和相应的效益值p1,p2,?,pn。输出：效益最大可行调度方案J(作业子集)Begin将作业按照效益值排序使得p1>p2>?>pn,相应的截至期限为d1,d2,?,dn。J=1Fori2TonDoIf(JUi中所有作业都能在它们的截至期限内完成)ThenJJUiEndifRepeatEnd.作业三一、名词解释：1. 多机调度问题：多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。2. 优先队列式分支限界法：优先

16、队列式分支限界法是将活结点表组织成一个优先队列，按照优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。二、简答题：1. 简述回溯法的基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2. 简要分析分支限界法与回溯法的异同。1)求解目标：回溯法的求解目标是找出解

17、空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2)搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。3. 常见的分支限界法有哪些？简述之。常见的两种分支限界法：1)队列式(FIFO)分支限界法：将活结点表组织成一个队列，并按照队列的先进先出(FIFO)原则选取下一个结点为扩展结点；2)优先队列式分支限界法：将活结点表组织成一个优先队列，按照优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。在优先队列式分支限界法中，一旦有一个叶结

18、点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。、算法编写及算法应用分析题：1.分派问题一般陈述如下：给n个人分派n件工作，把工作j分派给第i个人的代价是COST(,j)(非负实数)。要求设计一个回溯算法，在给每个人分派一件不同工作的前提下使得总代价最小。按照回溯法求解问题的基本步骤，请你完成几个任务：给出解的一般形式，写出解空间。以n=4为例画出表示解空间的状态空间树。并指出树中哪些结点是解结点？提出一个在深度优先搜索状态空间树时用于剪枝的剪枝函数(用文字描述)。解答：解的形式：(x1,x2,?,xn),其中xi=1,2,?,n表示给第i个人安排的工作号。解空间为(x1,x2,?

19、,xn)|xi=1,2,?,n,1wiwn。n=4的状态空间树为高度为4的满4叉树。图<略>。图中叶结点是解结点。剪枝操作有二。一是基于约束条件的剪枝操作：若当前给第i个人分配的工作号已被分配，则剪枝。另一个是基于目标值的剪枝操作：若当前给第i个人分配的工作号未被分配，但是目前已分配的总成本大于或者等于已有的某个分配方案的成本则剪枝。2.设计一个回溯算法来求解k-着色问题：给定无向图G=<V,E>,要求使用k种颜色来给图中每个结点着色(每个结点使用k种颜色之一)，使得没有两个相邻的结点颜色相同。给出解向量的形式，并画出当n=3,k=3时的搜索树。给出剪枝操作。最坏情况下

20、你的算法在搜索树上会生成多少个结点？分析算法的时间复杂度。解答：解向量的形式为(x1,x2,?,xn),其中xi=1,2,3表示图中第i个结点所着的颜色(iwiwn)。当n=3,k=3时搜索树为高度为3的满3叉树。剪枝操作如下：当搜索到结点X=(x1,x2,?,xi)时，如果图中第i结点所着色xi与前1,2,?,i-1结点所作的颜色无冲突，即图中这些结点中与结点i有边相连的结点所着颜色都不是xi,则不剪枝，否则剪枝(即搜索跳过对子树X的搜索)。该算法的最坏时间复杂度是与搜索树中结点个数和在每个结点处花费的时间都有关。搜索树中结点个数为O(kn),而在搜索中每个结点处花费的时间为O(n),因此最

21、坏时间复杂度是O(nkn)。3.对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。解：用Vi表示已经找到最短路径的顶点，V2表示与Vi中某个顶点相邻接且不在Vi中的顶点；Ei表示加入到最短路径中的边，E2为与Vi中的顶点相邻接且距离最短的路径。步骤V1V2E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,feab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,hab,bd,de,df