算法设计与分析总结.doc

简答： 算法定义： 算法是一个满足下列条件的计算： 有穷性/终止性：有限步内必须停止。/* 好算法/坏算法 */ 确定性：每一步都是严格定义和确定的动作。 /* 要严格算法语言 */ 能行性：每一个动作都能够被精确地机械执行。 输入：有一个满足给定约束条件的输入。 输出：满足给定约束条件的结果。 常用算法及其特点： 递归分治法，贪心算法，动态规划，回溯法等。 递归分治法： 基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 动态规划法： 1）适用条件：当一个优化问题可分为多个子问题，子问题的解被重复使用。具有最优子结构和重叠子问题 2）基本思想：求解每个子问题仅一次，并保存其结果，以后用到时直接存取，不重复计算，节省计算时间。 3）解题步骤： ① 分析优化解的结构 ② 递归地定义最优解的代价 ③ 自底向上地计算优化解的代价保存之，并获取构造最优解的信息 ④ 根据构造最优解的信息构造优化解 4）与递归分治法的区别：动态规划法自底向上，递归分治法自顶向下 贪心算法： 1）基本思想 ·求解最优化问题的算法包含一些列步骤 ·每一步都有一组选择 ·作出在当前看来最好的选择 ·希望通过作出局部优化选择达到全局优化选择 2）产生优化解的条件 ① 贪心选择性 ② 优化子结构 3）与动态规划法的比较： ·动态规划方法可用的条件 优化子结构 子问题相交性 子问题空间小 ·贪心算法可用的条件 优化子结构 贪心选择性 *可用Greedy方法时，动态规划方法可能不适用。 *可用动态规划方法时，Greedy方法可能不适用。 6. 平摊分析： 1）基本思想： ·在平摊分析中，执行一系列数据结构操作所需要时间是通过对执行的所有操作求平均而得出的。 ·平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。 ·平摊分析与平均情况分析不同, 不牵涉到概率。 2)常用方法: 聚集方法、会计方法、势能方法。 3）区别与联系： （1）聚集方法为每个操作都赋予相同的平摊代价，即使序列中存在不同类型操作时也一样。会计方法和势能方法对不同类型操作赋予不同的平摊代价。 （2）势能方法不是将已预付的费用作为存储在数据结构特定对象中的存款来表示，而是表示成一种“势能”，或“势”，它在需要时可释放出来以支付后面操作的代价。势是与整个数据结构而不是其中的个别对象发生联系的。即会计存储在个体上，势能存储在整体上。 7. 拟阵： 1）定义：Matroid是一个序对M=(S, I)，满足： S是一个有限非空集合; I是非空的S子集的集族，I中的子集合称为S的独立子集合; 遗传性: 如果B?I，A?B，则A?I； 交换性：如果A?I，B?I，?A??B?，则?x?B-A使得A?{x}?I。 2）图拟阵(Graphic Matroid)的定义： 设G=(V，E)是一个无向图，由G确定的图拟阵MG=（SG，IG）定义如下： SG是G的边集合E，IG={A | A= E’ ?E, (V, A)是一个森林}。 显然，SG=E是一个有限集合. 因为?e?E，(v, {e})是一个森林，{e}?IG。于是，IG是SG的非空集族。 ③ 证MG满足遗传性。如果B?IG，A?B，则(V，A)是一个森林。于是，A?IG，MG满足遗传性。 ④ 证MG满足交换性。设A?IG，B?IG，?A??B?，由图论定理可知，具有k条边的森林包括?V?-k棵树，于是，A包括?V?-?A?棵树，B包括?V?-?B?棵树。 由于B具有较少的树，B一定包含一个树T，T的结点在A的不相同树中。T是连通的，必包括一条边(u, v)，使得u和v在A的不相同树中。(u, v)?A-B连接A的两棵不同的树，(u, v)可以加到A，(V, A?{(u,v)})是森林，A?{(u,v)}? IG，于是MG满足交换性。 Matroid的性质 定义2. 设M=(S，I)是一个Matroid，A?I。x?A称为A的一个extension如果A?{x}?I。 定义3. 设M=(S，I)是一个Matroid，A?I（A称为M的独立子集合）。如果A没有extension，则称A为最大独立子集合。 定理2. 一个Matroid的所有最大独立子集合都具有相同大小。 证. A是Matroid M的最大独立子集合，而且存