算法设计与应用 试卷4答案

《算法设计与分析》试题A卷 第4页共4页试卷4答案选择题（共15小题，每小题3分，共45分）CABDBA/DBACDBAADD二、简答计算题(共4小题，共30分)1.Dijkstra算法主要应用于非负无权图的最短路径求解，Dijkstra无法在负权边的图上求最短路径，请给出一个存在负权边的无向图的具体例子（图中没有负环），用Dijkstra在此图中得出的最短路径会是错误的（6分）。解：如图所示3个节点v1，v2，v3，（v1，v2）的权重为2，（v1，v3）的权重为3，（v2，v3）的权重为-4，用Dijkstra得出v1到v2的最短路径为2，而实际上是-1。2.设A[1…n]是有n个不同数组成的无序数组，请用分治法求此数组的最大元素，要求给出递归代码，并请求算法的时间复杂度（7分）。解：1)（5分）MaxArray(A,i,j)Ifj-i<=1Returnmax{A[i],A[j]};ElseMax_1=MaxArray(A,i,(i+j)/2)/*更精确的写法是(i+j)/2向下取整Max_2=MaxArray(A,(i+j)/2+1，y)/*更精确的写法是(i+j)/2+1向下取整Returnmax{Max_1,Max_2}2)（2分）时间复杂度：T(n)=2T(n/2)+1=>T(n)=n3.给定图G=(V,E)，及初始节点s∈V，且对于任意节点u∈V，adj(u)表示u的邻节点集合。请给出一个广度优先搜索算法的变体，要求对任意v∈V，1）输出s到v的最短路径的跳数d(v)，2）从s到v跳数为d(v)的路径总数（请用伪代码或者代码描述，8分）。解：以下算法中，使用Li表示所有到s跳数为i的节点，dv表示节点s到v的最小跳数，kv表示节点s注：s到v最短路径的总数为前一跳最短路径总数之和。4.用分支限界法解决如下面所示n=4的0-1背包问题（背包容量为C=16），其中物品已经按照“单位重量价值”降序排列。要求1)给出限界函数;2)并画出搜索树，并对树中的每个节点给出编号（访问顺序）和上界；3）给出最优解和最优值。（9分）物品重量价值价值/重量11010010276393856744123参考答案1：1)（2分）限界函数：将背包中剩余容量全部装入第i+1个物品，ub=v+(C-w)2）（5分）3）（2分）取最大值，v=119,X=(0,1,1,0)参考答案2：1）限界函数：按小数背包贪心算法，up=v2）3）v=119,X=(0,1,1,0)三、综合分析题(2小题，共25分)参考答案:1）采用贪心算法求解，选择结束时间最早的课室作为贪心选择，具体描述为：a)按开始时间si从小到大对社团活动进行排序，该次序为各社团选择课室的次序；按结束时间fi从小到大对社团活动进行排序,由于课室时间由活动的结束时间决定，该次序也是课室的结束时间点。b)先为最早开始的社团活动打开一间课室，此时课室的最早结束时间为该活动的结束时间，然后遍历剩下的社团活动，对于每个活动，判断当前最早结束的课室内是否仍有活动（即课室的最早结束时间大于该活动的开始时间），如果有，打开一间新课室；如果没有，说明当前最早结束的课室能容纳当前的活动，更新课室的结束时间点，保证最早结束的课室最先开始下一个活动。2）要证明这个贪心解决方案是最优的，首先观察问题表现出最优子结构，即如果A是社团活动集合S对应的原问题的最优解，课室r1安排的社团活动集合为S1，则A'=A-{r1}是剩余活动集合S'=S-S1对应的子问题的最优解。用反证法证明：假设存在A''比A'所需的课室数更少，由于S'与S1不相容，那由A''和r1所构成解集合比A更优，与假设矛盾。其次，需要证明最优解包含贪心选择，即最优解A的某个活动a所选择的课室r^'不是结束时间最早的课室r，由于r的结束时间小于r^'，a能在r^'中进行，说明a必定能在r中进行，因此用r代替r^'的结果(A−{r^'})∪{r}仍是一个最优解，即最优解包含贪心选择。综上，该问题可用贪心算法求解，且将结束时间最早的课室为贪心选择能得到最优解。3）我们必须首先对社团活动按开始时间和结束时间进行排序，所以运行时间复杂度为O(nlogn)。2.参考答案：1）另Cx,y为从左至右第x列，从上至下第y行的格子中的硬币价值，OPTx,