几种经典算法回顾

今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }google的核心算法MapReduce其实就是分治法的衍生5）分治法例子：合并排序规约过程：动态规划1）基本思想将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的，如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算2）适用问题的特征最优子结构在递归计算中，许多子问题被重复计算多次3）步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。贪心算法1）基本思想贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择2）适用问题的特征贪心选择性质，即所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。最优子结构性质3）步骤：不断寻找局部最优解4）例子：找硬币，哈夫曼编码，单源最短路径，最小生成树（Prim和Kruskal） 最小生成树图示：回溯法1）基本思想在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索2）适用问题的特征：容易构建所解问题的解空间3）步骤定义问题的解空间 确定易于搜索的解空间结构以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索 4）回溯法例子：N皇后问题分支限界法1）基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2）分支限界法例子：单源最短路径问题问题描述：在下图所给的有向图G中，每一边都有一个非负边权。