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

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

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

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

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

分治法的设计思想是将一个规模为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)


相关推荐

  • JavaWeb项目为什么我们要放弃JSP?为什么要前后端解耦?为什么要动静分离?[通俗易懂]

    JavaWeb项目为什么我们要放弃JSP?为什么要前后端解耦?为什么要动静分离?[通俗易懂]以前的项目大多数都是java程序猿又当爹又当妈,又搞前端(ajax/jquery/js/html/css等等),又搞后端(java/mysql/oracle等等)。

  • java中|与||,&与&&到底有什么区别呢?

    java中|与||,&与&&到底有什么区别呢?在java中,很多人都不知道&与&&,|与||的区别。&,&&:(与,短路与):一样的地方就是二者执行最后的结果是一样的,但是执行的过程有区别,对于&:无论&左边是否为false,他都会继续检验右边的boolean值。对于&&:只要检测到左边Boolean值为false时,就会直接判断结果,不会在检验右边的值(因为”与”有一个false最后结果就是false了)所以&&的执行效率更

  • go struct转map_golang map

    go struct转map_golang mapGo字符串转Map和Map的嵌套取值想用Go写爬虫联系一下语法的,结果数据类型转换还不熟悉。map嵌套取值就会报错typeinterface{}doesnotsupportindexing字符串转Map//示例字符串resString:=`{ “args”:{}, “headers”:{ “Accept-Encoding”:”gzip”, “Host”:”httpbin.org”, “User-Agent”:”GRequests/0.10

  • c++界面开发工具_visual c++界面设计教程

    c++界面开发工具_visual c++界面设计教程亲爱的BCGSoft用户,我们非常高兴地宣布BCGControlBarProfessionalforMFC和BCGSuiteforMFCv30.2正式发布!此版本包含新的Office2019样式可视化主题、改进了Shell控件以及其他一些新功能和改进!本文将为大家介绍v30.2中发布的新功能!让您对BCG最新发布的版本有一个全新的认识和了解。需要最新版的可以点击这里【BCG下载】…

  • pve 和esxi哪个性能强(前后对比)

    ESXi实战1、安装ESXi7;2、在ESXi7上安装VCSA;3、在VCSA上管理ESXi7;4、在ESXi7上安装CentOS7;存储扩容:直接创建VMFS6,然后扩容;遇到的问题:vCenter(VCSA)中无法添加ESXi主机,提示无法找到IP,全部加入域后,问题解决;PVE实战1、安装ProxmoxVE6.1,主机名一定要唯一…

  • 变量放在堆还是栈_堆和栈的共同特点

    变量放在堆还是栈_堆和栈的共同特点内容会持续更新,有错误的地方欢迎指正,谢谢!什么是栈区,什么是堆区栈区(stack):由编译器自动分配释放,存放函数的参数值、局部变量的值等,内存的分配是连续的,类似于数组,当我们声明变量时,编译器会自动接着当前栈区的结尾来分配内存。堆区(heap):由程序员分配释放,若程序员不释放,程序结束时由OS回收,内存的分配不是连续的,类似于链表。变量存放的位置C/C++程…

发表回复

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

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