五大经典算法总结

五大经典算法总结    马上要开始投简历找实习了,自己还是毛都不会,慌得一笔,从今天开始每天刷2道以上的leetcode然后总结,并且总结各种面试题的知识点,以后常复习,加油。    在刷leetcode时经常看到有人说DP,然后去百度了DP是个啥,才知道DP是五大经典算法之一,今天开始总结一下五大经典算法。    五大经典算法分为1、分治法:把一个复杂的问题分成两个或更多的相同或相似的子问…

大家好,又见面了,我是你们的朋友全栈君。

       马上要开始投简历找实习了,自己还是毛都不会,慌得一笔,从今天开始每天刷2道以上的leetcode然后总结,并且总结各种面试题的知识点,以后常复习,加油。

        在刷leetcode时经常看到有人说DP,然后去百度了DP是个啥,才知道DP是五大经典算法之一,今天开始总结一下五大经典算法。

        五大经典算法分为

1、分治法:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

2、动态规划法:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

3、贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 常见的贪心算法有:Prim算法、Kruskal算法(都是求最小生成树的)。

基本思路:将问题分解为若干个小问题,逐渐求得各个子问题的局部最优解,最后合并为原来问题的解。

4、回溯法:回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。深度优先;

       回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

5、分支限界法:类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

一、分治法

分治法所能解决的问题一般具有以下几个特征:
    1) 该问题的规模缩小到一定的程度就可以容易地解决
    2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
    3) 利用该问题分解出的子问题的解可以合并为该问题的解;

    4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

若不具备第三条特征,可考虑采用动态规划法(DP)或者贪心法。

若不具备第四条特征,可考虑采用动态规划法。

分治法基本步骤:

    step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

    step3 合并:将各个子问题的解合并为原问题的解。

可使用分治法求解的一些经典问题:

(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表

(10)汉诺塔

二、动态规划法

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

适用条件:

能采用动态规划求解的问题的一般要具有3个性质:
    (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
    (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

   (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

案例:

有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。
分析:动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上,我们让f(n)表示走上n级台阶的方法数。

那么当n为1时,f(n) = 1,n为2时,f(n) =2,就是说当台阶只有一级的时候,方法数是一种,台阶有两级的时候,方法数为2。那么当我们要走上n级台阶,必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步,所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2),我们用dp[n]来表示动态规划表,dp[i],i>0,i<=n,表示到达i级台阶的方法数。

int fun(int n){  
    if (n==1||n==2)  
        return n;  
    /*判断n-1的状态有没有被计算过*/  
    if (!dp[n-1])  
        dp[n-1] = fun(n-1);  
    if(!dp[n-2])  
        dp[n-2]=fun(n-2);  
    return dp[n-1]+dp[n-2];  
}  

三、贪心算法

贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
解题的一般步骤是:
1.建立数学模型来描述问题;
2.把求解的问题分成若干个子问题;
3.对每一子问题求解,得到子问题的局部最优解;

4.把子问题的局部最优解合成原来问题的一个解。

例子:钱币找零问题

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?用贪心算法的思想,很显然,每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。

public class charge {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
    	int res = charge(84);
    	System.out.println(res);
    }
 
   private static int charge(int money) {
	   int count = 0;
       int value[] = {50,20,10,5,2,1};
       while(money>0){
       	int length = value.length;
       	for(int i=0;i<length;i++){
       		while(money>=value[i]){
       			money=money-value[i];
       			count++;
       			//System.out.println(money);
       		}
       	}
       }
       return count;
	}     
}

 四、回溯法

        回溯法是一种系统地搜索问题解答的方法。在搜索的过程中尝试找到问题的解,如果发现找不到了,就退一步,往上回溯(剪枝过程)。对于许多复杂问题和大规模问题都可以使用回溯法。 
      回溯法的基本思想是按照深度优先搜索的策略,从根节点开始搜索,当到某个节点时要判断是否是包含问题的解,如果包含就从该节点继续搜索下去,如果不包含,就向父节点回溯。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。 

      回溯法常用的剪枝函数:(1)约束函数:在节点处减去不满足约束的子树。(2)界限函数:减去得不到最优解的子树。

一般步骤:

1、针对所给问题,确定问题的解空间
2、利用适于搜索的方法组织解空间
3、利用深度优先搜索解空间

4、在搜索过程中用剪枝函数避免无效搜索。

举例:N皇后问题

在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击)。

暂缺代码

五、

 

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

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

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

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

(0)


相关推荐

  • win10如何添加linux开机引导,win10 linux 双系统怎么设置开机引导「建议收藏」

    win10如何添加linux开机引导,win10 linux 双系统怎么设置开机引导「建议收藏」匿名用户1级2018-11-16回答第一步:当然是下载Ubuntu了,我是在Ubuntu官网下载的原生版本,我下载的是Ubuntu最新版本15.04。没有选择国人修改过的kylin版本。kylin好不好我完全不懂,只是习惯性的觉得国人做系统不放心,就连修改下我都不放心。第二步:制作u盘启动盘。我用的是UltraISO这个软件制作的启动盘,操作很简单,为了增加文章篇幅,我就简单贴两张图吧。(这地方…

  • 二叉树的性质及其创建

    二叉树的性质及其创建二叉树的性质性质1在二叉树的第i层上至多有2^(i-1)个结点(i>=1)性质2深度为k的二叉树至多有2^k-1个结点(k>=1)性质3对任意一棵二叉树,若终端结点数为n0,其度数为2的结点数为n2,那么n0=n2+1满二叉树深度为k且结点个数为2^k-1,即每一层都具有最大结点数完全二叉树深度为k,结点数为n的二叉树,如果其结点1n的位置序号分别与满二叉树的结点1…

  • Cortex m33_STM32F4

    Cortex m33_STM32F4Cortex-M3Bit-Banding1.概述CM3的存储器系统支持所谓的“位带”(bit-band)操作。通过它,实现了对单一bit的原子操作。位带操作仅适用于一些特殊的存储器区域中。从汇编角度看:与传统方法的比较:在位带区中,每个比特都映射到别名地址区的一个字——这是个只有LSB才有效的字。支持位带操作的两个内存区的范围是:**0x2000_0000-0x

  • 英语商务邮件常用句子_商务英语email写作

    英语商务邮件常用句子_商务英语email写作1.Iamwritingtoconfirm/enquire/informyou…我发邮件是想找你确认/询问/想通知你有关…2.IamwritingtofollowuponourearlierdecisiononthemarketingcampaigninQ2.我写邮件来是为了跟进我们之前对第二季度营销活动的决定。3

    2022年10月20日
  • 大一下学期微积分期末预习(3):定积分的应用-求旋转体的体积

    大一下学期微积分期末预习(3):定积分的应用-求旋转体的体积下面这个是柱壳法,不是注,别问,问就是字写错了。

  • 卡巴斯基的离线更新以及病毒库备份[通俗易懂]

    卡巴斯基的离线更新以及病毒库备份[通俗易懂]卡巴斯基的离线更新以及病毒库备份 1、如果你用的是卡巴斯基5.0…..(….为版本号),病毒库在X:\DocumentsandSettings\AllUsers\ApplicationData\KasperskyAnti-VirusPersonal\5.0\base(其中X为安装时操作系统盘符,下同。专业版为X:\DocumentsandSettings\AllUsers…

发表回复

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

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