算法复习提纲

《算法复习提纲》由会员分享，可在线阅读，更多相关《算法复习提纲（9页珍藏版）》请在装配图网上搜索。

1、复习递归：定义、递归算法的效率分析（时间的递推式）蛮力法：定义： 蛮力法是一种简单直接的解决问题的方法，常常直接基于问题本身设计算法。可以用“直 接干吧！”来描述蛮力法策略，通常是最容易想到和采用的一种简单直接的算法设计策略。特点：1. 算法设计较为简单直接，相对容易；2. 通常，算法效率不高。因此，高效算法一般很少来自于蛮力法。3. 可以解决广泛领域的各种问题，几乎是唯一一种解决各种问题的 一般性方法。常用于一些非常基本而又十分重要的算法。比如： 计算 n 个数的和； 求一个列表的最大元素，等等。4. 对于一些重要的算法（如排序、查找、矩阵乘法、字符串匹配）， 蛮力法可以产生一些合理算法，多

2、少具备一些实用价值 ，且并不 限制问题的规模。5 对于规模不大的问题，蛮力法的计算速度可以接受时，设计一个 高效算法所花费的代价很可能不值得。（人力成本，算法复杂度）6. 蛮力法可为研究和教学服务，以它作为尺度，衡量该问题的其他 算法的效率。例：选择排序、冒泡排序、顺序查找、字符串匹配、穷举查找（穷举查找是一种简单的蛮力 法。）等、分治法：定义： 分治法是著名的通用算法设计技术，很多非常有效的算法实际上是这个通用算法的特殊 实现。基本思想符合人们在解决复杂问题时，常常将其从大到小逐步分解，进而将较易求解 的小问题解合并得到原问题的解。这即是“分治法”的分而治之的思想。1. 分解原问题规模为较小

3、的子问题，子问题最好有相同规模；2. 求解子问题；（ 1、2 步“分解求解”过程通常是递归的，直到子问题可简单求解为 止）3. 合并子问题的解，得到原问题的解（必要的话）。效率分析：建立递归算法的递推式并求解得到增长函数的增长率类型：分治法运算时间的通用分治递推式： 一个规模 n 的问题，每次被分为 a 个子问题，每个子问题规模 n/b （上例：a = 2, b = 2）。为简化分析，假定n是b的乘方即n = bk, k=1,2,3,., 通用分治递推式如下：T (n)二c, n 0&(nd ),a bd应用例：折半查找、合并排序、快速排序、大整数乘法、在序列Al.n中找最大最小元素的问题、

4、循环锦标赛问题等减治法：定义：利用给定规模与较小规模问题解之间的关系，从顶至下（递归） 或从底至上（非递归）求解 问题的一种方法。减治法通常分为 3 种：减常量法：常量通常为1即减1法，也有减2的（如奇偶数分别处理）减常因子法：常因子通常为2 （减半技术）。 减可变规模法。例：插入排序、深度优先与广度优先搜索、拓扑排序等减治与分治的区别变治法： 定义：变治法是一种通用的算法设计技术，基于变换的思想。变：把问题变得更容易求解；治：对变换后的问题求解。变治策略有 3 种主要类型：实例化简：变换为更简单的实例。如预排序。改变表现：变换为不同表现实例。如AVL树，2-3树，堆。问题化简：变换为另一个问

5、题的实例。如数学建模，将具体应用问题用变量、函数、方程这样的数学对象来表达。动态规划：定义：把求解过程分为一系列阶段，各个阶段依次按照最优性原则计算，最后阶段计算得到 最优解。包括 分段、求解 两大步。（不能段化的问题不能用动态规划法求解）动态的含义：求解算法施加的状态是变化的。当前状态只与其直接前趋状态有关，对其直接前趋状态 施加求解算法，成为当前状态。最优性原则 （Principle of Optimality）： 一个最优问题任何实例的最优解，是由该实例的子实例的最优解组成的。子实例组成父 实例，父实例分解为子实例。动态规划法的特点：1. 分阶段（级）决策。对最优化问题，用最优性原则设计

6、。2. 一般采用自顶向下分析（规模减小），自底向上计算（规模增加）。计算过程是一级一级 （一阶段一阶段）地向前推进，直到最终状态。动态规划算法的基本要素：最优子结构性质和重叠子问题。最优子结构性质： 问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必 须是基于当前状态（由上一次决策产生）的最优决策。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复 计算多次。对每个子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以 直接引用，不必重新求解。解决问题的基本特征1. 动态规划一般解决最值（最优，最大，最小，最长）问题；2.

