五大常用算法ppt课件.ppt

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

1、五大常用算法介绍及其在图像处理中的应用五大常用算法分治法1动态规划算法2贪心算法3分支限界法5回溯法4分治法设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治策略：对于一个规模为n的问题，若该问题可以容易地解决则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。(分治与递归)适用情况：1)该问题的规模缩小到一定的程度就可以容易地解决;2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;3)利用该问题分解出的子问题的解

2、可以合并为该问题的解；4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。分治法分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并：将各个子问题的解合并为原问题的解。分治法的一般设计模式：Divide-and-Conquer(P)1.if

3、P

4、≤n02.thenreturn(ADHOC(P))3.将P分解为较小的子问题P1,P2,...,Pk4.fori←1tok5.doyi←Divide-and-Conquer(Pi)△递

5、归解决Pi6.T←MERGE(y1,y2,...,yk)△合并子问题7.return(T)分治法分治法在医学图像处理中的应用传统的中值滤波算法需要对滤波窗口内的所有像素进行排序，再依据排序的结果选取中值。常用的排序算法有很多（插入排序、交换排序、选择排序、归并排序、分配排序），以快速排序为例，其算法的思想是将大问题分解为若干个规模较小但结构与大问题相似的问题，递归地解决这些小问题后，将小问题的解结合为大问题的解。2012年林清华等人提出一种新型快速中值滤波算法，主要应用于医学图像.文中方法利用中值滤波算法对滤波窗口内其他像素点的排列顺序不作要求的特点，将基于排序寻找中值的过

6、程转换为基于分治查找中值的过程。在分治查找过程中，利用医学图像未受干扰时图像中像素值的变化是渐变的特性，优先选用中心点附近的像素值进行分治查找，以达到提高算法效率的目的。动态规划算法基本概念动态规划：在多阶段决策问题中，各个阶段采取的决策，一般来说是和时间（先后）有关的，决策依赖于当前状态，又随机引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，这种解决多阶段决策最优化的过程为动态规划。多阶段决策过程：有一类活动的过程，可将过程分为若干个互相联系的阶段，在它的每一阶段都要做出决策，从而使整个过程达到最好的活动效果，这种把一个问题看作是一个前后关联

7、具有链状结构的多阶段过程，就称为多阶段决策过程。最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。动态规划算法基本思想将过程分成若干个互相联系的阶段，即子问题，将各阶段按一定的次序排列好之后，对于某个给定的阶段状态，先求解子问题，然后从这些子问题的解得到原问题的解，对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案。适用条件(1)最优化子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。(2)无后效性：

8、即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）动态规划算法基本步骤动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步

9、骤。初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态图1动态规划决策过程示意图实际应用中可以按以下几个简化的步骤进行设计：（1）分析最优解的性质，并刻画其结构特征。（2）递归的定义最优解。（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。（4）根据计算最优值时得到的信息，构造问题的最优解。动态规划算法基于动态规划算法分割椎骨上下边界的方法基本思想根据椎骨上下缘灰度与形状信息来寻找椎骨的上下边界，在梯度图像中，最终的分割结果被定义为具有最小累积代价和的“路径”，该“路径”由梯度图像中每一列上唯