中南大学2014算法试卷及答案分析

中南大学考试试卷2013--2014学年下学期时间100分钟2014年6月6日算法分析与设计课程48学时3学分考试形式：闭卷专业年级：12级计算机、信安、物联本科生，总分100分，占总评成绩70%注：此页不作答题纸，请将答案写在答题纸上一、简答题（本题30分，每小题5分）1、陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义？1最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。意义：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长2平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。意义：在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准2、简单描述分治法的基本思想。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。3、何谓最优子结构性质？如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。4、何谓P、NP、NPC问题P(Polynomial问题)：也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。NPC(NPComplete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。5、试比较回溯法与分支限界法。1、引言1.1回溯法回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。1.2分支限界法分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树，在每一个活结点处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种方法称为分支限界法。2、回溯法的基本思想用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在组织解空间时常用到两种典型的解空间树，即子集树和排列树。确定了解空间的组织结构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。3、分支限界法的基本思想用分支限界法解问题时，同样也应明确定义问题的解空间。之后还应将解空间很好的组织起来。分支限界法也有两种组织解空间的方法，即队列式分支限界法和优先队列式分支限界法。两者的区别在于：队列式分支限界法按照队列先进先出的原则选取下一个节点为扩展节点，而优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。4、回溯法的设计原理在设计一个回溯算法时，通常按照以下步骤进行：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。在一般情况下用递归方法实现回溯法的基本框架如下：voidbacktrack（intt）{if（tn）output（x）；elsefor（inti=f（n，t）；i=g（n，t）；i++）{x[t]=h（i）；if（constraint（t）&&bound（t））backtrack（t+1）；}}其中：t表示递归深度，output（x）记录或输出得到的可行解x，f（n，t）和g（n，t）分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号，h（i）表示当前扩展结点处的第i个可选值，constraint（t）和bound（t）表示当前扩展结点的约束函数和限界函数。5、分支限界法的设计原理在设计一个分支限界算法时，通常按照以下步骤进行：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以广度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。6、回溯法与分支限界法的差异及应用回溯法与分支定界法都是在问题的解空间上搜索问题解的算法。但是两者是有区别的：首先，求解目标不同：一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是尽快地找出满足约束条件的一个解。其次，搜索方法不同：由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不同，回溯法采用深度优先方法搜索解空间，而分支限界法一般采用用广度优先或以最小耗费优先的方式搜索解空间。再次，对扩展结点的扩展方式不同：在搜索解空间书中两者的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在回溯法中，如果当前的扩展结点不能够再向纵深方向移动，则当前扩展结点就成为死结点，此时应回溯到最近的一个活结点处，并使此活结点成为扩展结点。而在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。最后，存储空间的要求不同：分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。下面结合具体的实例来说明何种情况下比较适合采用回溯法，何种情况下比较适合采用分支限界法：适合采用回溯法的问题：最典型的代表如n后问题，即在n*n个格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。对于n后问题，解与解之间不存在优劣的区别。必须要搜索到叶节点时才能确定出一组解。这种情况下，我们采用回溯法来解决时，采用排列树的解空间结构，在最坏的情况下，其堆栈的深度不会超过n。而采用分支限界法时，由于解之间不存在优劣关系，故不可能用限界函数剪枝，需要较大的存储空间。适合采用分支限界法的问题：最典型的代表如布线问题，即印刷电路板将布线区域划分成n*m个方格阵列。要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。此问题，如果采用回溯法来解决时，为了找到最短路径，必须把整个区域的所有路径逐一搜索后才能得到最优解，这使得算法效率较低。而如果用分支限界法来解决，则可以保证找到的解是最短的布线方案，因为如果存在一条由a至b的更短的路径，b结点一定会更早地被加入到活结点队列中并得到处理。6、贪心法是一种通过多步选择，试图获得最优解的方法。贪心法每次选择的原则是什么？请举例说明。设计贪心算法的三个步骤将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解（比较重要的一步）证明作出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的证明作出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构两个关键因素1.贪心选择性质：可以通过做出局部最优（贪心）选择来构造全局最优解；即每个步骤做出贪心选择能生成全局最优解【视不同具体问题进行证明，没有普遍适用的方法】2.最优子结构：一个问题的最优解包含其子问题的最优解经典最优化问题的两个变形0-1背包问题：一个正在抢劫的小偷发现了n个商品，第i个商品价值vi美元，重wi磅，vi和wi都是整数；小偷想尽可能拿走价值更多的商品，但是他的背包最多能容纳W磅的商品，W是一个整数【对每个商品，不能拿走一部分，要么完整拿走，要么留下）分数背包问题：条件和0-1背包问题一样，但对每个商品，小偷可以拿走一部分两个问题都有最优子结构，很相似，但是贪心算法可以求解分数背包问题，而不能求解0-1背包问题分数背包问题：计算每个商品的每磅价值vi/wi，每次选择每磅价值最高的商品即可0-1背包问题：因为小偷无法装满背包，空闲空间降低了方案的有效每磅价值；当我们考虑一个商品食肉装入背包，需要比较包含此商品的子问题的解和不包含它的子问题的解，然后才能做出选择当然，由于两个问题都有最优子结构，所以能用动态规划算法进行求解。////////////////////////////拓展////////////////////////////////////////////////////////////////////////////////////////////////////////二、简答题（本题25分，每小题5分）1、简单描述分治法的基本思想。2、简述动态规划方法所运用的最优化原理。3、何谓最优子结构性质？4、简单描述回溯法基本思想。5、何谓P、NP、NPC问题二、简答题（本题25分，每小题5分）1、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。2、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1kn，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。3、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。4、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。5、P(Polynomial问题)：也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。NPC(NPComplete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。//////////////////////////////////////////////////////////////////////////////二、选择题（14分，每题2分）1.下述表达不正确的是。A．n2/2+2n的渐进表达式上界函数是O(2n)B．n2/2+2n的渐进表达式下界