算法分析复习.ppt

1、主要内容、分割战略、动态计划、贪心算法、回溯方法、0-1背包问题的算法设计战略比较与分析、分支限制法、分割法的基本思想是将N规模的问题分解为K个小子问题。这些子问题徐璐独立，与原始问题相同。递归解决这些子问题，然后合并每个子问题的解决，以获得原始问题的解决。1 .分治法、分治法可以解决的问题一般具有以下特点。如果在一定程度上缩小牙齿问题的规模，就很容易解决。牙齿问题可以分为几个小的相同问题。换句话说，牙齿问题具有最优子结构特性。利用牙齿问题，可以将分解子问题的解法结合成牙齿问题的解法。分解为牙齿问题的各个子问题徐璐独立。也就是说，子问题之间不包括公共子问题。问题的计算复杂性通常随着问题规模的增

2、加而增加，所以大部分问题满足了牙齿特征。牙齿特征是适用分治法的前提，大部分问题也可以满足。牙齿特征反映了递归思想的应用，能否利用分治法完全取决于问题是否具有牙齿特征。如果具有前两个茄子特征，不具有第三个特征，可以考虑贪心算法或动态计划。牙齿特征包括分治法的效率。如果各子问题不是独立的，分治法就要做很多不必要的事情，反复解决公共子问题。此时也可以使用分治法，但一般来说，最好使用动态计划。divide-and-conquer(p)if(| p |=n0)ad hoc(p)；/小型问题解决divide p into smaller sub instances P1，p2，PK；/分解问题for (I

3、=1，I=k，I)yi=divide-and-conquer(pi)；/每个子问题return merge(y1，yk)递归解决。/将每个子问题的解决合并为原始问题的解决，分割法的基本阶段，分割法的时间效率满足：T(n)=kT(n/m) f(n)，展开递归后分割法的时间效率大致是动态计划的基本思想。动态计划算法的基本要素：最佳子结构重叠子问题，2 .动态计划，动态计划算法适合解决最优化问题。将问题分成多个子问题，并将所有已解决子问题的答案记录在一个表中。无论牙齿问题以后使用还是渡边杏使用，一旦计算出来，就放入表中。动态规划基本阶段，寻找最佳解决方案的特性，并雕刻结构特征。递归定义最佳值。从底部

4、向上计算最佳值。根据计算最佳值时获得的信息构建最佳解决方案。贪心算法的基本思想通过目前看来最好的选择(贪心的选择)，缩小原来问题的规模，反复进行，直到最终解决方法出来。(威廉莎士比亚、贪心、贪心、贪心、贪心、贪心、贪心、贪心)牙齿技术的特点是，不能保证求的最后解法是最好的。不能用于查找最大或最小解决方案问题。只能查找满足特定约束的可执行解决方案的范围。3 .贪心算法，贪婪算法的基本要素：1，贪婪选择的性质，贪婪选择的性质意味着问题的整体最佳解决方案可以通过一系列部分最优选择来实现，即贪婪选择。这是贪心算法能够运行的第一个基本要素，也是贪心算法和动态编程算法之间的主要区别。牙齿性质是使用贪婪法成

