算法设计与分析：复习总结

【一】常见的算法策略算法策略和算法是算法设计中的两个方面算法策略是面向问题的,算法是面向实现的通过算法策略才找出解决问题的算法用不同算法求解的问题算法策略是不同的。【一】常见的算法策略1）递推：“递推法”和贪心算法一样也是由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系，每一步不需要策略参与到算法中，它们更多地用于计算。2）递归：递归法是利用大问题与其子问题间的递归关系来解决问题的。每次找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。例如：汉诺塔问题3）穷举：对所有可能的解逐一尝试。4）递归回溯：类似于穷举法的思想,递归回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。【一】常见的算法策略5）分治：求解较复杂的问题。这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解“合成”，就得到较大的子问题的解，最后合成为总问题的解。6）动态规划：动态规划法与贪心法类似，要求问题具有最优子结构（即最优解包含子问题的最优解），是一种自底向上的求解方式，与递归正好相反，每次求解到一个阶段时，该阶段求解所依赖的子问题已经完全求解完毕，因此每一步的求解都是在直到全部所需信息的情况下进行的，因此可以得到全局最优解。【一】常见的算法策略7）贪心：如果想要得到最优解，需要对问题性质有更严格的要求，除了要有最优子结构外，还要求问题具有贪婪选择性质。贪心每一步都要选择当前看来最好的，做完此选择后便将问题化为一个（仅仅一个）子问题，这是一个顺序的求解过程，每一步都是单独考虑，只考虑局部最优，因为并没有完成对之后子问题的求解，所以贪心算法不能完成对整个解空间的搜索，因此通常不能得到最优解。除非问题具有贪婪选择性质。所谓贪婪选择性质就是问题经过一次贪婪选择后只能形成一个子问题，这样求解空间实际上就是一个线性的空间，贪心算法可以得到最优解。是一种自顶向下求解思路。【二】算法策略之间关系1）“分治法”与“动态规划法”

•

都是递归思想的应用，找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。

•分治法的特征之一是所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

【二】算法策略之间关系

2）回溯与分支限界•回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。•一般情况下，回溯法的求解目标是找出解空间树中满足约束条件的所有解的方案，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。【二】算法策略之间关系

3）动态规划与搜索算法•搜索算法：在解决最优化问题的算法中，搜索可以说是“万能”的。所以动态规划可以解决的问题，搜索也一定可以解决。动态规划要求阶段决策具有无后向性，而搜索算法没有此限止。•动态规划算法在时间效率上的优势是搜索无法比拟的，但动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。•动态规划是自底向上的递推求解，而无论深度优先搜索或广度优先搜索都是自顶向下求解。【三】分治在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分治法。二分法是分治法较常用的分解策略，折半查找、归并排序等算法都是采用此策略实现的。【四】贪心贪心算法的基本性质1）贪心选择性质

2）最优子结构性质例一：Dijkstra单源最短路径问题(有向图)

例二：Kruskal最小生成树问题(每次选权值最小边，直到生成一个最小生成树)【五】动态规划

1）最优决策原理：要求问题具有最优子结构（即最优解包含子问题的最优解），是一种自底向上的求解思路。

2）动态规划的决策过程最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；决策的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向后递归或迭代，直到最终结果。【六】回溯与分支限界回溯与分支限界法解决实际问题，大致可分为四个环节：1）确定问题的可能解空间，即找出进行穷举的搜索范围。2）以一种便于搜索的方式组织所有的可能解，一般是生成可能解空间树。3）以某种方式搜索可能的解空间树，有两种基本搜索方式。即：深度优先搜索方式