算法设计与分析复习资料.doc

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

1、算法：指解决问题的一种方法或者一个过程，更严格的讲，算法是由若干条指令组成的有穷序列。它具有输入，输出，确定性，可行性，有穷性5个性质。递归算法：一个直接或者间接地调用自身的算法。可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一组决策变量的取值，都称为该线性规划的一个可行解。解空间：如果ξ1,ξ2,...ξs是一般齐次线性方程组的s个解,则它们的任一线性组合c1ξ1+c2ξ2+...+csξs也是该齐次线性方程组的解向量.由此可知若齐次线性方程组有非零解,则其解有无穷多个,而齐次线性方程组所有解的集合构成一个向量空

2、间,这个向量空间就称为解空间.解空间也就是一个集合。目标函数：(objectivefunction)是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。简单的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。最优化问题：最优化问题，主要是指以下形式的问题：给定一个函数，寻找一个元素使得对于所有A中的，（最小化）；或者（最大化）。这类定式有时还称为“数学规

3、划”（譬如，线性规划）。许多现实和理论问题都可以建模成这样的一般性框架。最优化，是应用数学的一个分支。子问题：一个原问题分解后得到的问题，规模更小。分治法：求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止，这便是分治法。分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解能够通过组合子问题的解来获取。贪心法：贪心法是一种极为直接的算法设计技术，可应用于多种问题的求解。贪心算法（又称贪婪算法）是指，在对问题求解时，

4、总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。动态规划：在多阶段决策问题中，各个阶段采取的策略，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，固有动态之说，称这种解决多阶段决策最优化的过程为动态规划方法。备忘录算法：备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。回溯法：又称试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺寻逐

5、一枚举和检验。回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。贪心选择性质：事先可能给定一些以函数形式表示出来的判定标准，这种在贪心法的每一步上用做决策依据的选择准则被称为最优度量标准，额称为贪心选择性质。最优子结构性质：对于一个问题，如果能从较小规模子问题的最优解求得较大规模同类子问题的最优解，最终得到给定问题的最优解，这就是问题最优解的最优子结构特性。重叠子问题:适

6、合于动态规划法求解的问题，将待求解的问题分解成若干个子问题，经分解得到的子问题往往不是相互独立的，他们可能共享更小的子问题，被称为重叠子问题。分治法所能解决的问题的特征：（基本要素） 该问题的规模缩小到一定程度就可以解决；该问题可以分解成若干规模小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解能合并为该问题的解；分解的各个子问题的解是相互独立的。 如具备了前面两条，而不具备第三条，可以考虑贪心算法和动态规划。理解什么是程序，程序与算法的区别和内在联系 程序(Program)，程序是算法用某种程序设计语言的具体实现。程序可

7、以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 （5）可行性：算法中每条指令的执行指令都

8、有明确的定义，是可行的，可在有限的时间内做完掌握算法的计算复杂性： 算法的复杂度是算法运行所需要的计算机资源的量，需要时间资源的量被称为时间复杂度，需要的空间资源的