5、功的保证。否则就是近忧。动态编程是子问题的解法，得到了当前问题的解法，因此动态编程算法通常自下而上解决每个子问题。贪心算法从当前问题的部分最优解决方案中导出子问题，因此贪心算法通常从上到下进行，以迭代的方式进行连续的贪心选择，每次做出贪心选择时，将想要的问题简化为较小的子问题。(David aser，Northern Exposure(美国电视电视剧，贪心)，2，最优子结构特性，问题的最优解包含子问题的最优解时，牙齿问题说具有最优子结构特性。问题的最优子结构特性是动态编程算法或贪心算法可以解决的问题的核心特征。回溯方法是系统的、跳跃的搜索算法。在包含所有问题分析的解决方案空间树中，根据深度优先

6、级策略在根节点中搜索解决方案空间树。4 .回溯方法，(1)定义给定问题的问题的解决空间(解释编码)(2)确定易于搜索的解决方案空间结构(由树或图组成)。(3)以深度优先级搜索解析空间，在搜索过程中使用茄子函数防止错误搜索。回溯方法的基本步骤：(1)提高回溯方法效率的两种茄子方法使用约束函数截断不符合约束条件的子树。使用边界函数截断无法获得最佳解决方案的子树。(2)两个茄子典型解析空间树子集树：0-1背包，叶节点数2n，摘要点数2n 1，遍历时间(2N)；阵列树：TSP问题，叶节点数n！巡回时间(n！)。如果给定问题在N个元素的集合S中找到满足特定特性的子集，则相应的解决方案空间树称为子集树。例

7、如，0-1背包问题。这些子集树通常包含2n个叶节点，节点总数为2n1-1。通过子集树需要O(2n)计算时间。子集树，void back track(int)if(TN)output(x)；else for(int I=0)；I=1；I)XT=I；If(约束(t)，如果给定问题确定n个元素满足特定特性的排序，则相应的解决方案空间树称为排序树。比如旅行推销员问题。这种阵列树通常有N牙齿！叶节点。要通过阵列树，请O(n！)计算时间。树阵列，void back track(int)if(TN)output(x)；else for(int I=t；I=n；I) swap(xt，Xi) : If(约束(t

8、)，回溯方法：回溯方法称为通用问题解决方法。这也显示了回溯法运用的广泛性。回溯方法与动态规划和贪心算法相比具有独特的优点。回溯方法是寻找一个问题的所有解法或任何解法。这在解决问题时更全面，这也是其他几个茄子算法所没有的优点。分支限制法的搜索策略是在扩展节点上，教师创建所有子节点(分支)，然后从当前活动节点表中选择下一个扩展节点。为了有效地选择下一个展开节点，加快搜索过程，计算每个活动节点上的函数值(边界)，并根据函数值选择当前活动节点表中最有利的节点之一作为展开节点。搜索转到解决空间中具有最佳解决方案的分支，以便尽快找到最佳解决方案。牙齿方法称为分支限制法。5 .分支限制法、分支限制法是解决方

9、案空间树，它经常以宽度优先或最小消耗(最大效果)优先级搜索问题。在分支限制法中，每个活动节点只有一次机会成为扩展节点。实时节点成为扩展节点时，将同时创建所有子节点。在这些儿子节点中，导致无法执行的分析或非最佳解决方案的儿子节点将被丢弃，其馀儿子节点将添加到活动节点表中。然后将“活动节点”(active nodes)表格中的下一个节点作为当前展开节点移除，并重复上述节点展开过程。牙齿过程将继续，直到找到所需的解决方法或活节点表为空。解决方案阶段，解决方案空间定义(解码)；确定解决方案空间的树结构。基于BFS等搜索： a。每个活动节点只有一个机会成为扩展节点。b .从扩展节点创建可以一次到达的新节

10、点。c .在新节点上，删除无法导出最佳解决方案的节点。/茄子修剪策略d .将其馀新节点添加到活动表(队列)中。e .在活动表中选择和展开节点。/选择策略f .直到活动表为空；两个茄子典型的活动节点扩展方法，先进先出队列(F I F O) :将活动节点表组织到一个队列中，并根据队列中的先进先出原则选择下一个节点作为扩展节点。优先级队列(用于消耗的小根堆、用于增加的大根堆):每个节点都有相应的消耗或收益。0-1背包问题的说明：给定的N茄子项目和背包。物品I的重量是wi，其价值是VI，背包的容量是C。问如何挑选背包里的东西，能最大限度地提高背包里的东西的总价值吗？选择装入背包的项目时，每个项目I只有

11、两种茄子选择：装入背包或记帐背包。不能将项目I多次放在背包里，也不能只放一部分。6 .0-1背包问题的算法设计战略比较与分析，正式说明：最佳解决方案序列为x1、x2、.假设为xn，则可以最大限度地实现背包容量C的总价值。如果x1=1，则x2，xn表示如果，x1=0，X2，XN是C容量的背包的总值，仍然是最大的序列。这就是我们所说的最佳子结构的性质。(1)动态规划算法具有0-1背包问题的最优子结构特性。这可以为动态编程问题提供递归关系。设置背包问题的子问题的最佳解决方案是m(i，j)。也就是说，m(i，J)是背包剩馀容量J，可选项目是I，I 1，N时0-1背包问题的最佳值。计算m(i，j)作为0

12、-1背包问题的最佳子结构性质的递归式如下：(1)动态编程算法求解、临界条件、算法复杂性分析：如m(i，J)的递归所示，算法需要O (NA)。背包容量C大时，算法需要更多的计算时间。例如，在c2n中，算法需要(n2n)计算时间。当一个问题具有最佳子结构特性时，可以使用动态计划解决。但有时有更简单有效的算法。贪心算法不是在整体最优中考虑的，在某种意义上只是部分最优选择。(约翰f肯尼迪，努力)贪心算法无法得到整个最优解，但最终结果是最优解的好近似值。(2)求解贪心算法，我们首先计算当前区域的最优解m(i，j)，然后通过循环继续查找最大值(M (I 1，Z)。这也可能表明贪心算法比动态计划算法解决0-

13、1背包问题的便利性。用贪心算法解决问题的前提是问题具有最优的子结构性质。所有选择都是当前状态下最好的部分选择。解决背包问题也显示出贪心算法解决特定问题时的效率。贪心算法不一定求最优解，但也是解决问题的重要方法。(1)分析空间定义：x=(0，0，0)，(0，0，1)，(0，1，0)，(1，1，0)，(1，1，0)解决方案空间可以显示为子集树。搜索解决方案空间树时，只要左侧儿子节点是可执行节点，搜索就会进入左侧子树。仅当右侧子树可以包含最佳解决方案时，才开始搜索右侧子树。否则，请剪切右侧的子树。可行性约束函数：wixiC上限函数：Bound()，使用回溯方法解决问题，但是背包问题比较麻烦。回溯方法

14、在解决多个茄子最优解问题时有很大的优点。因为计算父函数需要O(n)时间，最坏情况下需要O(2n)个右儿童节点需要父函数，所以计算0/1背包问题的回溯算法所需的计算时间复杂性为O(n2n)。(3)分支边界求解，0/1背包问题的分支边界算法可以使用最大收益算法边界函数计算活动节点的最大收益上限upprofit。活动节点为根的子树中所有节点的收入值不能超过upprofit。活动节点的最大堆使用upprofit作为关键值字段。在子集树中执行最大利润分支搜索的函数首先初始化活动节点的最大堆，然后使用数组bestx记录最佳解决方案。函数的循环首先验证E节点左边孩子的可行性。如果可能，请将其添加到子集树和活

15、动节点队列(即最大堆)中。仅当节点右侧孩子的边界值指示可以找到最佳解决方案时，才将右侧孩子添加到子集树和队列中。回溯方法比分支限制具有内存占用的优点。回溯方法使用解析空间的最大路径长度(o)记忆体，而分支边界使用解析空间大小(o)记忆体。对于子集空间，回溯方法需要O(n)的内存空间，分支限制需要O(2n)的空间。最大收益或最小消耗分支限制比回溯方法更直观，在很多情况下，可以检查比回溯方法少的节点数，但在实际应用中，回溯方法超出允许的时间限制之前，可能会超过内存限制。在解决0-1背包问题的过程中，可以清楚地看到四种茄子算法的优点和策略。解决背包问题的四种茄子算法的效率也各不相同。贪心的算法是最有效的，但不一定是最优的解决方案。回溯方法也很好，但解决过程很麻烦，是求所有最优解。动态计划是最差的，因为递归是使用系统资源最多的方法