精华内容
下载资源
问答
  • 文章目录1 分治算法的一般性描述1.1 分支算法的时间分析1.2 两类常见的递推方程与求解方法2 总结 1 分治算法的一般性描述 设分治算法为:Divide-and-Conquer§ 设计要点 原问题可以划分或者规约为规模较小的...

    本文主要描述分治算法的一般描述和分析方法。衔接上一篇文章:【算法设计与分析】13 分治策略的设计思想

    1 分治算法的一般性描述

    • 设分治算法为:Divide-and-Conquer§

    在这里插入图片描述

    • 设计要点
    1. 原问题可以划分或者规约为规模较小的子问题。其中子问题之间遵循以下的规则:

       	1. 子问题与原问题具有相同的性质
       	2. 子问题的求解彼此独立
       	3. 划分时,子问题的规模尽可能均衡
      
    2. 子问题较小时可以直接求解

    3. 子问题的解综合可以得到原问题的解

    4. 算法的实现:迭代或者递归

    1.1 分支算法的时间分析

    时间复杂度函数的递推方程:

    • W(n)=W(P1)+W(P2)+...+W(Pk)+f(n)W(n)=W(|P_1|)+W(|P_2|)+...+W(|P_k|)+f(n)
    • W(c)=CW(c)=C

    其中

    1. P1,P2,...PkwP_1,P_2,...P_kw为划分后产生的子问题
    2. f(n)f(n)为划分子问题以及将子问题的解综合得到原问题的解的总工足量
    3. 规模为c的最小子问题的工作两为:C

    1.2 两类常见的递推方程与求解方法

    • f(n)=inaif(ni)+g(n)(1)f(n) = \sum_i^n a_i f(n-i)+g(n){, (1)}
    • f(n)=af(nb)+d(n)(2)f(n)=af(\frac{n}{b}) + d(n){, (2)}

    例子:

    Hanoi塔,W(n)=2W(n1)+1W(n)=2W(n-1)+1
    二分检索,W(n)=W(n/2)+1W(n)=W(n/2)+1
    归并排序,W(n)=2W(n/2)+n1W(n)=2W(n/2)+ n-1

    那么这些递推方程如何求解?

    • 方程1:f(n)=inaif(ni)+g(n)f(n) = \sum_i^n a_i f(n-i)+g(n)
    1. 迭代法、递归树
    • 方程2:f(n)=af(nb)+d(n)f(n)=af(\frac{n}{b}) + d(n)
    1. 迭代法、换元法、递归树、主定理

    对于方程2,可以使用主定理,该定理可以很快求解出方程的解,前面的文章已经学习过主定理,这里再次提一下:

    • 对于方程T(n)=aT(n/b)+d(n)T(n)=aT(n/b)+d(n)
    1. 如果d(n)为常数:

    T(n)={O(nlogba),a1O(logn),a=1 T(n)= \begin{cases} O(n^{log_ba}), & \text {$a \not= 1$} \\ O(logn), & \text{a=1} \end{cases}

    1. 如果d(n) = c(n)

    T(n)={O(n),a < bO(nlogn),a=bO(nlogba),a>b T(n)= \begin{cases} O(n), & \text {a < b} \\ O(nlogn), & \text{a=b} \\O(n^{log_b{a}}), &\text{a>b} \end{cases}

    注:上述的logbalog_ba中的b是以b为底的意思,但是上面的公式显示的不明显。

    2 总结

    • 想要彻底理解分治算法的思想,还需要多做练习,后面的文章会结合具体的例子,来讲解分治算法的思想在具体应用中的使用
    展开全文
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法...

    分类算法

    分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法属于一种有监督的学习。分类算法的分类过程就是建立一种分类模型来描述预定的数据集或概念集,通过分析由属性描述的数据库元组来构造模型。分类的目的就是使用分类对新的数据集进行划分,其主要涉及分类规则的准确性、过拟合、矛盾划分的取舍等。分类算法分类效果如图所示。

    常用的分类算法包括:NBC(Naive Bayesian Classifier,朴素贝叶斯分类)算法、LR(Logistic Regress,逻辑回归)算法、ID3(Iterative Dichotomiser 3 迭代二叉树3 代)决策树算法、C4.5 决策树算法、C5.0 决策树算法、SVM(Support Vector Machine,支持向量机)算法、KNN(K-Nearest Neighbor,K 最近邻近)算法、ANN(Artificial Neural Network,人工神经网络)算法等。

    NBC算法

    NBC 模型发源于古典数学理论,有着坚实的数学基础。该算法是基于条件独立性假设的一种算法,当条件独立性假设成立时,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。
    NBC算法的优点

    1. NBC算法逻辑简单,易于实现;
    2. NBC算法所需估计的参数很少;
    3. NBC 算法对缺失数据不太敏感;
    4. NBC 算法具有较小的误差分类率;
    5. NBC 算法性能稳定,健壮性比较好;

    NBC算法的缺点
    1.在属性个数比较多或者属性之间相关性较大时,NBC 模型的分类效果相对较差;
    2.算法是基于条件独立性假设的,在实际应用中很难成立,故会影响分类效果

    LR算法

    LR 回归是当前业界比较常用的机器学习方法,用于估计某种事物的可能性。它与多元线性回归同属一个家族,即广义线性模型。简单来说多元线性回归是直接将特征值和其对应的概率进行相乘得到一个结果,逻辑回归则是在这样的结果上加上一个逻辑函数。在此选择LR 作为回归分析模型的代表进行介绍。
    LR算法的优点
    1.对数据中小噪声的鲁棒性好;
    2.LR 算法已被广泛应用于工业问题中;
    3.多重共线性并不是问题,它可结合正则化来解决。

    LR算法的缺点
    1.对于非线性特征,需要转换
    2.当特征空间很大时,LR的性能并不是太好

    SVM算法

    SVM 算法是建立在统计学习理论基础上的机器学习方法,为十大数据挖掘算法之一。通过学习算法,SVM 可以自动寻找出对分类有较好区分能力的支持向量,由此构造出的分类器可以最大化类与类的间隔,因而有较好的适应能力和较高的分准率。SVM 算法的目的在于寻找一个超平面H,该超平面可以将训练集中的数据分开,且与类域边界的沿垂直于该超平面方向的距离最大,故SVM 法亦被称为最大边缘算法。

    SVM算法的优点
    1.SVM 模型有很高的分准率;
    2. SVM 模型有很高的泛化性能;
    3. SVM 模型能很好地解决高维问题;
    4. SVM 模型对小样本情况下的机器学习问题效果好。

    SVM算法的缺点
    1.SVM 模型对缺失数据敏感;
    2.对非线性问题没有通用解决方案,得谨慎选择核函数来处理。

    ID3算法

    ID3 算法是一种基于决策树的分类算法,该算法是以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。信息增益用于度量某个属性对样本集合分类的好坏程度。ID3 算法的时间复杂度为O(n*|D|*log|D|)。

    ID3算法的优点

    1. ID3 算法建立的决策树规模比较小;
    2. 查询速度快。

    ID3算法的缺点
    1.不适合处理连续数据;
    2.难以处理海量数据集;
    3.建树时偏选属性值较大的进行分离,而有时属性值较大的不一定能反应更多的数据信息。

    C4.5 算法

    C4.5 算法是ID3 算法的修订版,采用信息增益率来加以改进,选取有最大增益率的分割变量作为准则,避免ID3 算法过度的适配问题。

    C4.5算法优点
    1.C4.5 继承了ID3 优点;
    2.在树构造过程中进行剪枝;
    3.能对不完整数据进行处理;
    4.能够完成对连续属性的离散化处理;
    5.产生的分类规则易于理解,准确率较高;
    6.用增益率来选择属性,克服了用增益选择属性时偏向选择取值多的属性。

    C4.5 算法缺点
    1.构造树时,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效;
    2.只适合于能驻留于内存的数据集,当训练集达到内存无法容纳时程序无法运行。

    C4.5 用于遥感分类过程中,首先依据通常的方式建立第一个模型。随后建立的第二个模型聚焦于被第一个模型错误分类的记录。以此类推,最后应用整个模型集对样本进行分类,使用加权投票过程把分散的预测合并成综合预测。Boosting 技术对于噪声不大的数据,通常通过建立的多模型来减少错误分类的影响,提高分类精度。

    C5.0算法

    C5.0 算法是 Quinlan 在C4.5 算法的基础上改进而来的产生决策树的一种更新的算法,它除了包括C4.5 的全部功能外,还引入许多新的技术,其中最重要的技术是提升(Boosting)技术,目的是为了进一步提高决策树对样本的识别率。同时C5.0 的算法复杂度要更低,使用更简单,适应性更强,因此具有更高的使用价值。

    C5.0算法的优点
    1.C5.0 模型能同时处理连续和离散的数据
    2.C5.0 模型估计
    模型通常不需要很长的训练时间;
    3.C5.0 引入Boosting 技术以提高分类的效率和精度;
    4.C5.0 模型易于理解,模型推出的规则有非常直观的解释;
    5.C5.0 模型在面对数据遗漏和特征很多的问题时非常稳健。

    C5.0算法的缺点
    目标字段必须为分类字段。

    美国地质调查局(USGS)在进行土地覆盖分类项目过程中研发了支持决策树分类的软件。软件分类模块主要是针对庞大数据量的数据集进行数据挖掘,找出特征,然后建立规则集进行决策分类。在分类模块中采用C5.0 模型来完成决策树分类、形成分类文件,实现遥感影像的分类。

    KNN 算法

    KNN 算法是Cover 和Hart 于1968 年提出的理论上比较成熟的方法,为十大挖掘算法之一。该算法的思路非常简单直观:如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

    KNN算法的优点
    1.KNN 算法简单、有效;
    2.KNN 算法适用于样本容量比较大的类域的自动分类;
    3.由于KNN 方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN 方法较其他方法更为适合。

    KNN算法的缺点
    1.KNN 算法计算量较大;
    2.KNN 算法需要事先确定K 值;
    3.KNN 算法输出的可解释不强;
    4. KNN 算法对样本容量较小的类域很容易产生误分。

    ANN 算法

    人工神经网络(ANN)算法就是一组连续的输入/输出单元,其中每个连接都与一个权相关。在学习阶段,通过调整神经网络的权,使得能够预测样本的正确类标号来学习。

    ANN算法的优点
    1.能处理数值型及分类型的属性;
    2.分类的准确度高,分布并行处理能力强;
    3.对包含大量噪声数据的数据集有较强的鲁棒性和容错能力。

    ANN算法的缺点
    1.不能观察之间的学习过程;
    2.学习时间过长,甚至可能达不到学习的目的;
    3.对于非数值型数据需要做大量数据预处理工作;
    4.输出结果难以解释,会影响到结果的可信度和可接受程度;
    5.神经网络需要大量的参数,如网络拓扑结构、权值和阈值的初始值。

    小结:

    算法名称 收敛时间 是否过度拟合 是否过渡拟合缺失数据敏感度 训练数据量
    NBC 存在 不敏感 无要求
    LR 存在 敏感 无要求
    SVM 一般 存在 敏感 小数据量
    ID3 存在 不敏感 小数据集
    C4.5 存在 不敏感 小数据集
    C5.0 不存在 不敏感 大数据集
    ANN 存在 敏感 大数据集
    KNN 存在 敏感 数据量多

    创建了一个技术闲聊群:有兴趣可加我微信,拉你一起讨论杂七杂八的技术,虽然大家都不怎么活跃!
    加好友备注:你的博客名 && 随便给我的任意文章点个赞或留言
    在这里插入图片描述

    展开全文
  • 常用的图像处理算法: 1、图像变换:(空域和频域、几何变换、色度变换) 几何变换:图像平移、旋转、镜像、转置; 尺度变换:图像缩放、插值算法(最近邻插值、线性插值、双三次插值); 2、图像增强: 灰度...

    机器视觉工业缺陷检测的那些事(四、常用算法与库)

    目录

    机器视觉工业缺陷检测的那些事(四)

    二、算法(预处理算法、检测算法)

    常用的图像处理算法:

    1、图像变换:(空域和频域、几何变换、色度变换、尺度变换)

    2、图像增强:

    3、纹理分析(取骨架、连通性);

    4、图像分割:

    5、图像特征:

    6、图像/模板匹配:

    7、色彩分析

    8、图像数据编码压缩和传输

    9、表面缺陷目标识别算法:

    10、图像分类(识别)

    11、图像复原

    三、现有可用的视觉检测软件/库

    1、做工业视觉检测的公司有哪些?

    2、常用的视觉检测软件/库

    HSV颜色识别-HSV基本颜色分量范围

    【骆驼走得慢,但终能走到目的地。 】


    机器视觉工业缺陷检测的那些事(四)

    二、算法(预处理算法、检测算法)

    常用的图像处理算法:

    1、图像变换:(空域与频域、几何变换、色度变换、尺度变换)

    1. 几何变换:图像平移、旋转、镜像、转置;
    2. 尺度变换:图像缩放、插值算法(最近邻插值、线性插值、双三次插值);
    3. 空域与频域间变换:由于图像阵列很大,直接在空间域中进行处理,涉及计算量很大。因此,有时候需要将空间域变换到频域进行处理。例如:傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术,将空间域的处理转换为频域处理,不仅可减少计算量,而且可获得更有效的处理(如傅立叶变换可在频域中进行数字滤波处理)。

    2、图像增强:

    图像增强不考虑图像降质的原因,突出图像中所感兴趣的部分。如强化图像高频分量,可使图像中物体轮廓清晰,细节明显;如强化低频分量可减少图像中噪声影响。

    1. 灰度变换增强(线性灰度变换、分段线性灰度变换、非线性灰度变换);
    2. 直方图增强(直方图统计、直方图均衡化);
    3. 图像平滑/降噪(邻域平均法、加权平均法、中值滤波、非线性均值滤波、高斯滤波、双边滤波);
    4. 图像(边缘)锐化:梯度锐化,Roberts算子、Laplace算子、Sobel算子等;

    3、纹理分析(取骨架、连通性);

    4、图像分割:

    图像分割是将图像中有意义的特征部分提取出来,其有意义的特征有图像中的边缘、区域等,这是进一步进行图像识别、分析和理解的基础。

    (1)阈值分割(固定阈值分割、最优/OTSU阈值分割、自适应阈值分割);

    (2)基于边界分割(Canny边缘检测、轮廓提取、边界跟踪);

    (3)Hough变换(直线检测、圆检测);

    (4)基于区域分割(区域生长、区域归并与分裂、聚类分割);

    (5)色彩分割;

    (6)分水岭分割;

    5、图像特征:

    (1)几何特征(位置与方向、周长、面积、长轴与短轴、距离(欧式距离、街区距离、棋盘距离));

    (2)形状特征(几何形态分析(Blob分析):矩形度、圆形度、不变矩、偏心率、多边形描述、曲线描述);

    (3)幅值特征(矩、投影);

    (4)直方图特征(统计特征):均值、方差、能量、熵、L1范数、L2范数等;直方图特征方法计算简单、具有平移和旋转不变性、对颜色像素的精确空间分布不敏感等,在表面检测、缺陷识别有不少应用。

    (5)颜色特征(颜色直方图、颜色矩)

    (6)局部二值模式( LBP)特征:LBP对诸如光照变化等造成的图像灰度变化具有较强的鲁棒性,在表面缺陷检测、指纹识别、光学字符识别、人脸识别及车牌识别等领域有所应用。由于LBP 计算简单,也可以用于实时检测。

    6、图像/模板匹配:

    轮廓匹配、归一化积相关灰度匹配、不变矩匹配、最小均方误差匹配

    7、色彩分析

    色度、色密度、光谱、颜色直方图、自动白平衡

    8、图像数据编码压缩和传输

    图像编码压缩技术可减少描述图像的数据量(即比特数),以便节省图像传输、处理时间和减少所占用的存储器容量。压缩可以在不失真的前提下获得,也可以在允许的失真条件下进行。编码是压缩技术中最重要的方法,它在图像处理技术中是发展最早且比较成熟的技术。

    9、表面缺陷目标识别算法:

    传统方法:贝叶斯分类、K最近邻(KNN)、人工神经网络(ANN)、支持向量机(SVM)、K-means等;

    10、图像分类(识别)

    图像分类(识别)属于模式识别的范畴,其主要内容是图像经过某些预处理(增强、复原、压缩)后,进行图像分割和特征提取,从而进行判决分类。

    11、图像复原

    图像复原要求对图像降质的原因有一定的了解,一般讲应根据降质过程建立“降质模型”,再采用某种滤波方法,恢复或重建原来的图像。

    三、现有可用的视觉检测软件/库

    1、做工业视觉检测的公司有哪些?

    比较出名的有:大恒图像(亚洲Halcon最大代理商)、凌云光技术(VisionPro视觉平台:印刷、3C电子、显示屏、玻璃、线路板检测)、大族激光(振静系统:视觉激光焊接,定视觉位、缺陷检测)、康耐视、基恩士、深圳精锐视觉、深圳市视觉龙科技有限公司、广州超音速、深圳市创科自动化等等。

    可二次开发的视觉系统:Labview、DVT、Halcon、OpenCV等。

    2、常用的视觉检测软件/库

    视觉开发软件工具 Halcon、VisionPro、LabView、OpenCV, 还有eVision、Mil、Sapera等。

    (一)、Halcon:底层功能算法多,运算性能快,功能齐全,容易上手,开发项目周期短。非开源项目,商用收费,价格较贵。

             Halcon:Halcon是德国MVtec公司开发的一套完善的标准的机器视觉算法包,拥有应用广泛的机器视觉集成开发环境。它是一套image processing library,由一千多个各自独立的函数,以及底层的数据管理核心构成。其中包含了各类滤波,色彩以及几何,数学转换,型态学计算分析,校正,分类辨识,形状搜寻等等基本的几何以及影像计算功能。整个函数库可以用C,C++,C#,Visual basic和Delphi等多种普通编程语言访问。 Halcon为大量的图像获取设备提供接口,保证了硬件的独立性。

    (二)OpenCV:功能算法相对较多(比Halcon少),开源,可用于商用,开发周期较长(比Halcon长),有些算法要自己写。

            OpenCV是一个基于(开源)发行的跨平台计算机视觉库,可以运行在Linux、Windows和Mac OS操作系统上。其核心轻量级而且高效——由一系列 C 函数和少量 C++ 类构成,实现了图像处理和计算机视觉方面的很多通用算法。OpenCV用C++语言编写,它的主要接口也是C++语言。该库也有大量的Python, Java and MATLAB/OCTAVE的接口,如今也提供对于C#, Ruby的支持。OpenCV可以在 Windows, Android, Maemo, FreeBSD, OpenBSD, iOS,Linux 和Mac OS等平台上运行。

    OpenCV出身:OpenCV是Intel开源计算机视觉库。 其核心由一系列 C 函数和少量 C++ 类构成,实现了图像处理和计算机视觉方面的很多通用算法。 OpenCV 的特点拥有包括300多个C函数的跨平台的中、高层 API 跨平台:Windows, Linux; 免费(FREE):无论对非商业应用和商业应用;速度快;使用方便。

    OpenCV具有以下的特征: (1)开源计算机视觉采用C/C++编写。 (2)使用目的是开发实时应用程序。 (3)独立与操作系统、硬件和图形管理器。 (4)具有通用的图象/视频载入、保存和获取模块。 (5)具有底层和高层的应用开发包。

    应用OpenCV能够实现以下功能: (1)对图象数据的操作,包括分配、释放、复制和转换数据。 (2)对图象和视频的输入输出,指文件和摄像头作为输入,图象和视频文件作为输出。 (3)具有对距陈和向量的操作以及线性代数的算法程序,包括距阵、解方程、特征值以及奇异值。 (4)可对各种动态数据结构,如列表、队列、集合、树和图等进行操作。 (5)具有基本的数字图象处理能力,如可进行滤波、边缘检测、角点检测、采样与差值、色彩转换、形态操作、直方图和图象金字塔等操作。

    (6)可对各种结构进行分析,包括连接部件分析、轮廓处理、距离变换、各种距的计算、模板匹配、Hongh变换、多边形逼近、直线拟合、椭圆拟合和Delaunay三角划分等。 (7)对摄像头的定标,包括发现与跟踪定标模式、定标、基本矩阵估计、齐次矩阵估计和立体对应。 (8)对运动的分析,如对光流、运动分割和跟踪的分析。 (9)对目标的识别,可采用特征法和隐马尔科夫模型(HMM)法。 (10)具有基本的GUI功能,包括图像与视频显示、键盘和鼠标事件处理及滚动条等。 (11)可对图像进行标注,如对线、二次曲线和多边形进行标注,还可以书写文字(目前之支持中文)。

    (三)VisionPro
             VisionPro是美国康耐视Cognex公司提供全套视觉解决方案。VisionPro提供多种开发工具拖放式界面、简单指令码和编程方式等,全面支持所有模式的开发。用户利用VisionPro QuickBuild™可以无需编程配置读取、选择并优化视觉工具,决定产品是否合格。用户也可以利用C++、C#、VB及.NET开发管理应用程序。Vision Pro提供的.NET程序接口允许用户采用面向对象的高级语言编程访问所有工具,以高效开发客户的专用视觉方案。

    (四)LabView

             LabView是一种程序开发环境,由美国国 家仪器(NI)公司研制开发,使用的是图形化编辑语言G编写程序,产生的程序是框图的形式。 LabView软件是NI设计平台的核心,也是开发测量或控制系统的理想选择。 LabView开发环境集成了工程师和科学家快速构建各种应用所需的所有工具,旨在帮助工程师和科学家解决问题、提高生产力和不断创新。

     

     

     

    HSV颜色识别-HSV基本颜色分量范围

    一般对颜色空间的图像进行有效处理都是在HSV空间进行的,然后对于基本色中对应的HSV分量需要给定一个严格的范围,下面是通过实验计算的模糊范围(准确的范围在网上都没有给出)。

    H:  0 — 180

    S:  0 — 255

    V:  0 — 255

    HSV(色相/饱和度/明度)颜色空间是表示类似于RGB颜色模型的颜色空间的模型。根据色相通道(Channel)对颜色类型进行建模,因此在需要根据颜色对对象进行分割的图像处理任务中非常有用。饱和度的变化代表颜色成分的多少。明度通道描述颜色的亮度。

     

     

     

    【骆驼走得慢,但终能走到目的地。 】

     

     

     

     

    展开全文
  • 递归算法描述与实现

    千次阅读 2012-11-09 16:52:02
    递归算法在C/C++程序设计巾硇描述与实现 [摘要]递归是函数实现的一个很重要的环节,对许多复杂的问题,递归能提供简单、自然的解法。本文在对递归的概念进行介绍的基础上,重点讨论了递归的程序设计方法,并分析了...

    递归算法在C/C++程序设计巾硇描述与实现

    [摘要]递归是函数实现的一个很重要的环节,对许多复杂的问题,递归能提供简单、自然的解法。本文在对递归的概念进行介绍的基础上,重点讨论了递归的程序设计方法,并分析了递归函数的调用和回溯过程。
    [关键词]递归 函数调用 C/C++

    1.引言
    递归是计算机科学中一种强有力的问题求解方法,用递归算法编写的程序结构清晰,具有很好的可读性,正确性容易验证。但由于递归的设计思想比较巧妙,特别是对于规模较大的问题,掌握递归算法的设计分析和实现过程并非易事,因此,有必要对其进行深入探讨,分析其概念及设计方法和实现过程,以此加深对递归算法思想的进一步理解,学会正确应用递归解决实际问题的方法。
    2.递归的概念
    如果一个对象部分地由自己组成或者是根据自己定义的,则称这个对象是递归的;在程序设计中,若一个过程直接地或间接地调用自身,则称这个过程是递归的过程。在C/C++程序中,因为每次调用函数时,c ++语言都会为参数和局部变量分配新的存储区空间,因此函数调用它自身是可能的。这种类型的函数称为递归(recursive)函数。当函数调用它自身时,这个过程称为直接递归(direct recursion)。同样,函数能够调用第二个函数,反过来第二个函数也可以调用第一个函数。这种类型的递归称为间接(indirect)递归。
    通常如下两种情况会用到递归:
    (1)问题的定义是递归的。
    许多数学上常用的概念是递归定义的。如阶乘函数的常见定义:
    . f 1, 当n=0时
    In (n一1)!, 当n≥1时
    这种定义方法是用阶乘函数自身定义了阶乘函数。由于n!和(n一1)!
    都是同一个问题的求解,因此可将n!用递归函数来描述。程序代码如下:
    【例1】用递归函数编程求n的阶乘n!。
    long factorial(int n)
    (
    1ong result=0;
    if(O==n)
    result=1;
    else
    result=n*lfactorial(n一1)j//调用自身
    return result;
    )
    (2)问题的解法是递归的。
    例如有序表上的二分查找过程:确定查找区间的中心位置,用待查找数据与中心位置上的数据比较,若两者相等则查找成功;否则若前者小于后者,则把查找区间定为原查找区间的前半部分,继续重复之前的查找过程;若前者大于后者,则把查找区间定为原查找区间的后半部分,继续重复之前的查找过程。在这里我们可以发现,对当前区间的查找过程与当前区间的前半部分或后半部分的查找过程是同一个问题的求解,因此可以将这一过程设计用递归函数来描述。
    上述两种情况的求解过程中有一个共同的特点:都可以将待求解问题分解为形式更加简单的子问胚,而子问题的求解方法与原问题的求解方法又是相同的。有时一个问题的求解过程可以化为较小问题的求解过程,而较小问题的求解过程又可化为更小问题的求解过程,依次类推。这种有规律地将原问题逐渐化小的过程,并且求解小问题的方法与求解大问题的方法相同,则称为递归求解过程。由于在递归过程中,求解的问题越化越小,最后不需要再向下递归而能够直接得到一个最小问题的解;然后再逐层向上返回,依次得到较大问题的解,因此最终得到原有问题的解。
    3.递归的设计方法
    能采用递归描述的算法通常有这样的特征:把规模大的、较难解决的问题分解成规模较小的、易解决的同一问题。规模较小的问题又用同
    样的方法分解成规模更小的问题,并且小到一定程度可以直接得出它
    的解,从而得到原来问题的解。特别地,当规模N=I时,能直接得解。
    当一个问题存在上述构成递归的特征时,我们就可以考虑利用递
    归进行处理。由此我们分析适宜用递归求解问题的充要条件是:其一,
    问题具有某种可借用的类同自身的子问题描述的性质;其二,某一有限
    步的子问题有直接的解存在。
    当一个问题存在上述两个基本要素时,设计该问题递归算法的方
    法是:
    (1)设计递归公式。即将一个问题化解为一个或多个子问题求解,
    且子问题和原问题具有相同的解法。例如,前面【例1】的n!可化解为n
    (n一1)!,其中,子问题n一1)!和n!的解法相同。
    (2)设计递归出口。即递归终止条件(边界条件)。递归最后一级的
    调用必须不能再进行递归,递归函数必须返回。不能无穷递归。
    在通常情况下,递归调用都是要受到条件控制的,而且在被调用的
    过程中,会对调用条件进行有规律的修改,即每递归一次要使递归趋于
    结束,直到满足边界条件,返回边界值,结束递归;然后按照原来的路径
    逐层返回,求出原问题的解。由此可知,递归算法设计的关键在于递归
    描述(递归公式)和递归终止条件。
    一般地,用递归方法进行“问题求解”时,具体需要依次进行下列三
    个步骤。
    (1)化解问题,求得算法
    当问题化解成子问题后,有的可以写出一个迭代公式。如阶乘n!,
    可写迭代公式f(n)=n f(n一1)。
    有的可以归于一个操作的循环。例如,若将一个十进制数n转换为
    二进制数输出,则可有下列循环:①输出n的2的余数(n%2);②将n
    向右移一位或求n/2,若结果为O,输出后结束;若结果不为O,则转步骤
    ① 。程序代码如下:
    【例2】将十进制数I1转换为二进制输出。
    #include<iostream>
    using namespace std;
    void d2b(int n】;
    intmain()
    (
    d2b(147);
    return 0:
    }
    void d2b(int n)
    (
    if((0==n)lI(1==n))
    cout<<n;
    else 、
    f
    d2b(n/2);
    cout<<n%2;//注意输出语句与递归调用语句的位置关系
    }
    }
    程序运行结果:1001001 1
    无论是上述的哪一种情况,我们都可以看出每次递归在规模上都
    有所缩小(通常是减半),而且相邻两次递归之间有紧密的联系,前一次
    要为后一次做准备(通常前一次的输出就作为后一次的输入)。
    (2)规划递归路线
    有些问题无须返回值,它要求完成相应的递归操作,类似递推,称为递归过程。无论是递归过程还是递归函数,递归路线可以有一条或多
    条。如【例1】中的F orial函数,自身调用语句只有一条,也就是递归路
    线只有一条。若递归函数或过程中自身调用语句不止一条,则可形成多
    条递归路线。但是每次递归的时候只有一条路线起作用。如二分查找用
    递归算法实现时,由于待查找数据与中心位置数据的比较结果不止一
    个,所以就会形成多条递归路线,但每次调用只有一条路线会被执行
    到。
    需要说明的是,由于递归调用是在栈内存空间中完成的,而栈的工
    作原理是先进后出,因此当递归路线中需要输出时,输出语句放在递归
    函数调用语句之前和之后次序是刚好相反的。如【例2】函数d2b中,若
    语句“eout<<n%2;”,放在递归调用语句“d2b(11/2);”之前,则递归后
    “cout<<n%2;”从左至右输出最低位到最高位的值。显然,这样输出次序
    是颠倒的。应将语句“cout<<n%2;”放在递归调用语句之后,利用栈的先
    进后出原理,从而输出正确的次序。
    (3)确定形参,设计递归终止条件
    在问题的规模极小时必须直接给出解答而不再进行递归调用,因
    而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),
    无条件递归调用将会成为死循环而不能正常结束。递归过程或递归函
    数的参数值在递归过程中必须是按规律变化的,且参数值的增/减方
    向应与递归终止条件相匹配,这样才能控制递归调用。如【例2】递归函
    数d2b中的形参n,每次递归调用时n值减半,直到n等于0或1为止,
    递归终止。
    一般递归函数设计的格式为:
    说明:若递归路线为多条,则else分支不止一个。
    4.递归过程
    递归函数在实现过程中需多次进行自我调用,因而正确理解递归
    调用及回溯过程是十分重要的。
    由函数调用的内部机制我们知道函数调用是在栈内存空间中完成
    的,栈的工作原理是先进后出。当调用一个函数时,整个调用过程分为
    三步进行:调用初始化、执行函数调用、调用后处理。高级程序设计语言
    利用堆栈保存递归函数调用时的信息,系统中用于保存递归函数调用
    信息的堆栈称为运行时栈。
    递归函数调用时,系统的运行时栈会将函数的返回地址、本次函数
    调用时的实参值、被调用函数的局部变量值三种信息构成一个工作记
    录存人栈中,在每进入下一层递归调用时就建立一个新的工作记录,并
    把这个工作记录进栈成为运行时栈的新栈顶;每退出一层递归调用,即
    函数调用返回时,系统运行时栈需要保存函数的返回值、释放实参和局
    部变量的内存空间,释放栈空间,然后按照之前所保存的返回地址返
    回,完成一个工作记录的退栈。因为栈顶的工作记录必定是在当前运行
    层的工作记录,所以栈顶的工作记录称为活动记录。
    由于函数的地址是系统动态分配的,调用函数的返回地址因此也
    是动态变化的,不好给出具体数值,所以我们仅以递归函数调用时形参
    的内存地址作为考查对象,来分析一下递归函数的调用和回溯过程。
    为了能看清楚递归函数在运行过程中调用和返回的情况,这里将
    【例l】中函数factorial的代码修改如下(斜体阴影部分),其中begin、end
    两个静态局部变量分别表示递归函数的调用序号和返回序号,用&n获
    取参数n的地址。
    #include<iostream>
    using namespace std;
    long factorial(int n);
    intmain()
    {
    cout<<”4『一”<<factorial(4)<<endl;
    return O:
    }
    long factorial(int n)

    long resuh=0;
    retum resuk;
    )
    程序运行结果如下:
    调用序号1 O012FF2C factoriall(41
    调用序号2 0012FECC factorial(3)
    调用序号3 O012FE6C factorial(2)
    调用序号4 0012FEOC factorial(1)
    调用序号5 O012FDAC factorialf0)
    返回序号l 0012FDAC factorial(0)=l
    返回序号2 0012FEOC factorial(1)=l
    返回序号3 0012FE6C factorialf2)=2
    返回序号4 0012FECC factorial(3)=6
    返回序号5 0012FF2C factorial(4)=24
    4『_24
    由以上运行结果可见,尽管函数factorial递归调用时的形参都是
    n,但每次调用系统会为其分配不同的内存空间。程序第一次调用 一
    torial函数计算41,即调用函数factorial(41,形参n接受传递的实参值4,
    因n=4,不等于0,故执行“resuh=4*factorial(3);”,并未直接得到factorial
    (4)的结果,而是要继续调用factorial(3)。同理,在进行函数factorialO)调
    用时,又因为要执行“resuh=3*factorial(2);”而无法直接得到factorial(3)的
    结果,需继续调用函数factorial(2),依次类推。直到进行函数factorial(0)
    调用时,形参n=O,故执行result=l,继而执行“retum resuh;”,到此时,才
    第一次得到了函数factorial的返回结果,但此时得到的结果factorial(O),
    是5次函数调用中最后一次的调用结果,而第一次函数调用factorial(4)
    将会在最后得到运行结果。由此证明,递归函数是按照“后调用先返回”
    的原则进行调用和回溯的。
    结合上述例子,递归算法的执行过程是不断地自调用,直到到达递
    归出口才结束自调用过程;到达递归出口后,递归算法开始按最后调用
    的过程最先返回的次序返回;返回到最外层的调用语句时递归算法执
    行过程结束。
    5.结束语
    在选择递归结构进行程序设计时,要考虑到“可理解性和效率”之
    间的关系。递归的能力在于能用有限的语句来定义对象的无限集合。用
    递归思想写出的程序往往十分简洁易懂。但需要注意的是,递归是一种
    代码简短的程序设计方法,但它执行起来效率并不高,因为递归每次调
    用都要进行调用初始化、执行函数代码、调用后处理这三步,不仅耗费
    机时,而且也占用较多的栈空间,递归次数过多容易造成栈溢出。所以
    如果采用递归算法设计程序,还需要控制问题的规模。

    展开全文
  • 游戏常用算法

    万次阅读 2013-09-11 12:50:51
    算法一:A*寻路初探 译者序:很久以前就知道了A*算法,但是从未认真读过相关的文章,也没有看过代码,只是脑子里有个模糊的概念。这次决定从头开始,研究一下这个被...毫无疑问,作者用形象的描述,简洁诙谐的语言由浅
  • 演化算法是一种具有鲁棒性的随机搜索优化算法,它通过模拟大自然的生物进化过程,依据简单的遗传操作和优胜劣汰的自然选择法则来寻求问题的最优解。 演化算法具有适于高度并行与自组织、自学习、自适应等特征。 一...
  • 常用算法的特点及适用场景

    千次阅读 2019-04-01 14:04:26
    本文主要回顾下几个常用算法的适应场景及其优缺点! 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。...
  • 常见数据挖掘算法分析 概述 一般认为,数据挖掘领域所使用的方法均属于机器学习算法、深度学习算法和数据挖掘算法。 一般认为,数据挖掘领域的问题主要有分类、回归、聚类、推荐、图像识别、预测。 一般认为,...
  • 机器学习常用算法对比

    千次阅读 2018-06-02 22:16:34
    转自http://www.csuldw.com/2016/02/26/2016-02-26-choosing-a-machine-learning-classifier/侵权删除本文主要回顾下几个常用算法的适应场景及其优缺点!(提示:部分内容摘自网络)。机器学习算法太多了,分类、...
  • 常见分类算法优缺点

    千次阅读 2018-10-21 21:36:54
    本文主要回顾下几个常用算法的适应场景及其优缺点! 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。...
  • 工业大数据分析综述:模型与算法

    千次阅读 2018-12-13 13:03:18
    工业大数据分析综述:模型与算法王宏志,梁志宇,李建中,高宏哈尔滨工业大学计算机科学与技术学院,黑龙江 哈尔滨 150001摘要:随着条形码、二维码、RFID、工业传感器...
  • 8种常见算法比较

    万次阅读 2016-08-09 17:42:38
    8种常见机器学习算法比较 2016-08-04 17:46 转载 陈圳 0条评论 雷锋网(搜索“雷锋网”公众号关注)按:本文转自刘志伟责编,在机器学习中选择一个恰当的算法十分重要,文中主要介绍了8种计算机算法...
  • 几种经典常用加密算法

    千次阅读 2015-10-27 11:08:17
     MD5将任意长度的“字节串”变换成一个128bit的大整数,并且它是一个不可逆的字符串变换算法,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说
  • 本文总结了常用的数学模型方法和它们的主要用途,主要包括数学和统计上的建模方法,关于在数学建模中也挺常用的机器学习算法暂时不作补充,以后有时间就补。至于究竟哪个模型更好,需要用数据来验证,还有求解方法也...
  • 数据挖掘常用算法优缺点分析

    万次阅读 2017-06-18 21:22:29
    常用的机器学习、数据挖掘方法有分类,回归,聚类,推荐,图像识别等。在实际应用中,一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普遍认同的算法,诸如SVM,GBDT,Adaboost,现在深度学习很火热,...
  • 本文主要回顾下几个常用算法的适应场景及其优缺点! 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。...
  • 算法

    千次阅读 2013-12-12 16:51:34
    算法 译自From Wikipedia, the free encyclopedia   一种计算在位置名为A和B的两个数字a 和b的最大公约数 (g.c.d.) 的算法(欧几里得的算法)的流程图。  该算法通过在两个循环中连续减进行的:如果测试B≥A产生...
  • 进化算法

    千次阅读 2017-06-27 16:03:31
    进化算法,也被成为是演化算法...与传统的基于微积分的方法和穷举方法等优化算法相比,进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法,具有自组织、自适应、自学习的特性,能够不
  • 请注意,我们不要求在算法具有新颖性。相反,我们的贡献在于首先确定单步跟踪器背后的挑战,然后将在计算机视觉的不同领域开发的多种技术和概念组合在一起,以解决以前的MOT工作中忽略的挑战。 我们的方法的概述如...
  • 常见机器学习算法比较

    千次阅读 2016-07-17 15:14:36
    本文主要回顾下几个常用算法的适应场景及其优缺点!(提示:部分内容摘自网络)。 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们...
  • 几个常用算法的适应场景及其优缺点(非常好)

    万次阅读 多人点赞 2016-10-25 10:03:58
    本文主要回顾下几个常用算法的适应场景及其优缺点! 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验...
  • 智能优化算法:灰狼优化算法-附代码

    万次阅读 多人点赞 2020-07-31 16:31:41
    GWO算法具有结构简单、需要调节的参数少,容易实现等特点,其中存在能够自适应调整的收敛因子以及信息反馈机制,能够在局部寻优与全局搜索之间实现平衡,因此在对问题的求解精度和收敛速度方面都有良好的性能。...
  • 进化算法之遗传算法

    2020-03-30 17:00:41
    进化算法 ​ 进化算法,也被成为是演化算法(evolutionary algorithms,简称EAs),...与传统的基于微积分的方法和穷举方法等优化算法相比,进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法,具有自组...
  • 迭代算法与递归算法的概念及区别

    万次阅读 多人点赞 2019-04-30 14:19:20
     利用迭代算法处理问题,需要做好以下三个方面的做:  一、确定迭代变量。在能够用迭代算法处理的问题中,至少具有一个间接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。  二、建...
  • 8种常见机器学习算法比较

    万次阅读 多人点赞 2016-10-26 20:35:41
    机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普遍认同的算法,诸如SVM...
  • 智能优化算法

    万次阅读 多人点赞 2018-09-03 21:27:12
    智能优化算法 目录 智能优化算法 目录 遗传算法(Genetic Algorithm) 理论 特点 领域 算法流程 差分进化算法(Differential Evolution Algorithm) 理论 特点 领域 算法流程 免疫算法(Immune Algorithm,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,306
精华内容 13,722
关键字:

常用的算法描述工具有