logo资料库

湘潭大学xtu算法设计考试复习资料（个人整理）.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：1.43M 资料格式：pdf 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    考试复习 2019年6月16日 星期日 下午12:59 1. 算法概论 什么是算法 解决问题的方法和过程。是对特定问题求解步骤的一种描述，包含操作有限规则和操作有限序 性质 列。 确定性：意义清晰，无歧义 有限性：执行次数、执行时间有限 输入：0个或多个输入 输出：至少产生一个输出 什么是程序 是算法用某种程序设计语言的具体实现 算法与程序 程序不一定满足有限性，例如操作系统永不停止； 程序中指令必须机器可执行的； 算法代表了对问题的解，而程序是算法在计算机上的具体实现 问题求解 理解问题->选择数据结构->设计算法->证明正确性->分析算法->设计程序 算法描述 自然语言、流程图、程序设计语言、伪代码 算法正确性 对所有输入都最终停止；产生正确输出 算法分析 目的：改进（设计）算法、选择算法 复杂性分析 算法复杂性=所需要的计算机资源 T(n)时间复杂性 S(n)空间复杂性 决定复杂性的因素：求解问题的规模、具体的输入数据、算法本身的设计 最有实际价值的：最坏情况时间复杂性 渐进函数 a=f(n),b=c*g(n),c为常数 2. 递归与分治 递归a. 概论 要素 直接或间接地调用自身的算法 边界条件、递归方程 整数划分问题 状态：q(n,m)：最大加数a<=m； 1. 2. 边界条件：q(n,1)=1;//n=1+1+……+1 q(1,m)=1;//1只有一种划分 3. 递归方程：当n
    当n=m时，q(n,n)=1+q(n,m-1);//n=(n-1)+1; 当n>m时，加数中存在m，则排列数为q(n-m,m); 不存在m，排列数为q(n,m-1) 所以，q(n,m)=q(n-m,m)+q(n,m-1); 总结 分治b. 思想 1. 2. 优点：结构清晰，可读性强；易用数学归纳法证明算法的正确性； 缺点：运行效率低，时间复杂度、空间复杂度高； 将大规模的问题分割成k个小规模的相同子问题； 对k个子问题分别求解，若子问题的规模还不够小，继续划分，直到规模足够小易求解为止； 将小规模问题的解合并成一个更大规模的问题的解，自底向上逐步求出原解。 适用条件 最优子结构性质：该问题可以分解成若干个规模较小的相同问题； 1. 2. 3. 各个子问题相互独立； 最小规模的子问题易解决、子问题的解可以合并。 c. 时间复杂度 一般方程 a子问题的个数；b递减的步长；D(n)合成子问题的开销； ～递减方式：n-b、n/b n-b的求解方程式 O(a^n) n/b的求解方程式 D(n) 常数c a>1 a=1 线性函数c*x a
    幂函数n^x a>b O(n^p) aD(b) O(n^p) 时间复杂性：T(deta)=O(2^deta)=O(2^(n-m)); // 是T(deta) 例题1 应用d. 大整数乘法 快速排序 1. 2. 基本思想：通过一趟排序后，将待排数组分成两部分，前部分均小于后部分，分别对这两 部分进行排序，直到全部有序； 最坏情况：每次划分的基准是当前无序区中关键字的最小（最大）的那个 时间复杂度：每次长度为m的序列，需要比较m-1次 所以，T(n)=(n-1)+(n-2)+….1=n(n-1)/2=O(n^2) 3. 最好情况：每次划分选取的序列都是当前无序区的“中值” 时间复杂度：T(n)=2T(n/2)+(n-1)=O(nlogn) 4. 改进：“三者取中”——选取首、尾、中间三个位置，选择中间值作为基准 循环赛日程 表 问题：n=2^k个运动员比赛，要求每个选手与其他n-1个选手各赛一次，一个选手一天只能 参赛一天，一共举行n-1天 3. 动态规划 概论a. 分阶段决 将求解过程分解成若个阶段，依此求解每个阶段得到原问题的解。
    策 各个阶段不要求相互独立，前一阶段的输出可以作为下一阶段的输入。 求解策略 如果最求解的问题可以划分成若干段，那么最后的最优解是由各个部分解组成的。 且部分解一定是对应阶段的最优解。 基本要素 最优子结构性质：原始问题最优解与子问题最优解存在递归关系。（自底向上构造原问题最 优解） 重叠子问题性质：相对较小的子问题与原问题相似，且子问题的解在不同的上一级问题中都 需要用（自顶向下分解原问题） 基本思想 构造记录已解的子问题，再次遇到时查表即可，避免重复计算，提高效率 应用b. 最短路径 矩阵连乘 不同的计算顺序差别很大！ 关系式子：A[1:n]=A[1:k]*A[k+1,n]，每个A都是最优解 最长公共 子序列 最大子段 和 递增最长 参考link：https://segmentfault.com/a/1190000012754802
    子序列 序列的要求：长度越长越好（优先满足）、末尾元素越小越好 比如已经有这3个子序列： 0• 0, 4 • 0, 4, 12 • 现在扫描到8。前两个序列都可以在后面拼接8。反正不管拿0还是0, 4来拼接，拼接完以后 的结尾元素都是8，那当然是用0, 4来拼接啊！得到的新序列长度更大！ 拼接以后得到了0, 4, 8，显然比0, 4, 12更有潜质，因此将buildingLists[3]从12更新为更好的8。 4. 贪心算法 a. 与动态规划的比较 相同点 都具有最优子结构性质 不同点 动态规划 贪心法 性质 子问题重叠性质 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优解的选择达 到 求解方法 自底向上 自顶向下：每做一次贪心选择就将所求的问题简化成更小规模问题 概论b. 特点 总是作出当前看起来最好的选择，只考虑局部最优，通常能获得近似最优解 如何确定贪心选择性质 需要证明贪心选择将会导致整体的最优解： 1. 2. 3. 证明问题的最优解必须包含第一个贪心选择(即第一个选择是对的) 证明贪心选择后，原问题可化成更小规模的类似子问题 用数学归纳法证明，一系列贪心选择后，可以得到整体最优解 应用c. 最小生成树 Prim算法：选点；Ｏ(n)，适合点少的 Kruskal算法：选边（排序）；O(eloge )，适合边少的 0-1背包问题 n个物品，1个背包，给出每个物品的重量、价值，以及背包容量，求如何使背包价值最 大？ 0-1背包问题不能用贪心法解决，背包问题（物品可以分割）可以用
    单源最短路径 (Dijkstra算 法) 旅行商问题 用贪心法（每次选择权值最小的边）不保证能得到最优解 活动安排问题 贪心策略：最早结束时间——可以使下一活动尽早开始 5. 回溯法 a. 三种搜索方式 如何搜索 优点 缺点 广度优先搜索 逐层搜索； 一定能找到解 时间、空间复杂性大 深度优先搜索 逐分支搜索 时间、空间复杂性小 不一定能找到解 数据结构 队列 栈 启发式搜索 最好优先搜索 时间复杂度小 需要设计评价函数，其优劣影响效率 按某方式排序 概论b. 适用情形 需要找出满足某些约束条件的最优解时 1. 2. 求解组合数相当大的问题 基本思想 初始时，根节点为活节点，也是当前扩展节点； 在当前扩展节点出，向纵深方向搜索、移动，得到新的扩展节点； 当当前的扩展节点不能再向纵深方向移动时，则称为死节点； 则往回移动（回溯）至最近的一个活节点处，并使这个活节点成为当前的扩展节点。 应用c. 数的全排列 O(n!) n皇后问题 斜对角线：↘ x+y、↙ x-y表示 TSP旅行商问题 选一条路线，经过每个城市最后回到驻地，使总路程最小 0-1背包问题 剪枝：超过背包容量、当前价值+剩余物品的全部价值<=当前求解最优值 O(2^n)：因为0-1背包是一个求子集的过程 d. 回溯法常见求解两类问题
    求排列 O(f(n)*n!)，f(n)是处理一个节点所需要的时间复杂度 求子集 O(f(n)*2^n) 6. 分之界限法 a. 与回溯法的对比 回溯法 分支限界法 求解目标 找出解空间树T中满足条件的所有解 找出满足约束条件的一个解or某种意义下的最优解 搜索方式 深度优先 剪枝依据 约束条件 广度优先or最小消耗优先 约束条件and目标的限界函数 概论b. 评价函数构 造 评价函数f(d)=已有损耗g(d)+期望损耗h(d) 评价函数应该准确有效地压缩状态空间 索路径构造 扩展节点信息表：节点名、评价函数值、前驱指针； 两个表：Open表——保存准备扩展的节点，Close表——已搜索的节点； 一旦找到目标，则可根据前驱指针逆向构造路径 下界L(d)<=f(d)<=上界U(d) 根据评价函数and上下界函数，将解空间不可能产生最佳解的子树剪掉，提高效率 每个活节点只有一次机会成为扩展节点。活结点一旦成为扩展节点，就一次性产生其所有 的儿子节点。 导致不可行解or非最优解的儿子节点被舍弃，其他的加入到活节点表中。 从活节点表取出下一扩展节点，重复上诉过程，直到找到所需要的解or活节点表为空为止 根据选择下一扩展节点的方式不同，分成两种分支限界法： 队列式（FIFO）分支限界法、优先队列式分支限界法（按优先级原则） 界限 基本思想 方法 应用c. 单源最短路 径 g(d)=g(p)+C[p][d] g(d)：从源S到节点d的路径长度；p：d的前驱节点；C[p][d]：p到d的最短路径 下界：0； 上界：正无穷，之后会不断用最短路径取代
    0-1背包问题 评价函数：f(d)=背包中已装载的物品价值； 限界函数：u(d)=当前已找好的最优解-（背包已装价值+剩余未选物品总价值） 若u(d)>0则说明，即使所有东西都装满了也不可能得到最优解，所以无需继 续下去 旅行商问题 评价函数：f(d)=节点1(起始节点)到节点d的代价-已走过的边的数量 f(d)=f(p)+Cpd-1，p是d的前驱 扩展方法：每次选取评价函数最小的节点扩展 7. 概率（随机化）算法 概论a. 思想 使用概率和统计的方法，在执行过程中，对下一计算步骤做出随机选择 随机性 1. 2. 3. 同一实例多次执行，效果可能完全不同 时间复杂性随机 解的正确性随机 性能分析 平均时间复杂度、获得正确解（优化解）的概率、解的精确度估计 算法b. 数值随机化 算法 蒙特卡罗算 法 目的 1. 2. 适用情况：数值问题 结果：得到近似解 1. 2. 3. 适用情况：需要准确解的问题 结果：可能给出错误解，求正确解的概率依赖于时间 思想：舍p是一个实数，且1/2=p，则称该算法 是p正确的； 若同一实例不会给出不同的解，则称该算法是一致的；
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料