资源描述
,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,算法分析与设计课程总结,课程主讲,计算机科学学院 王小明,（,博士,/,教授,/,博士生导师,）,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,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
