五类常见算法小记 (递归与分治,动态规划,贪心,回溯,分支界限法)

五类常见算法小记 (递归与分治,动态规划,贪心,回溯,分支界限法)

大家好,又见面了,我是全栈君。

近日复习了一些算法知识,小记于此

  • 递归与分治法
直接或间接地调用自身的算法称为递归算法。 递归是算法设计与分析中经常使用的一种技术,描写叙述简单且易于理解。

分治法的设计思想是将一个规模为n难以解决的问题分解为k个规模较小的子问题,这些子问题
相互独立
与原问题同样
递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

典型样例:Fibonacci数列,阶乘。Hanoi塔;
二分法搜索、高速排序、合并排序。


  • 动态规划法

 

动态规划过程是:依据当前(阶段)状态,採取对应的决策。引起状态的转移。例如以下图。一个决策序列就是在变化的状态中产生出来的,这样的多阶段最优化决策解决这个问题的过程就称为动态规划。


 初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

                      图1 动态规划决策过程示意图


动态规划过程中的转移中的状态能够是一个。也能够是一个集合,比方状态集合包括{a,b,c},但每一步的状态都是由上一步或几步的状态决定的。

动态规划算法与分治法类似,其思想也是将待求解问题分解成若干个子问题(一般每一个问题相应一个阶段)。
按顺序求解子阶段。前一子问题的解,为后一子问题的求解提供了实用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其它局部解。

依次解决各子问题。最后一个子问题就是初始问题的解。

    因为动态规划解决的问题多数有重叠子问题这个特点,为降低反复计算。对每个子问题仅仅解一次,将其不同阶段的不同状态保存在一个二维数组中。

    与分治法最大的区别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)

典型样例:最长公共子序列; 最大连续子序列和(
最大m子段和)。


  • 贪心算法
贪心算法在策略的运行过程中。总是做出对当前看来是最好的选择。也就是说贪心算法并不从整理最优上进行考虑。它所做出的选择仅仅是在某种意义上的局部最优选择。

贪心算法不能保证找到的解是最优解,但在某些情况下能够是最优解的近似解。甚至是最优解。


典型样例:哈夫曼编码;单源最短路径(Dijkstra算法)。最小生成树(Prim和Kruskal算法)


  • 回溯法 (DFS搜索解空间)
回溯法是以深度优先方式搜索问题解的算法。它适用于组合数较大的问题,能系统地搜索到一个问题的全部解惑任一解。
回溯法解题通常包括3个步骤:①针对所给的问题。定义问题的解空间。  ②确定易于搜索的解空间的结构; ③ 以DFS搜索解空间,并在搜索过程中用剪枝函数(约束条件)避免无效搜索。

解空间树
①子集树:当所给问题是从n个元素的结合S中找出满足某种性质的子集时。对应的解空间树称为子集树。

比如n个物品的0-1背包问题。这类子集树通常有2^n个叶节点,其节点总个数为为2^(n+1)-1。

遍历子集树的不论什么算法均需O(2^n)的计算时间

②排列树:当所给问题是确定n个元素满足某种性质的排列时,对应的解空间树成为排列树。

比如旅行售货员问题。排列树通常有n!

个叶节点。因此遍历排列树须要O(n!)的计算时间。


搜索实现能够递归。也能够用树的非递归深度优先遍历算法来实现(用到
栈Stack)。

典型样例:八皇后(找出全部的解),
N 皇后

  • 分支界限法(BFS搜索解空间)
分支界限法的求解目标是找出满足约束条件的一个解。或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。(分支界限法与回溯法求解目标不同)

分支界限法以广度优先或以最小耗费(最大收益)优先的方式搜索解空间。所谓“分支”就是在扩展节点处,先生成其全部儿子节点(分支)。然后在从当前的活结点表中选择下一个扩展节点。继续搜索。过程中能够用约束条件,进行剪枝。
常见的扩展节点的常见方式:
先进先出FIFO队列
优先队列分支界限法


典型样例:单源最短路径


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108483.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • idea创建一个javaweb项目

    idea创建一个javaweb项目前提java环境以及tomcat的安装1、IDEA创建Web项目此处以Idea2020.3.4举例1、新建普通Java项目注意:Idea2020无法直接新建JavaWeb项目,只能通过新建普通Java项目的方式间接新建JavaWeb项目。选择项目位置和普通Java项目相同,此处略过。2、修改普通Java项目为JavaWeb项目项目根目录->右键->AddFrameworkSupport选择JavaEE版本勾选左侧的WebApplication

  • navicat15for激活码-激活码分享

    (navicat15for激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • html+css实现漂亮的透明登录页面,HTML实现炫酷登录页面

    html+css实现漂亮的透明登录页面,HTML实现炫酷登录页面承蒙各位小伙伴的支持,鄙人有幸入围了《CSDN2020博客之星》的前200名,现在进入投票环节,如果我平时写的文章和分享对你有用的话,请每天点击一下这个链接,投上你们宝贵的一票吧!谢谢!❤️每一票都是我坚持的动力和力量!https://bss.csdn.net/m/topic/blog_star2020/detail?username=qq_23853743作者:AlbertYang,软件设计师,Java工程师,前端工程师,爱阅读,爱思考,爱编程,爱自由,信奉终生学习,每天学习一点点,就是领.

  • matlab理想低通滤波器代码_matlab简单低通滤波器

    matlab理想低通滤波器代码_matlab简单低通滤波器低通滤波器的设计设计低通滤波器的要求:设低通滤波器通带截止频率为ωp=0.2π,阻带截止频率为ωs=0.4π,通带波纹Ag=0.5dB,最小阻带衰减Ar=50dB。wp=0.2*pi;wr=0.4*pi;trwidth=wr-wp;%过渡带宽度N=ceil(6.64*pi/trwidth)+1;%滤波器的长度n=0:1:N-1;wc=(wr+wp)/2;hd=ideal_lp(wc,N);w_…

    2022年10月23日
  • sscanf,sscanf_s及其相关使用方法「建议收藏」

    sscanf,sscanf_s及其相关使用方法

  • Vue(12)组件的组织结构和组件注册「建议收藏」

    Vue(12)组件的组织结构和组件注册「建议收藏」组件的组织通常一个应用会以一棵嵌套的组件树的形式来组织:例如,你可能会有页头、侧边栏、内容区等组件,每个组件又包含了其它的像导航链接、博文之类的组件。为了能在模板中使用,这些组件必须先注册以便

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号