算法分析与设计总结

第一章算法概述1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。2.算法的性质：1)输入：有零个或多个输入2)输出：有至少一个输出3)确定性：每条指令是清晰的、无歧义的4)有限性：每条指令的执行次数和时间都是有限的3.算法与程序的区别程序是算法用某种程序设计语言的具体实现程序可以不满足算法的有限性4.算法复杂性分析1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性2)三种时间复杂性：最坏情况、最好情况、平均情况3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性第二章递归与分支策略1.递归概念：直接或间接调用自身的算法2.递归函数：用函数自身给出定义的函数3.递归要素：边界条件、递归方程4.递归的应用汉诺塔问题voidHanuo(intn,inta,intb,intc){if(n==1)return;Hanuo(n-1,a,c,b);move(a,b)Hanuo(n-1,c,b,a);}全排列问题voidPerm(Typelist[],intk,intm){//产生list[k,m]的所有排列if(k==m){for(inti=0;I=m;i++)coutlist[i];coutendl;}else{for(inti=j;i=m;i++){Swap(list[k],list[i]);Perm(list,k+1;m);Swap(list[k],list[i])}}}5.分治法的基本思想：将一个规模较大的问题分成若干个规模较小的子问题，这些子问题互相独立且与原问题相同。6.分治法的使用条件：问题的规模缩小到一定程度可以容易地解决问题可以分解为若干个规模较小的相同问题利用原问题分解出的子问题的解可以合并为原问题的解各个子问题是相互独立的7.分治法的时间复杂度8.分治法的应用二分搜索1)时间复杂度O(logn)2)参考算法快速排序1)快排的运行时间与划分是否对称有关2)时间复杂度O(nlogn)合并排序1)基本思想：将待排元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最总将排序好的子集合合并成所要求的排序好的集合。2)时间复杂度O(nlogn)棋盘覆盖大整数乘法Strassen矩阵乘法第三章动态规划1.基本思想：将待求解问题分解成若干个子问题，先求解子问题，再从这些子问题的解得到原问题的解。2.动态规划与分治法的区别：与分治法不同，适合于动态规划求解的问题，经分解得到的子问题往往是不独立的。3.动态规划算法求解步骤1)找出最优解性质，并刻画其结构特征2)递归地定义最优值3)自底向上求最优值4)构造最优解4.基本要素：最优子结构性质：问题的最优解包含子问题的最优解子问题重叠性质：在递归法自顶向下求解问题时，每次产生的子问题并不总是新的问题，有些子问题被反复计算多次。5.动态规划、递归、备忘录的区别备忘录的递归方式是自顶向下的，动态规划的递归方式是自底向上的备忘录与直接递归的控制结构相同，区别在于备忘录给子问题的解建立了备忘录，以备查看。6.算法应用矩阵连乘最大字段和最大公共子序列0-1背包第四章贪心算法1.基本思想：总是做出当前看来最好的选择即使贪心算法不能得到整体最优解，但最终结果却是最优解的很好的近似解2.基本要素贪心选择性质所求问题的整体最优解可以通过一系列局部最优解的选择即贪心选择来达到。最优子结构性质一个问题的最优解包括子问题的最优解。3.分治、贪心和动态规划动态规划以自底向上的方式求解，贪心选择以自顶向下方式求解贪心和动态规划都有最优子结构性质背包问题可以用贪心算法，而0-1背包问题不能用贪心算法求解分治动态规划贪心算法适用类型通用问题优化问题优化问题子问题结构每个子问题不同很多子问题重复（不独立）只有一个子问题最优子结构不需要必须满足必须满足子问题数全部子问题都要解决全部子问题都要解决只要解决一个子问题子问题在最优解里全部部分部分选择与求解次序先选择后解决子问题先解决子问题后选择先选择后解决子问题4.算法应用活动安排问题结束时间早的优先背包问题为什么0-1背包用贪心算法不能求得最优解？主要原因在于无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。最优装载问题哈夫曼编码问题计算平均码长单源最短路径问题最小生成树问题Prim和Kruskal算法多机调度问题第五章回溯法1.基本思想：以深度优先方式系统搜索问题解的算法2.解题步骤：1)针对所给问题，定义问题解空间2)确定解空间结构3)以深度优先搜索解空间，并在搜索过程中剪枝3.回溯法是一个既带有系统性又带有跳跃性的搜索算法。4.特征：在搜索过程中动态产生问题的解空间。问题的解空间树是虚拟的，并不需要算法运行时构造一个真正的树结构，在任何时刻，算法只保存从根结点到当前扩展结点的路径。5.扩展结点：一个正在产生儿子的结点。6.活结点：一个自身已生成但儿子结点还没有全部生成的结点。7.死结点：不能再向纵深方向移动的扩展结点。8.避免无效搜索策略——剪枝函数约束函数：用约束函数在扩展结点处剪去不满足约束的子树限界函数：用限界函数剪去得不到最优解的子树。9.算法框架递归回溯和迭代回溯子集树：当从n个元素的集合中找出满足某种性质的子集时，相应的解空间叫子集树。遍历时间O(2^n)排列树：确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。遍历时间O(n!)10.算法应用装载问题解空间树：子集树右儿子剪枝：当前载重量+剩余集装箱重量=当前最优载重量0-1背包问题解空间树：子集树右儿子剪枝：当前结点处上界Bound最大团问题解空间树：子集树右儿子剪枝：确认有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。n后问题解空间树：完全n叉树图的m着色问题解空间树：完全m叉树(m为颜色数)旅行售货员问题解空间树：排列树递归遍历第六章分支限界法1.基本思想：以广度优先或最小耗费（最大效益）优先的方式搜索解空间树，搜索过程中，每一个活结点只有一次机会称为当前扩展结点。活结点一旦成为扩展结点，就一次性产生所有儿子结点。2.回溯法与分支限界法的异同1)求解目标不同：回溯法更适合找出解空间树中满足约束条件的所有解；分支限界法更适合找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2)对解空间搜索方式不同：回溯法以深度优先方式搜索解空间树，每个活结点有多个机会成为扩展结点分支限界法以广度优先或最小耗费优先方式搜索解空间树，每个活结点只有一次机会成为扩展结点，一旦成为扩展结点就一次性产生所有儿子结点。3)都是在问题的解空间上搜索问题解的算法3.分支限界法算法框架队列式分支限界法将活结点表组织成一个队列，按队列先进先出的原则选取下一个结点为当前扩展结点。不搜索已不可行结点为根的子树，因为搜索时结点的处理是跳跃式的，所以无法递归。优先队列式分支限界法将活结点组织成一个优先队列，按优先队列式中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。4.算法应用单源最短路径最小堆优先级是结点所对应的当前路长约束条件：一种是下界不小于当前最短路径则剪去以该节点为根的子树另一种是利用结点间的控制关系进行剪枝。两条路径到达同一结点，剪去较长路径所对应的树中的结点为根的子树。装载问题队列式右儿子剪枝：当前结点对应重量+剩余集装箱重量=当前最优解搜索到第一个叶结点之前，总有当前最优解为0，上式总成立，右子树测试不起作用。为确保右子树成功剪枝，应该在算法每一次进入左子树的时侯就更新当前最优值。优先队列式优先级：从根结点到结点x的路径所相应的载重量再加上剩余集装箱重量之和。最小堆最优解的构造：需要保存已构造出的部分解空间树0-1背包问题最大堆优先级：已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。上界：背包问题的最优解最大团问题最大堆优先级：un(见上界)上界：用变量cn表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；cn+n-level+1作为顶点数上界un的值。算法的终止条件：遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。旅行售货员问题最小堆优先级：堆中每个结点的子树费用的下界下界：以剩余的所有顶点最小出边费用和作为依据。计算图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。