算法分析复习ppt课件.ppt

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

1、主要内容分治策略动态规划贪心算法回溯法0-1背包问题的算法设计策略对比与分析分支限界法分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。1.分治法分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公

2、共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。divide-and-conquer(P){if(

3、P

4、<=n0)adhoc(P)

5、;//解决小规模的问题dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}分治法的基本步骤分治法的时间效率满足：T(n)=kT(n/m)+f(n)展开递归式后，得到分治法的时间效率近似为：动态规划的基本思想：将求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解

6、。动态规划算法的基本要素：最优子结构重叠子问题2.动态规划动态规划算法适用于解最优化问题。它把问题分解为很多子问题，用一个表来记录所有已解决的子问题的答案。不管该问题以后是否用到，只要它被计算过，就将其放入表中。动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。贪心算法的基本思想是通过作出在当前看来最优的选择（贪心选择），将原问题规模缩小，如此反复，直至得到最终解。该技术的特点是：不能保证求得的最后解是最佳的。不能用来求最大或最

7、小解问题。只能求满足某些约束条件的可行解的范围。3.贪心算法贪心算法的基本要素：1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。该性质是贪心法使用成功的保障，否则得到的是近优解；动态规划是由子问题的解得到当前问题的解，所以动态规划算法通常以自底向上的方式解各子问题；贪心算法则是由当前问题的局部最优解导出子问题，所以贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪

8、心选择就将所求问题简化为规模更小的子问题。2、最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。4.回溯法回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯法的基本步骤：(1)针对所给问题，定义问题的解空间（对解进行编码）；(2)确定易于搜索的解空间结构（按树或图组织解）；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无

9、效搜索。（1）提高回溯法效率的二种方法①用约束函数剪去不满足约束的子树；②用限界函数剪去不能得到最优解的子树。（2）二类常见的解空间树①子集树：如0-1背包，叶结点数2n，总结点数2n+1，遍历时间为Ω(2n)；②排列树：如TSP问题，叶结点数n!，遍历时间为Ω(n!)。子集树当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。例如0-1背包问题。这类子集树通常有2n个叶结点，其结点总个数为2n+1-1。遍历子集树需O(2n)计算时间。voidbacktrack(intt){if(t

10、>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(constraint(t)&&bound(t))backtrack(t+1);}}排列树当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。例如旅行售货员问题。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。vo