《数据结构与算法应用教程 教学课件 ppt 作者高佳琴 第10章完 常用算法》由会员分享，可在线阅读，更多相关《数据结构与算法应用教程 教学课件 ppt 作者高佳琴 第10章完 常用算法（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实用教程,主编 高佳琴,第10章 常用算法,本章要点： 1)穷举搜索法。 2)分治法。 3)回溯法。 4)贪婪法。 5)递推法。 6)动态规划法,第10章 常用算法,10.1 穷举法 10.2 回溯法 10.3 分治法 10.4 贪婪法 10.5 递推法 10.6 动态规划法,10.1 穷举法,穷举法可视为最简单的搜索，即在问题答案可能的全部解集内逐一分析查询，直到找出答案为止。简单说穷举法就是先要生成全部可能的候选解，然后查询到符合要求的特定解。,10.2 回溯法,为提高算法效率，必须寻找新的算法，回溯法就是对穷举法的一种很好的改进算法。回溯算法也称为试探法，它是一种系统地搜索
2、问题的解的方法，即按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先的选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术称为回溯法，而满足条件的某个状态点称为回溯点。,10.3 分治法,分治法就是将分而治之策略运用到高效率的计算机算法的设计过程中，将某个输入规模为n的问题，用某种方法划分成等价的m个子问题(每个问题的规模是n/m），只要m个子问题被解决了，原问题就比较容易解决。在算法设计领域应用这个策略，可以解决比大小、矩阵乘法、残缺棋盘、排序等问题。,10.4 贪婪法,贪婪法是指在算法的每一步上，都按照给定的标准，确定一个目前看上去最好的选择，一旦作好选择，就不能
3、更改 1)由给定的n个权值w0， w1， w2， ， wn-1，构造具有n棵二叉树的森林F=T0， T1， T2， ， Tn-1，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。 2)重复以下步骤， 在F中选取两棵根结点的权值最小的扩充二叉树，做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删去这两棵二叉树。 把新的二叉树加入F。,10.5 递推法,递推法是利用问题本身所具有的一种递推关系求问题解的方法。递推法的关键是按照某种标准找出递推关系式，并求出第一个项 (或前几项)，然后代入递推关系式，求出题中要求的值。此方法通常表现为两种方式：一种是顺推，就是从简单问题求解推到一般问题的求解；另一种是逆推，将一个复杂问题逐步推到一个已知解的简单问题。,动态规划（dynamic programming）算法是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。,10.6 动态规划法,
