算法分析与设计考前复习重点

1、个特性，程序与算法的算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：输入：有外部提供的量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。2算法分析是对算法所需要的两种计算机资源一时间和空间进行估算。3何谓递归？构成递归需具备的2个条件(要素)。递归(recursion)是数学与计算机科学中的基本概念。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数

2、。构成递归需具备的条件：不能无限制地调用本身，须有个出口，化简为非递归状况处理(边界条件或递归出口)；子问题与原问题为同一类型，且更为简单(递归模式或递归体).4、递归算法与非递归算法的优缺点优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便，是算法设计中的一种强有力的工具。缺点：递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。因此无论是耗赛的计算时间还是占用的存储空间都比非递归算法要多。5、利用分治法求解的问题一般应具有哪四个特征(即分治法的适用条件)。

3、该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有结构自相似性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。6、求解背包问题和0/1背包问题的约束条件有什么不同？7、动态规划法和分治法之间有什么共同点？有什么不同点？动态规划的实质是分治思想和解决冗余动态规划法与分治法类似，它们都是将问题实例归纳为更小的、相似的子问题，并 通过求解子问题产生一个全局最优解。分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子 问题的解后，便可自下而上地将子问题的

4、解合并成问题的解。不足之处：如果各子问题 是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈 现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时 加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。8、求解0/1背包问题的三种贪心策略（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选 择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个 数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入

5、尽可能多的物品，从而增加背包的总价值。 但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。9、简述动态规划法和贪心法之间的异同。动态规划算法与贪心算法比较，其相同点是：问题都应具有最优子结构的性质，都是将问题 的求解过程化为多阶段决策问题。区别是:贪心法每采用一次贪心策略便做出唯一决策，求解过 程只产生一个决策序列;求解过程为自顶向下，不一定得到最优解；动态规划的求解过程产生多 个决策序列，下一步的选择总是依赖上一步的结果，求解过程多为自底向上，总能得到最优

6、解。动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出 一系列的贪心选择。10、什么是最优子结构性质？动态规划法如何利用问题的最优子结构性质求解问题的最优解？（利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出 整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。）当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题 满足最优性原理。11、用动态规划法求解的问题应具有哪两个特征？1）满足最优子结构性质，即该问题的最优解中也包含着其子问题的最优解。2）待求解问题分解成若干个相互重叠的子问题12、利用贪心法

7、求解的问题具有的两个特征。（1）最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质：所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选 择，即贪心选择来得到。13、用回溯算法解决问题的时候一般步骤。1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用剪枝函数避免移动到不可能产生解的子空间。14、回溯法对解空间树的搜索过程中，采用的两种策略避免无效搜索。(1)用约束条件剪去得不到可行解的子树;(2)用目标函数剪去得不到最优解的子树。15、简述利用回溯

8、法对解空间树的搜索过程。回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至 树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的 界，也就是判断该结点是否包含问题的(最优)解，如果肯定不包含，则跳过对以该结点为 根的子树的搜索，即所谓剪枝(Pruning);否则，进入以该结点为根的子树，继续按照深度 优先策略搜索。16、回溯法求解问题时，常常遇到两种典型的解空间树，在用回溯法求解问题时，常常遇到两种典型的解空间树:(1)子集树(SubsetTrees):当所给问题是从n个元素的集合中找出满足某种性质的子集 时，相应的解空间树称为子集树。

9、在子集树中，|S1| = |S2|=. = |Sn|=c，即每个结点有相同数 目的子树，通常情况下c=2，所以，子集树中共有2n个叶子结点，因此，遍历子集树需要。(2n)时间。(2 )排列树(Permutation Trees):当所给问题是确定n个元素满足某种性质的排列时， 相应的解空间树称为排列树。在排列树中，通常情况下，|S1| = n , |S2| = n-1，|Sn| = 1 , 所以，排列树中共有n!个叶子结点，因此，遍历排列树需要Q (n!)时间。17,写出n=4时0-1背包问题的解空间。18、分治法：求解递归方程；动态规划：0-1背包问题和TSP问题填表；贪心法：（1 ）三种

10、贪心策略求解0-1皆包问题；（2）TSP问题的最近邻点贪心策略；（3 ）求最小生成树最近顶 点贪心策略；回溯法：0-1背包问题和TSP问题的解空间树或搜索空间树。回溯法01背包问题搜索树例如，对于n=3的0/1背包问题，三个物品的重量 为20, 15, 10，价值为20, 30, 25，背包容量为 25，从图所示的解空间树的根结点开始搜索，搜 索过程如下：不可行解价值=20 价值=55价值=30价值=25 价值=0回溯法tsp问题搜索树83671282886823768贪心法最近邻点贪心策略求tsp问题(1)最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一 个，直到经过了所有的

11、城市，最后回到出发城市。83 3 2 6387 3 23782 523 28362 5 38(a) 5城市的代价矩阵C=(b)城市1 城市4(c)城市4-城市3(d)城市3 -城市5(e) 城市5 -城市2(f) 城市2 -城市1最近邻点贪心策略求解TSP问题的过程最近顶点策略：任选一个顶点，并以此建立起生成树，每一步的贪心选择是简 单地把不在生成树中的最近顶点添加到生成树中。(a)连通网，U= A cost=( A, B )34,( A, C )46, (A, D)8 ,(A, E)8 ,(A, F)19 (b)U=( A, Fcost=( A, B )34, (F, C)25 ,F, D)

12、25,( F, E)26(U = A, F, C, D cost=( A, B )34, (F, E)26 U= A, F, C, D, E cost=(E, B )12 U= A, F, C, D, E, B cost= Prim算法构造最小生成树的过程示意注：cost表示候选最短边集0-1背包问题例如，有3个物品，其重量分别是20, 30, 10，价值分别为60,120, 50，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。10/2030TU(a)三个物品及背包(b)贪心策略 1(c)贪心策略2 (d)贪心策略 3动态规划tsp问题动态规划法求解TSP问题的填表过程

13、假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2 n-1 中，设数组 dn2 n-1存放迭代结果，其中dij表示从顶点i经过子集 Vj中的顶点一次且仅一次，最 后回到出发点 0的最短路径长度。（从顶点0出发） 1231, 21, 32, 31, 2, 30101586726951033121114厂83 6 782 34 823 7 58带权图的代价矩阵240-1背包问题例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。根据动态规划函数，用一个 (n+1) X (C+1)的二维表V，Vij 表示把前i个物品装入容量为j的背包中获得的最大价值。01