7、动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3. 动态规划解决的问题必须包含最优子结构，即可以由（n-1）的最优推导出n的最 优； 解决问题的基本步骤：1. 划分阶段；2. 选择状态；3. 确定决策并写出状态转移方程实际应用当中的简化步骤：1. 刻画最优解的结构特性. (一维，二维，三维数组)2. 递归的定义最优解. (状态转移方程)3. 以自底向上的方法来计算最优解.4. 从计算得到的解来构造一个最优解.应用例：斐波纳契数列F(n)(动态规划应用于非最优化问题例) 步骤1：用F (n)表示在斐波纳契数列中第n个数的值;步骤 2：状态转移方程：n if n = 0 or 1F(n-

8、1) + F(n-2) if n 1步骤3：以自底向上的方法来计算最优解n012345678910F(n)011235813213455步骤 4：在数组中分析构造出问题的解计算二项式系数步骤1：用C(n,k)表示二项式系数；步骤 2：状态转移方程：C(n-1,k-1)+C(n-1,k) if n k0步骤 3：以自底向上的方法来计算最优解k步骤4：在数组中分析构造出问题的解n 1数塔问题(如何(如何分段、转题、最短路径问题(FloydWarshall算法)1C(n-t k-V Gn-D分段、转移方程的确定、实例求解过程)、有向无环图的最短路径问题 移方程的确定、实例求解过程)、最长公共子序列问

9、题、最长上升子序列问0-1背包问题：n个重量wl,.,wn、价值vl,.,vn的物品和一个承重量W的背包。 要求：找出最有价值子集，且能装入背包中(不超重)。分段：对于01背包问题，可利用减一技术和最优性原则，按物品数量和背包承重量分段。状态： V(i, j) 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。 转移方程：V(0, j) = 0 (0 个物品)，V(i, 0) = 0 (承重量 0)V(i, j) = V(i-1, j) 第i个物品不能装入，j wi (不超重)i在最优子集中i不在最优子集中自底向上计算：V(i, j)-V(n, W)(i： 0-n,j： 0-W)目标

10、V(n, W)Vj=0j - wijj=Wi=00000i - 10V(i-1, j-wi)V(i-1, j)i0V(i, j)i=n0V(n, W)贪婪法：贪婪法常用来解决最优化问题。犹如登山一样，一步一步向前推进。 从某个初始点 出发，根据当前局部的而不是全局的最优决策，以满足 约束方程为条件，使目标函数值增 加最快或最慢为规则，决定本步的 局部最优解。如最速上山法各步的方向选择 梯度。 计算机学家 把贪婪法作为一种通用设计技术，通过一系列步骤来构造问题的解， 每一 步对当前获得的局部最优解进行扩展，直到全局最优解为止。每一步选择满足（与动态规划法不同）：1. 可行解：满足约束条件。2.

11、局部最优；当前步骤下，所有选择中的局部最佳选择（贪婪）。3. 不可取消：当前局部解一旦得到，后续步骤无法改变。优点：比动态规划法的时间和空间效率高，算法设计也较简单。但对于某些 问题，贪婪法不 能获得全局最优解。用贪婪法的两个性质判断问题是否适用贪婪法求解1 贪婪选择：所求问题的全局最优解，可通过一系列的局部最优选择来达到。每次 选择就得到一个局部最优解，将所求问题化简为规模更小的子问题。2 最优子结构： 问题的最优解中包含它的子问题最优解。换句话说，全局最优解是由局部最优解组 成。贪婪法与动态规划法的区别动态规划法，第k步所作出的选择依赖于第k-1步内若干个子问题解（与未来选择有 关），只有

12、在解出 k-1 步所有子问题后，才能作出选择。 贪婪法仅在当前状态下作局部 最优选择（与未来选择无关）。然后， 再去解作出这个选择后产生的子问题。正由于这 种差别，动态规划法 通常以自底向上方式求解各个子问题，而贪婪法则通常以自顶向下的 方式进行。贪婪法不能得到最优解时，动态规划法可以得到最优解。例：背包问题：两类背包问题：1. 物品可以分割的背包问题。贪婪法求得最优解。2. 物品不可以分割的 0-1 背包问题。贪婪法不一定能求得最优解。多机调度问题：设有n个独立的作业1,2,，n ，由m台相同的机器进行加工处理。作业i所需的处理 时间为 ti 。现约定，每个作业均可在任何一台机器上加工处理，

13、但未完工前不允许中断处 理。作业不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m 台机器加工处理完成。最小生成树问题（Prim （普里姆）算法、Kruskal （克鲁斯卡尔）算法）单源（单起点）最短路径问题（Dijkstra算法）旅行商问题：求给定带权图的最短哈密顿回路。哈密顿回路：图的每个顶点只经过 一次的回路。 因此，旅行商问题要求从任一顶点出发，包含（经过） 给定带权图的全部顶点的一条最 短路径哈夫曼树、哈夫曼编码、作业调度回溯有分支限界法：定义、区别、解空间树、回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜

14、索 至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该 结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略 搜索。求问题所有解：要回溯到根，且根结点的所有子树都已被搜索遍才结束。求任一解：只要搜索到问题的一个解就可结束。回溯算法设计过程 stepl确定问题的解空间； step2确定结点的扩展规则； step3 搜索解空间。n 皇后问题问题描述：n后问题要求在一个nXn格棋盘上放置n个皇后，使得它们彼此不攻击。 按国际象棋规则，一个皇后可攻击在同一行或同一列或 同一斜线上的其他任何棋子。因此， n 后问题等价于在一个 nX n 棋盘 放

15、 n 个皇后，使任何 2 皇后不能被放在同一行或同一列 或同一斜线上。问：这样的布局有多少种？4后问题的状态空间树及实际的搜索树（红色箭头线表示）使用回溯策略，实际扫描过的状态如图：0-1 背包问题给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何 选择装入背包的物品，使得装入背包中物品的总价值最大?示例：n=3, C=30, w=16, 15, 15, v=45, 25, 25问题的解空间树：约束条件：X w x ci i 1i=1如何剪枝？：设r是当前尚未考虑的剩余物品价值总和；Cv是当前价值；bestv是当前最优价值。 当r+CvWbestv时，可剪去右子树。分支搜索：分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓“分支”是采用广度优先的策略，依次生成E-结点的所有分支，也就是所有的儿子 结点。和回溯法一样，可以在生成的结点中，抛弃那些不满足约束条件的结点，其余结点加 入活结点表。然后从表中选择一个结点作为下一个E-结点。选择下一个E-结点方式的不同导致几种分支搜索方式：1FIFO 搜索2. LIFO搜索*3优先队列式搜索