精华内容
参与话题
问答
  • 五大常用算法总结

    万次阅读 多人点赞 2016-06-10 23:26:41
    据说有人归纳了计算机的五大常用算法,它们是贪婪算法,动态规划算法,分治算法,回溯算法以及分支限界算法。虽然不知道为何要将这五个算法归为最常用的算法,但是毫无疑问,这五个算法是有很多应用场景的,最优化...

    引言

    据说有人归纳了计算机的五大常用算法,它们是贪婪算法,动态规划算法,分治算法,回溯算法以及分支限界算法。虽然不知道为何要将这五个算法归为最常用的算法,但是毫无疑问,这五个算法是有很多应用场景的,最优化问题大多可以利用这些算法解决。算法的本质就是解决问题。当数据量比较小时,其实根本就不需要什么算法,写一些for循环完全就可以很快速的搞定了,但是当数据量比较大,场景比较复杂的时候,编写for循环就是一个很不明智的方式了。一是耗时,二是写出的代码绝对是天书。当然还有第三点,这点也是最重要的,写代码是一种艺术,而不是搬砖。前面的文章里对这五种算法都已经做了详细的讲解和归纳,本文主要是一个总结,将这五种算法整理到一起来对比,分析一下。

    0) 穷举法

    穷举法简单粗暴,没有什么问题是搞不定的,只要你肯花时间。同时对于小数据量,穷举法就是最优秀的算法。就像太祖长拳,简单,人人都能会,能解决问题,但是与真正的高手过招,就颓了。

    1) 贪婪算法

    贪婪算法可以获取到问题的局部最优解,不一定能获取到全局最优解,同时获取最优解的好坏要看贪婪策略的选择。特点就是简单,能获取到局部最优解。就像打狗棍法,同一套棍法,洪七公和鲁有脚的水平就差太多了,因此同样是贪婪算法,不同的贪婪策略会导致得到差异非常大的结果。
    具体的详细解析请参见下面的文章:
    http://blog.csdn.net/changyuanchn/article/details/51417211

    2) 动态规划算法

    当最优化问题具有重复子问题和最优子结构的时候,就是动态规划出场的时候了。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果,避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时,动态规划的效果也会很差。如果问题存在大量的重复子问题的话,那么动态规划对于效率的提高是非常恐怖的。就像斗转星移武功,对手强它也会比较强,对手若,他也会比较弱。
    具体的详细解析请参见下面的文章:
    http://blog.csdn.net/changyuanchn/article/details/51420028
    http://blog.csdn.net/changyuanchn/article/details/51429979

    3)分治算法

    分治算法的逻辑更简单了,就是一个词,分而治之。分治算法就是把一个大的问题分为若干个子问题,然后在子问题继续向下分,一直到base cases,通过base cases的解决,一步步向上,最终解决最初的大问题。分治算法是递归的典型应用。
    具体的详细解析请参见下面的文章:
    http://blog.csdn.net/changyuanchn/article/details/17150109
    http://blog.csdn.net/changyuanchn/article/details/51465175

    4) 回溯算法

    回溯算法是深度优先策略的典型应用,回溯算法就是沿着一条路向下走,如果此路不同了,则回溯到上一个
    分岔路,在选一条路走,一直这样递归下去,直到遍历万所有的路径。八皇后问题是回溯算法的一个经典问题,还有一个经典的应用场景就是迷宫问题。
    具体的详细解析请参见下面的文章:
    http://blog.csdn.net/changyuanchn/article/details/17354461

    5) 分支限界算法

    回溯算法是深度优先,那么分支限界法就是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间,获取问题的所有解,而分支限界法则是获取一个解(一般来说要获取最优解)。
    具体的详细解析请参见下面的文章:
    http://blog.csdn.net/changyuanchn/article/details/17102037

    展开全文
  • 目录简介一、监督学习1、决策树(Decision Tree,DT)2、朴素贝叶斯分类器(Naive Bayesian Model,NBM)3、最小二乘法(Least squares)4、逻辑回归(Logistic Regression)5、支持向量机(SVM)6、K最近邻算法...

    1、简介

    本文讲解了机器学习常用算法总结和各个常用分类算法精确率对比。收集了现在比较热门的TensorFlow、Sklearn,借鉴了Github和一些国内外的文章。

    机器学习的知识树,这个图片是Github上的,有兴趣的可以自己去看一下:
    地址:https://github.com/trekhleb/homemade-machine-learning
    在这里插入图片描述

    简单的翻译一下这个树:

    英文 中文
    Machine Learning 机器学习
    Supervised Learning 监督学习
    Unsupervised Learning 非监督学习
    Reinforcement Learning 强化学习
    Neural Networks and Deep Learning 神经网络与深度学习
    Ensemble Learning 集成学习

    以下是一部分算法的概念和应用,仅供大家参考

    2、监督学习

    监督学习可以看作是原先的预测模型,有基础的训练数据,再将需要预测的数据进行输入,得到预测的结果(不管是连续的还是离散的)

    2.1、决策树(Decision Tree,DT)

    决策树是一种树形结构,为人们提供决策依据,决策树可以用来回答yes和no问题,它通过树形结构将各种情况组合都表示出来,每个分支表示一次选择(选择yes还是no),直到所有选择都进行完毕,最终给出正确答案。

    决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:

    先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。
    后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。
    

    在这里插入图片描述

    2.2、朴素贝叶斯分类器(Naive Bayesian Model,NBM)

    朴素贝叶斯分类器基于贝叶斯定理及其假设(即特征之间是独立的,是不相互影响的),主要用来解决分类和回归问题。

    具体应用有:
    标记一个电子邮件为垃圾邮件或非垃圾邮件;
    将新闻文章分为技术类、政治类或体育类;
    检查一段文字表达积极的情绪,或消极的情绪;
    用于人脸识别软件。
    

    学过概率的同学一定都知道贝叶斯定理,这个在250多年前发明的算法,在信息领域内有着无与伦比的地位。贝叶斯分类是一系列分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。朴素贝叶斯算法(Naive Bayesian) 是其中应用最为广泛的分类算法之一。朴素贝叶斯分类器基于一个简单的假定:给定目标值时属性之间相互条件独立。

    2.3、最小二乘法(Least squares)

    你可能听说过线性回归。最小均方就是用来求线性回归的。如下图所示,平面内会有一系列点,然后我们求取一条线,使得这条线尽可能拟合这些点分布,这就是线性回归。这条线有多种找法,最小二乘法就是其中一种。最小二乘法其原理如下,找到一条线使得平面内的所有点到这条线的欧式距离和最小。这条线就是我们要求取得线。
    在这里插入图片描述

    2.4、逻辑回归(Logistic Regression)

    逻辑回归模型是一个二分类模型,它选取不同的特征与权重来对样本进行概率分类,用一个log函数计算样本属于某一类的概率。即一个样本会有一定的概率属于一个类,会有一定的概率属于另一类,概率大的类即为样本所属类。用于估计某种事物的可能性。

    逻辑回归

    2.5、支持向量机(Support Vector Machine)

    支持向量机(support vector machine)是一个二分类算法,它可以在N维空间找到一个(N-1)维的超平面,这个超平面可以将这些点分为两类。也就是说,平面内如果存在线性可分的两类点,SVM可以找到一条最优的直线将这些点分开。SVM应用范围很广。

    在这里插入图片描述

    要将两类分开,想要得到一个超平面,最优的超平面是到两类的margin达到最大,margin就是超平面与离它最近一点的距离,如下图,Z2>Z1,所以绿色的超平面比较好。

    在这里插入图片描述

    2.6、K最近邻算法(KNN,K-NearestNeighbor)

    邻近算法,或者说K最近邻(KNN,K-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
    在这里插入图片描述

    主要应用领域是对未知事物的识别,即判断未知事物属于哪一类,判断思想是,基于欧几里得定理,判断未知事物的特征和哪一类已知事物的的特征最接近。如上图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。由此也说明了KNN算法的结果很大程度取决于K的选择。

    2.7、集成学习(Ensemble Learning)

    集成学习就是将很多分类器集成在一起,每个分类器有不同的权重,将这些分类器的分类结果合并在一起,作为最终的分类结果。最初集成方法为贝叶斯决策。
    在这里插入图片描述

    集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练,然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法,同时也非常流行。

     常见的算法包括:
     Boosting, Bootstrapped Aggregation(Bagging),
     AdaBoost,堆叠泛化(Stacked Generalization, Blending),
     梯度推进机(Gradient Boosting Machine, GBM),随机森林(Random Forest)。
    

    那么集成方法是怎样工作的,为什么他们会优于单个的模型?
    他们拉平了输出偏差:如果你将具有民主党倾向的民意调查和具有共和党倾向的民意调查取平均,你将得到一个中和的没有倾向一方的结果。
    它们减小了方差:一堆模型的聚合结果和单一模型的结果相比具有更少的噪声。在金融领域,这被称为多元化——多只股票的混合投资要比一只股票变化更小。这就是为什么数据点越多你的模型会越好,而不是数据点越少越好。
    它们不太可能产生过拟合:如果你有一个单独的没有过拟合的模型,你是用一种简单的方式(平均,加权平均,逻辑回归)将这些预测结果结合起来,然后就没有产生过拟合的空间了。

    3、无监督学习

    3.1、聚类算法

    聚类算法就是将一堆数据进行处理,根据它们的相似性对数据进行聚类。

    聚类,就像回归一样,有时候人们描述的是一类问题,有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构,以便按照最大的共同点将数据进行归类。常见的聚类算法包括 k-Means算法以及期望最大化算法(Expectation Maximization, EM)。

    聚类算法有很多种,具体如下:中心聚类、关联聚类、密度聚类、概率聚类、降维、神经网络/深度学习。
    在这里插入图片描述
    在这里插入图片描述

    3.2、K-均值算法(K-Means)

    K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

    在这里插入图片描述

    通常,人们根据样本间的某种距离或者相似性来定义聚类,即把相似的(或距离近的)样本聚为同一类,而把不相似的(或距离远的)样本归在其他类。

    3.3、主成分分析(Principal Component Analysis,PCA)

    主成分分析是利用正交变换将一些列可能相关数据转换为线性无关数据,从而找到主成分。PCA方法最著名的应用应该是在人脸识别中特征提取及数据降维。
    在这里插入图片描述

    PCA主要用于简单学习与可视化中数据压缩、简化。但是PCA有一定的局限性,它需要你拥有特定领域的相关知识。对噪音比较多的数据并不适用。

    3.4、SVD矩阵分解(Singular Value Decomposition)

    也叫奇异值分解(Singular Value Decomposition),是线性代数中一种重要的矩阵分解,是矩阵分析中正规矩阵酉对角化的推广。在信号处理、统计学等领域有重要应用。SVD矩阵是一个复杂的实复负数矩阵,给定一个m行、n列的矩阵M,那么M矩阵可以分解为M = UΣV。U和V是酉矩阵,Σ为对角阵。

    在这里插入图片描述

    PCA实际上就是一个简化版本的SVD分解。在计算机视觉领域,第一个脸部识别算法就是基于PCA与SVD的,用特征对脸部进行特征表示,然后降维、最后进行面部匹配。尽管现在面部识别方法复杂,但是基本原理还是类似的。

    3.5、独立成分分析(ICA)

    独立成分分析(Independent Component Analysis,ICA)是一门统计技术,用于发现存在于随机变量下的隐性因素。ICA为给观测数据定义了一个生成模型。在这个模型中,其认为数据变量是由隐性变量,经一个混合系统线性混合而成,这个混合系统未知。并且假设潜在因素属于非高斯分布、并且相互独立,称之为可观测数据的独立成分。

    640 (5)

    ICA与PCA相关,但它在发现潜在因素方面效果良好。它可以应用在数字图像、档文数据库、经济指标、心里测量等。

    在这里插入图片描述

    上图为基于ICA的人脸识别模型。实际上这些机器学习算法并不是全都像想象中一样复杂,有些还和高中数学紧密相关。

    4、强化学习

    4.1、Q-Learning算法

    Q-learning要解决的是这样的问题:一个能感知环境的自治agent,怎样通过学习选择能达到其目标的最优动作。

    强化学习目的是构造一个控制策略,使得Agent行为性能达到最大。Agent从复杂的环境中感知信息,对信息进行处理。Agent通过学习改进自身的性能并选择行为,从而产生群体行为的选择,个体行为选择和群体行为选择使得Agent作出决策选择某一动作,进而影响环境。增强学习是指从动物学习、随机逼近和优化控制等理论发展而来,是一种无导师在线学习技术,从环境状态到动作映射学习,使得Agent根据最大奖励值采取最优的策略;Agent感知环境中的状态信息,搜索策略(哪种策略可以产生最有效的学习)选择最优的动作,从而引起状态的改变并得到一个延迟回报值,更新评估函数,完成一次学习过程后,进入下一轮的学习训练,重复循环迭代,直到满足整个学习的条件,终止学习。

    Q-Learning是一种无模型的强化学习技术。具体来说,可以使用Q学习来为任何给定的(有限的)马尔可夫决策过程(MDP)找到最优的动作选择策略。它通过学习一个动作价值函数,最终给出在给定状态下采取给定动作的预期效用,然后遵循最优策略。一个策略是代理在选择动作后遵循的规则。当这种动作值函数被学习时,可以通过简单地选择每个状态中具有最高值的动作来构建最优策略。 Q-learning的优点之一是能够比较可用操作的预期效用,而不需要环境模型。此外,Q学习可以处理随机过渡和奖励的问题,而不需要任何适应。已经证明,对于任何有限的MDP,Q学习最终找到一个最优策略,从总体奖励的预期值返回到从当前状态开始的所有连续步骤是最大可实现的意义。

    5、机器学习常用Python包

    5.1、sklearn

    开源机器学习模块,包括分类、回归、聚类系列算法,主要算法有SVM、逻辑回归、朴素贝叶斯、Kmeans、DBSCAN等;也提供了一些语料库。
    学习地址:https://scikit-learn.org/stable/modules/classes.html

    5.2、numpy

    Python的语言扩展,定义了数字的数组和矩阵。提供了存储单一数据类型的多维数组(ndarray)和矩阵(matrix)。
    学习地址:http://www.numpy.org/

    5.3、scipy

    其在numpy的基础上增加了众多的数学、科学以及工程计算中常用的模块,例如线性代数、常微分方程数值求解、信号处理、图像处理、稀疏矩阵等等。
    学习地址:https://www.scipy.org/

    5.4、pandas

    直接处理和操作数据的主要package,提供了dataframe等方便处理表格数据的数据结构
    学习地址:http://pandas.pydata.org/

    5.5、statsmodels

    统计和计量经济学的package,包含了用于参数评估和统计测试的实用工具
    学习地址:https://pypi.org/project/statsmodels/

    5.6、matplotlib、pyplot、pylab

    用于生成统计图。pyplot 和 pylab属于matplotlib的子模块,所以只需安装matplotlib,就会有pyplot和pylab的了。
    学习地址:https://matplotlib.org/

    5.7、jieba

    中文分词工具。
    学习地址:https://github.com/fxsjy/jieba

    5.8、Pattern

    此库更像是一个“全套”库,因为它不仅提供了一些机器学习算法,而且还提供了工具来帮助你收集和分析数据。数据挖掘部分可以帮助你收集来自谷歌、推特和维基百科等网络服务的数据。它也有一个Web爬虫和HTML DOM解析器。“引入这些工具的优点就是:在同一个程序中收集和训练数据显得更加容易。
    学习地址:https://github.com/clips/pattern

    6、各个算法精确率对比

    此次算精确率对比,总语料样本21282条,分类标签911个,语料是企业的语料集,不对外公开。精准率是把整体样本按照8:2的比例,分为80%的训练集,20%的测试集来算的,实验流程在每篇文章中都有详细记载。数据量低于21282的是取了总样本的部分数据做的实验,效果统计如下:

    6.1、支持向量机(SupportVectorMachine)

    6.1.1、升级版sklearn

    机器学习 之 支持向量机(SupportVectorMachine)文本算法的精确率——升级版sklearn
    在这里插入图片描述

    6.1.2、Liblinear

    机器学习 之 Liblinear中的支持向量机(SupportVectorMachine)文本算法的精确率
    在这里插入图片描述

    6.1.3、sklearn

    机器学习 之 sklearn中的支持向量机(SupportVectorMachine)文本算法的精确率
    在这里插入图片描述

    6.2、随机森林(Random Forest)

    机器学习 之 随机森林(Random Forest)文本算法的精确率
    在这里插入图片描述

    6.3、朴素贝叶斯(Naive Bayesian Model)

    机器学习 之 朴素贝叶斯(Naive Bayesian Model)文本算法的精确率
    在这里插入图片描述

    6.4、K近邻(K-NearestNeighbor)

    机器学习 之 K近邻(K-NearestNeighbor)文本算法的精确率
    在这里插入图片描述

    6.5、逻辑回归(LogisticRegression)

    机器学习 之 逻辑回归(LogisticRegression)文本算法的精确率
    在这里插入图片描述

    6.6、决策树(Decision Tree)

    机器学习 之 决策树(Decision Tree)文本算法的精确率
    在这里插入图片描述
    看完本文实属不易,写本文也耗费了我很多时间和精力,希望大家有钱场捧个钱场,有人场捧个人场,谢谢~

    7、推荐

    无意中发现了一个巨牛的人工智能教程,忍不住分享一下给大家。教程不仅是零基础,通俗易懂,而且非常风趣幽默,像看小说一样!觉得太牛了,所以分享给大家。点这里可以跳转到教程。

    展开全文
  • 蓝桥杯知识点汇总:基础知识和常用算法

    万次阅读 多人点赞 2020-01-21 14:59:45
    此系列包含蓝桥杯(软件类)所考察的绝大部分知识点,算法,和写算法题必须学会的JAVA的基础语法,API,对想从C/C++转到JAVA组以及初学算法的同学很有帮助。


    此系列包含蓝桥杯(软件类)所考察的绝大部分知识点,一共有基础语法常用API算法和数据结构,和往年真题四部分。
    语言以JAVA为主,对想从C/C++转到JAVA组的同学很有帮助,也适合初学者查阅一些算法模板和API。如果读者发现文章有误,请告知我,十分感谢。另外,有什么问题可私信我。欢迎催更~

    JAVA基础语法:

    备战蓝桥杯(一):一般输入输出 和 快速输入输出
    备战蓝桥杯(二):java编程规范和常用数据类型
    备战蓝桥杯(三):常用功能符以及循环结构和分支结构
    备战蓝桥杯(四):函数(方法)、类和对象

    算法竞赛常用的JAVA API:

    备战蓝桥杯(五):大数类
    备战蓝桥杯(六):Math类
    备战蓝桥杯(七):String 、StringBuilder、StringBuffer常用方法和区别
    备战蓝桥杯(八):Calendar日期类
    备战蓝桥杯(九):ArrayList(Vector)
    备战蓝桥杯j(十): HashMap 和 TreeMap
    备战蓝桥杯(十一):HashSet 和 TreeSet
    备战蓝桥杯(十二): PriorityQueue(优先队列)
    备战蓝桥杯(十三): sort方法和自定义比较器的写法

    算法和数据结构

    简单算法

    备战蓝桥杯(十四):递归
    备战蓝桥杯(十五):深度优先搜索(DFS)和宽度优先搜索(BFS)
    备战蓝桥杯(十六):位运算
    备战蓝桥杯(十七):二分
    备战蓝桥杯(十八):快速排序
    备战蓝桥杯(十九):归并排序

    简单数据结构

    备战蓝桥杯 (二十):用数组模拟单链表
    备战蓝桥杯 (二十一):用数组模拟栈和对列
    备战蓝桥杯 (二十二):哈希表
    备战蓝桥杯(二十三):并查集
    备战蓝桥杯(二十四):trie树

    图论

    备战蓝桥杯(二十五) :树和图的存储:邻接矩阵和邻接表
    备战蓝桥杯(二十六):最短路问题
    备战蓝桥杯(二十七):最小生成树
    备战蓝桥杯(二十八):二分图

    数学

    贪心

    备战蓝桥杯(三十八):贪心算法

    动态规划

    补充

    图论:拓扑排序

    省赛题解

    第十届蓝桥杯省赛JAVA B组题解

    第六届蓝桥杯省赛JAVA AB题解

    待更:

    1. 递归
    2. 搜索
    3. 位运算
    4. 二分
    5. 排序
    6. 贪心
    7. 动态规划
    8. 图论
    9. 数论
    10. 等

    另附:

    蓝桥杯考察范围
    在这里插入图片描述参赛选手机器环境
    在这里插入图片描述

    展开全文
  • 五大常用算法之三:贪心算法

    万次阅读 2018-03-14 13:11:26
    贪心算法一、基本概念: 所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法没有固定的算法框架,算法...

    贪心算法

    一、基本概念:
     
         所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解
         贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
        所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。


    二、贪心算法的基本思路:
        1.建立数学模型来描述问题。
        2.把求解的问题分成若干个子问题。
        3.对每一子问题求解,得到子问题的局部最优解。
        4.把子问题的解局部最优解合成原来解问题的一个解。


    三、贪心算法适用的问题
          贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
        实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。
     

    四、贪心算法的实现框架
        从问题的某一初始解出发;
        while (能朝给定总目标前进一步)
        { 
              利用可行的决策,求出可行解的一个解元素;
        }
        由所有解元素组合成问题的一个可行解;
      

    五、贪心策略的选择
         因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。
     

    六、例题分析
        下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
        [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
        要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
        物品 A B C D E F G
        重量 35 30 60 50 40 10 25
        价值 10 40 30 50 35 40 30
        分析:
        目标函数: ∑pi最大
        约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
        (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
        (2)每次挑选所占重量最小的物品装入是否能得到最优解?
        (3)每次选取单位重量价值最大的物品,成为解本题的策略。
        值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。
        贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。
        可惜的是,它需要证明后才能真正运用到题目的算法中。
        一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
        对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
        (1)贪心策略:选取价值最大者。反例:
        W=30
        物品:A B C
        重量:28 12 12
        价值:30 20 20
        根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
        (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
        (3)贪心策略:选取单位重量价值最大的物品。反例:
        W=30
        物品:A B C
        重量:28 20 10
        价值:28 20 10
        根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。


    本文转自这里http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html

    展开全文
  • 五大常用算法之一:分治算法

    万次阅读 2018-03-14 12:49:45
    分治算法一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单...
  • 五大常用算法之二:动态规划算法

    万次阅读 2018-03-14 12:52:53
    动态规划算法一、基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。二、基本思想与...
  • 五大常用算法入门(一)——贪心算法

    万次阅读 多人点赞 2019-02-25 21:48:13
    贪心算法简介1.1 基本定义1.2 贪心算法案例3.贪心算法的基本思路2.贪心算法最优性证明2.1 贪心算法的前提2.2 最优子结构2.3 贪心算法与动态规划的区别3.贪心算法的经典问题3.1 近似解3.2 最优解参考资料 1.贪心算法...
  • 算法07:常用算法排序

    万次阅读 2020-04-06 21:16:52
    文章目录一、十种排序算法比较二、排序算法的选择三、常用算法代码0. 输入输出函数的封装1. 冒泡排序算法步骤代码2. 插入排序算法步骤代码3. 归并排序算法步骤代码4. 快速排序算法步骤代码 一、十种排序算法比较 ​ ...
  • OI常用算法

    千次阅读 2019-11-24 17:00:58
    在OI中常用算法有以下几种: Dynamic Programming(动态规划) Greedy(贪心) Complete Search(搜索枚举) Flood Fill(漫水填充) Shortest Path(最短路径) Recursive Search Techniques(回溯搜索技术)...
  • 常用算法简述 -- 插入排序

    万次阅读 2018-03-12 16:49:57
    插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只...
  • 推荐系统中的常用算法——Wide & Deep

    万次阅读 2017-10-07 20:10:16
    这篇文章是阅读《Wide &amp; Deep Learning for Recommender Systems》后的总结,该文章中提出结合Wide模型和Deep模型的组合方法,对于提升推荐系统(Recommendation System)的性能有很重要的作用。...
  • 常用算法简述 -- 冒泡排序

    万次阅读 2018-03-12 14:56:30
    写在前面 排序算法种类繁多,根据处理的数据规模与存储特点,可分为内部排序和外部排序...而在云计算之类的环境中,待排序的数据是实时生成的,在排序算法开始运行时,数据并未完全就绪,而是随着排序算法本身的进...
  • 常用算法简述 -- 选择排序

    万次阅读 2018-03-12 15:34:28
    选择排序(英文:Selection Sort)是一种非常简单直观的排序算法。它的工作原理如下:首先在未排序序列(排序操作开始时,未排序序列就是完整的序列)中找到最小(大)元素,存放到排序序列的起始位置(根据具体循环...
  • 计算机图形学常用算法

    千次阅读 2017-01-08 08:17:37
    http://blog.csdn.net/orbit/article/details/7082678对学习计算机编程比较直观。1. C++标准模板库从入门到精通 http://edu.csdn.net/course/detail/33242.跟老菜鸟学C++http://edu.csdn.net/course/detail/29013. ...
  • c#要点总结和常用算法

    千次下载 2008-01-16 14:46:09
    呕心沥血的c# 和asp.net以及部分sql的要点总结和C#常用算法,C#实例代码。非常具体使用,大家一起研讨。
  • c语言常用算法整理

    千次阅读 多人点赞 2019-02-26 10:10:57
    这里整理c语言常用算法,主要有: 交换算法 查找最小值算法 冒泡排序 选择排序 插入排序 shell排序 (希尔排序) 归并排序 快速排序 二分查找算法 查找重复算法 代码如下: //交换 void swap(int *a, int *b){ int ...
  • 面试常用算法总结——排序算法(java版)
  • 单片机常用算法

    千次阅读 2018-03-22 08:53:13
    算法的描述:是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述,包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程.....
  • 算法思想有很多,业界公认的常用算法思想有8种,分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然8种只是一个大概的划分,是一个“仁者见仁、智者见智”的问题。 1.1 枚举算法思想 知识点讲解...
  • 图论常用算法

    千次阅读 2017-08-16 13:44:24
    图论常用算法 最小生成树 Prim算法(普利姆算法) 关键问题 Krustral算法(克鲁斯卡尔算法) 关键问题 最短路径 拓扑排序 关键路径 网络流问题 图论常用算法 最小生成树 首先, 什么是最小生成树 图论...
  • java常用算法整理

    万次阅读 2018-03-02 17:46:24
    做移动端的同学们经常会忽略算法使用,因为平时开发后台数据已经处理好了,前端更多的是动画逻辑,布局逻辑等,但是算法重要性毋庸置疑,好的运用算法可以增加程序效率和提升代码质量,这里整理一下常见的面试中遇到...
  • CTR常用算法

    千次阅读 2018-07-25 10:56:59
    广告点击率预估常用算法
  • 常用算法PK

    千次阅读 2012-05-23 19:52:20
    本篇博客主要讲分治法、动态规划法、贪心法、回溯法、分支限界法几种常用算法的原理,方便同学们理解每种算法的道理到底是怎么回事。 分治法:  将一个难以直接解决的大问题分解为一些规模较小的相同问题各个击破...
  • 机器学习简介及常用算法

    万次阅读 2016-12-15 10:02:09
    机器学习涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心...
  • iOS常用算法

    千次阅读 2018-08-17 15:35:33
    //冒泡排序  NSMutableArray *arr=[NSMutableArray arrayWithObjects:@"6",@"23",@"19",@"-7",@"103", nil];  for (int i=0; i&lt;... 
  • 常用算法程序集(C语言描述)

    千次下载 热门讨论 2008-02-01 16:58:58
    常用算法,C语言版的 附例子的源程序
  • Qt常用算法

    千次阅读 2017-11-20 20:54:19
    Qt中的和提供了一些常用算法和函数 此处只列举最常用的几个: 函数 说明 qAbs() 返回绝对值 qMax(a,b) 返回两个数中的最大值 qRound() 四舍五入取整 qSwap(a,b) 交换两个数的值
  • ACM 常用算法合集

    千次阅读 多人点赞 2018-04-12 20:31:16
    【基础算法】 模拟算法:点击这里 数据排序:点击这里 高精度计算:点击这里 递推算法:点击这里 递归算法:点击这里 贪心算法:点击这里 分治法:点击这里 二分查找:点击这里 三分查找:点击这里 尺取法...

空空如也

1 2 3 4 5 ... 20
收藏数 55,614
精华内容 22,245
关键字:

常用算法