算法分析与设计知识点总结

第一章概述算法的概念：算法是指解决问题的一种方法或过程，是由假设干条指令组成的有穷序列。算法的特征：可终止性：算法必需在有限时间内终止；正确性：算法必需正确描述问题的求解过程；可行性：算法必需是可实施的；0011算法与程序的关系：区分：程序可以不肯定满足可终止性。但算法必需在有限时间内完毕；程序可以没有输出,而算法则必需有输出；算法是面对问题求解的过程描述，程序则是算法的实现。联系：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性性质。算法描述方式：自然语言，流程图，伪代码，高级语言。算法简单性分析：算法简单性的凹凸表达运行该算法所需计算机资源〔时间，空间〕的多少。算法简单性度量：期望反映算法本身性能，与环境无关。〔。一般是针对问题选择根本运算和根本存储单位根本运算与根本存储单位的开销作为标准。算法简单性C问题规模N、算法输入I和算法本身A。即C=F(N,I,A)。其次章递归与分治分治法的根本思想：求解问题算法的简单性一般都与问题规模相关，问题规模越小越简洁处理。分治法的根本思想是，将一个难以直接解决的大问题，分解为规模较小的一样子问题，直至这些子问题简洁直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。是分治法中最常用的技术。使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到肯定的程度就可以简洁地解决；该问题可以分解为假设干个规模较小的一样问题，即该问题具有最优子构造性质；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。〔作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好〕递归的概念：直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。题缩小到很简洁直接求出其解。这自然导致递归过程的产生。有限次计算后得出结果。第三章动态规划动态规划的根本思想：挨次求解各子问题。最终一个阶段或子问题的解就是初始问题的解。分治法求解时，子问题数目太多，从而导致解决原问题需要消耗指数级时间。与分治法不同的是，动态规划中分解得到的子问题往往不是相互独立的。。动态规划的适用条件：动态规划法解所能解决的问题一般具有以下两个根本因素：一、最优子构造性质当问题的最优解包含着其子问题的最优解时，称该问题具有最优子构造性质。二、重叠子问题性质屡次。这种性质称为子问题的重叠性质。其它同分治法。动态规划问题的特征：求解的问题是组合优化问题；求解过程需要多步推断，从小到大依次求解；子问题目标函数最优解之间存在依靠关系；动态规划算法设计的根本步骤和要素：根本步骤：找出最优解的性质，并刻画其构造特征〔考察是否适合承受动态规划法〕递归地定义最优值。(建立递归式或动态规划方程)以自底向上的方式〔或以自顶向下的备忘录方法〕计算出最优值。依据计算最优值时得到的信息，构造最优解。要素：最优子构造重叠子问题备忘录〔表格〕应用实例分析：1、矩阵连乘问题：分析最优解构造：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。题的最优子构造性质是该问题可用动态规划算法求解的显著特征。建立递归关系；〔递归求解最优值简单度较高的缘由是)；计算最优值—迭代查表求解计算最优值—备忘录求解构造最优解第四章贪心法贪心算法的根本思想：方法。优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心算法不能对全部问题都得到整体最优解，但对很多问题它能产生整体最优解。设计中的优化原则本质上是全都的。动态规划算法在某一步打算优化函数的最大或最小值时而是依据当时状况实行“只顾眼前”的贪心策略打算取舍。贪心算法的设计要素：可以用贪心算法求解的问题一般具有2个重要的性质：1、最优子构造性质：题的最优子构造性质是该问题可用动态规划算法或贪心算法求解的关键特征2、贪心选择性质：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择选择来到达。这是贪心算法与动态规划算法的主要区分。动态规划算法通常以自底向上的方式求解各子问题为规模更小的子问题。选择最终导致问题的整体最优解。应用实例：1、活动安排问题：第五章回溯法回溯法的根本思想：回溯法的使用条件：回溯法适用于搜寻问题和优化问题。回溯法的设计要素：针对问题定义解空间：问题解向量解向量重量取值集合构造解空间树两类典型的解空间树：子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶结点n树称为排列树。排列树通常有n!个叶结点。推断问题是否满足多米诺性质。搜寻解空间树，确定剪枝函数。确定存储搜寻路径的数据构造。第六章分支限界法分支限界法的根本思想：分支界限法类似与回溯法，也是在问题解空间中搜寻问题解的一种算法。分支界限法与回溯法思想比照：支限界法的求解目标则是找出满足约束条件的一个解种意义下的最优解。广度优先或以最小消耗优先的方式搜寻解空间树。儿子结点被