计算机算法分析与设计期末总复习.doc

《计算机算法分析与设计期末总复习.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法期末总复习一、算法概述1.算法（1）定义：是解决问题的一种方法或一个过程。（通俗）是由若干条指令组成的有穷序列。（严格）（2）性质：输入、输出、确定性、有限性、可行性。（3）算法三要素：操作、控制结构、数据结构（4）算法设计质量指标：正确性、可读性、健壮性、效率与存储量需求（5）算法好坏标准：时间复杂度、空间复杂度（6）任何可用计算机求解的问题所需的时间都与其   规模  有关。（7）记号在算法复杂性的表示法中表示  渐进确界或紧致界2.程序（1）程序:程序是算法用某种程序设计语言的具体实现。（2）分类：算法分为数值计算和非数值计算；而非数值计算又分为P类（算法的

2、时间复杂度是个多项式P类问题包含在NP类问题中）、NP类（算法的时间复杂度是个非多项式）、NP完全类（首先是一个NP类问题，找不到一个算法使得问题在多项式时间内完成）（3）步骤： 分析问题 à设计算法 à编写程序à调试程序二.递归与分治策略1.递归（1）概念：直接或间接地调用自身的算法为递归算法。用函数自身函数给出定义的函数称为递归。（2）典型案例阶乘函数、斐波拉契数列、汉诺塔问题2.分治（1）概念将一个规模为N的问题分解（划分）为K个规模较小的相同问题，再合并。这些子问题相互独立且原问题相同。（2）典型案例二分查找、快速排序、大整数乘积、矩阵乘法、循环赛日程表三.动

3、态规划1.定义:通常以自底向上的方式，以上一问题的解作为下一问题的基础求解最优解2.适用范围解最优化问题3.基本思想：是将待求解问题分解成若干子问题，先求解子问题 ，然后从这些子问题的解得到原问题的解。4.设计步骤：找出最优解的性质，并刻画其结构特征；递归地定义最优值以自底向上的方式计算出最优值根据计算最优值得到的信息，构造最优解5.基本要素：最优子结构性质：以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的额最优解重叠子问题性质：在用递归算法从顶向下解问题时，有些子问题被反复计算多次，利用此性质，每个问题只解一次，然后保存，再次计算时只是简单地用时间常数查看

4、一下结果5.典型案例矩阵连乘问题、0-1背包问题（不需要排序）四、贪心算法1.定义：以自顶向下的方式从初始阶段开始，每一个阶段总是作一个使 局部最优 的贪心选择来求解最优解，不一定是全局的最优解2.基本要素：（1）贪心选择性质：（贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别）贪心算法的每一个选择都是当前状态下局部最好选择，即贪心选择。（2）最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。3.典型案例0-1背包问题、哈夫曼编码（O（nlogn）、单源最短路径（Dijkstra）、最小生成树活动安排五、回溯法1.定

5、义：一种选优搜索法，又叫试探法，按选优条件向前搜索，以达到目标。但当探索到某步时，达不到原先的目标，就退回一步重新选择。它可以系统地搜索一个问题的所有解或任一解。这种不断回头寻找目标的方法称为 回溯法回溯法是一个既带有系统性又带有跳跃性的搜索算法。2.基本思想：以深度优先方式搜索整个解空间。3.状态空间树裁剪分支标准：约束条件和目标函数的界同时使用约束条件和目标函数的界是    0/1背包问题（需要排序）只使用约束条件进行裁剪的是   N皇后问题 4.解空间树的剪枝函数：约束函数限界函数5.典型案例0-1背包问题（需要排序）、N皇后问题、旅行售货员问题（子集树）六、分

6、支限界法1：定义类似于回溯法，以广度优先或最小耗费（最大效益）优先的方式搜索问题的解空间树。每个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被抛弃，其余儿子结点被加入活结点表中。2.类型：队列式（FIFO）分支限界法按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。 优先队列式 分支限界法按照优先队列中规定的优先级选取优先级最高的结点成为当前的扩展结点。3.分支限界法与回溯法的不同（1）求解目标：后者是找出解空间树中满足约束条件的所有解，前者是找出满足约束条件的一个解，

7、或是在某种意义下的最优解。（2）搜索方式的不同：后者以深度优先的方式搜索解空间树，而前者是以广度优先或最小耗费优先的方式搜索解空间树。4.典型示例;单源最短路径（剪掉、替换）、装载问题、0-1背包问题（需要排序）七、随机化算法1.定义：在算法中使用随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或者执行结果。随机化算法基于随机方法，依赖于概率大小。2.种类:（1）数值随机化算法：用于求解数值问题，结果往往是近似解。（2）蒙特卡罗算法：用于求问题的准确解，但是这个解未必是正确的，一定的概率得到正确解。是概率算法的一种（3）拉斯维加斯算法：