五大经典算法总结

五大经典算法总结    马上要开始投简历找实习了,自己还是毛都不会,慌得一笔,从今天开始每天刷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)


相关推荐

  • 2109-全国大学生电子设计竞赛-F-纸张数识别(内含arduino代码以及题解)[通俗易懂]

    2109-全国大学生电子设计竞赛-F-纸张数识别(内含arduino代码以及题解)[通俗易懂]题目:一,任务设计并制作纸张计数显示装置,其组成如图1所示。两块平行极板(极板A、极板B)分别通过导线a和导线b连接到测量显示电路,装置可测量并显示置于极板A与极板B之间的纸张数量。二,要求1,基本要求(1)极板A和极板和极板B上的金属电极部分均为边长50mm0mm±1mm的正方形,导线a和导线b长度均为500mm…

  • python 面向对象(进阶篇)

    python 面向对象(进阶篇)上一篇《Python面向对象(初级篇)》文章介绍了面向对象基本知识:面向对象是一种编程方式,此编程方式的实现是基于对类和对象的使用类是一个模板,模板中包装了多个“函数”供使用(可以讲多函数

  • PLSQL详细使用教程及下载地址「建议收藏」

    PLSQL详细使用教程及下载地址「建议收藏」Oracle数据库连接必备,大公司玩转oracle数据库必备,虽然现在已经都用MYSQL替换了,但是不可否认这款软件的实力。中文版还具有语法加强、SQL和PL/SQL帮助、对象描述等功能特性。下载地址:http://kk04.cn/f-6339.html详细使用教程:http://kk04.cn/f-6342.html…

  • PKI体系_基于PKI体系的认证方式进行论述

    PKI体系_基于PKI体系的认证方式进行论述在非对称加密中,公钥可以通过证书机制来进行保护,但证书的生成、分发、撤销等过程并没有在X.509规范中进行定义。实际上,如何安全地管理和分发证书可以遵循PKI(PublicKeyInfrastructure)体系来完成。PKI体系核心解决的是证书生命周期相关的认证和管理问题,在现代密码学应用领域处于十分基础和重要的地位。需要注意,PKI是建立在公私钥基础上实现安全可靠传递…

  • U8 8.9 数据库置疑恢复方法

    U8 8.9 数据库置疑恢复方法A.我们使用默认方式建立一个供恢复使用的数据库(如test)。可以在SQLServerEnterpriseManager里面建立。B.停掉数据库服务器。C.将刚才生成的数据库的日志文件test_log.ldf删除,用要恢复的数据库mdf文件覆盖刚才生成的数据库数据文件test_data.mdf。D.启动数据库服务器。此时会看到数据库test的状态为“置疑”。这时候不能对此数据库进行任何操作。…

发表回复

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

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