算法课程总结市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.ppt

本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,算法分析与设计课程总结,课程主讲,计算机科学学院 王小明,（,博士,/,教授,/博士生导师,）,Email:wangxm,1/20,算法分析与设计课程总结,第一部分 课程回顾,第二部分 算法比较,2/20,第一部分：课程回顾,算法课程总结,3/20,最优子结构,课程思维导图,4/20,定义：,用变量旧值不停递推出新值处理问题方法。通惯用于数值计算。,实现：递推法,（,利用问题本身所含有一个递推关系求问题解一个方法,）,倒推法,（,倒推法是对一些特殊问题所采取违反通常习惯，从后向前推解问题方法，,如猴子偷桃问题,）,课程回顾,迭代法,(iteration):,5/20,定义：,把问题全部情况或全部过程交给计算机去一一尝试，从中找出问题解。,如狱吏问题。,如枚举法,(enumerate),应用：次序查找，选择排序，冒泡排序，插入排序都是采取蛮力法,课程回顾,蛮力法：,6/20,应用：折半查找，快速排序，二叉树遍历，等等。,定义,:,把一个难于直接处理大问题分解为若干个“相同”小问题，再解全部小问题，然后把小问题解“合并”，从而得到大问题解。,课程回顾,分治法,:,思想：,把问题分解为大小相当（或相等）独立子问题，然后处理子问题，最终把子问题解合并，得到原问题解。,实现：,二分法：每次把问题一分为二。,如二分法求金块分配问题,减治法：只需处理子问题一部分，合并这部分子问题解即可得到原问题解。,*,递归方法是详细实现分治算法一个技术。,*分治法是递归设计方法一个详细策略。,7/20,定义：,贪心算法总是作出在当前看来最好选择。即贪心算法并不从整体最优考虑，它所作出选择只是在某种意义上局部最优选择。,如背包问题、工资发放问题,应用：活动安排问题、最优装载、哈夫曼编码、单源最短路径、最小生成树、多机调度问题,*对于一个详细问题，要确定它是否含有贪心选择性质，必须证实每一步所作贪心选择最终造成问题整体最优解。,哪些问题适适用“贪心法”取得最优解？,满足：贪心选择性质、最优子结构性质问题适适用“贪心法”求最优解,1.,贪心选择性质所求问题整体最优解能够经过一系列局部最优解选择，即“贪心选择”来得到。,2.,最优子结构性质当一个问题最优解包含其全部子问题最优解时，称此问题含有最优子结构性质。,课程回顾,贪心法：,8/20,定义：,我们把这种经过多阶段决议以最优化处理问题过程称为动态规划。,问题特征：,适合用动态规划算法处理问题及决议应该含有三个性质：最优化原理、无后向性、子问题重合,(,子问题之间是不独立,),性质。,基本思想：,把求解问题分成许多阶段或多个子问题，然后按次序求解各子问题。最终一个子问题解就是初始问题解。,实例：,0-1,背包问题、最短路径问题、数塔问题、,n,矩阵连乘问题,应用：资源分配问题、,n,矩阵连乘问题,课程回顾,动态规划：,9/20,定义：,实际是一个类似枚举搜索尝试方法，它主题思想是在搜索尝试中找问题解，当不满足求解条件就回溯”,(,返回,),，尝试别路径。回溯算法是尝试搜索算法中最为基本一个算法,其采取了一个“走不通就掉头”思想，作为其控制结构。如,八皇后问题,课程回顾,回溯,(Backtravking),算法：,10/20,定义：,一个在问题解空间上进行尝试搜索算法。所谓“分支”是采取广度优先策略，依次生成结点,(,扩展节点,),全部分支，也就是全部儿子结点。和回溯法一样，在生成节点中，抛弃那些不满足约束条件（或者说不可能导出最优解）结点，其余节点加入活节点表。然后按一定规则,(,如后进先出、先进先出、,优先队列,),从表中选择一个节点作为下一个活节点。,如装载问题。,实现：,分支搜索、分支限界搜索、优先队列分支限界搜索,课程回顾,分支搜索法：,11/20,概率算法：,是指选择下一步执行步骤时，用随机（概率）方法进行选择，而不是用逻辑上确定方法进行选择.,概率算法特点：,随机决议、不可再现性（,在同一实例上执行两次其结果可能不一样,;,在同一实 例上执行两次时间亦可能不太相同。,）、分析困难（,要求有概率论，统计学和数论知识。,）,课程回顾,概率算法及智能优化算法：,智能优化算法：,模拟自然过程“,优胜略劣汰,”算法普通称之为智能算法。比如，依据动植物繁衍过程原理、物理或化学现象原理等设计处理困难计算问题算法，都能够称为智能优化算法。如蚁群算法、模拟退火算法、遗传算法等。,12/20,蚁群算法模拟自然界蚂蚁觅食过程一个分布式、启发式群体智能算法。,（蚂蚁一开始选择觅食路径概率是一样，但经过一段时间后更优路径上信息素（算子）增多，蚂蚁选择更优路径概率随之增大。）,*迭代思想在实现蚁群算法时有很好应用。,关键点：,信息素控制计算函数设计、随机选择概率函数设计、经验,参数,选取,主要应用领域：组合优化（如,TSP,问题等）、机器学习（如神经网络优化设计等）,遗传算法：,在每一代中，依据个体适应度大小选挑个体，并借助于自然遗传学遗传算子进行选择、交叉、变异，产生新种群。最终末代中最优个体经过解码能够作为问题近似最优解。,*,遗传算法是基于迭代一个优化工具。,关键点：,问题元素编码，选择交叉和变异,主要应用领域：尤其适合组合优化问题，在机器学习、自动控制等领域一样应用广泛。,课程回顾,智能优化算法举例：,13/20,第二部分：算法比较,算法课程总结,14/20,算法比较,中心思想：,全部算法策略中心思想就是用算法基本工具,循环机制和递归机制,来实现算法。,基本策略：,普通而言（除蛮力法），算法实现就是“化大为小，化繁为简”过程。,算法策略和算法区分与联络：,它们是算法设计中两个方面，算法策略是面向问题,算法是面向实现。,二者又是不可分,经过算法策略能够找出处理问题算法，经过处理算法亦可反应其处理策略。,综述：,15/20,算法策略,迭代法,蛮力法,分治法,基本思想,用变量旧值不停递推出新值处理问题方法,把问题全部情况或全部过程交给计算机去一一尝试,分解处理合并,算法（实现）,递推法,倒推法,枚举法,二分法,减治法,适合处理问题,适用处理计算问题,问题可能解是有限、固定、不会产生组合爆炸、轻易枚举。多用于决议类问题。,问题解能够经过将问题分解成相互独立、”相同”子问题来得到。,算法比较,迭代法、蛮力法、分治法比较,16/20,算法策略,贪心法,动态规划,算法思想,做从当前来看最好选择,整体规划动态处理，,做整体最优选择,最优子结构性质,满足。,满足。,贪心选择性质,满足。,后向性,无后向性,适用问题,满足最优子结构、贪心选择性质问题。如多机调度问题等,满足最优子结构、无后向性、子问题重合性质问题。如资源分配问题,算法比较,动态规划法与贪心法比较,17/20,算法策略,分治法,动态规划,算法思想,分解处理合并,得出问题结果,整体规划动态处理，,做整体最优选择,子问题重合,子问题相互独立，不包含公共子问题,将问题归纳为更小、相同子问题子，子问题不独立、有重合,适用问题,问题可分解且子问题相互独立，如折半查找，快速排序等,满足最优子结构、无后向性、子问题重合性质问题。如资源分配问题,算法比较,动态规划法与分治法比较,18/20,算法,回溯法,分支限界法,搜索方法,深度优先搜索,广度优先搜索或者最小消耗优先搜索出,数据结构,堆栈,队列、优先队列,节点存放特征,活节点全部可行子节点被遍历后才被栈中弹,每个节点只有一次成为活节点机会,应用,满足约束 条件全部解方案,满足约束条件一个解,或者在某种意义下最优解,算法比较,回溯法与分支限界法比较,19/20,谢,谢！,本 文 稿 由 卢 茂 生 整 理,水 平 有 限，仅 供 参 考,Q1339075067Q,算法课程总结,20/20,