第一篇：总结 图像配准算法范文
图像配准定义为：对从不同传感器、不同时相、不同角度所获得的两幅或多幅图像进行最佳匹配的处理过程[2]。图像配准需要分析各分量图像上的几何畸变，然后采用一种几何变换将图像归化到统一的坐标系统中。在配准过程中，通常取其中的一幅图像作为配准的标准，称之为参考图像；另一幅图像作为配准图像。
图像的获取参考图像输入图像 图像的预处理 特征提取 特征匹配 空间变换模型类型的确定 模型参数的估计 图像的插值与变换 配准结果 配准系统的评价 图像配准
图1-1 图像配准的基本流程
图像配准算法分类按全局与局部划分按配准的四要素划分从自动化角度划分全局配准点点匹配搜索空间特征空间搜索策略相似性度量互相关函数绝对差和相位相关Hausdorff距离…手工配准刚性变换仿射变换投影变换多项式变换局部变换灰度特征区域特征线特征点特征…穷尽搜索逐级求精树图匹配动态规划…半自动配准自动配准
图1-2 图像配准方法分类-根据配准使用的特征，图像配准的方法大致可分为三类：
(1)基于图像灰度的配准算法。首先从参考图像中提取目标区作为配准的模板，然后用该模板在待配准图像中滑动，通过相似性度量(如相关系数法、差的平方和法、差的绝对值法、协方差法)来寻找最佳匹配点。
(2)基于图像特征的配准算法。该算法是以图像中某些显著特征(点、线、区域)为配准基元，算法过程分为两步：特征提取和特征匹配。首先从两幅图像中提取灰度变化明显的点、线、区域等特征形成特征集。然后在两幅图像对应的特征集中利用特征匹配算法尽可能地将存在对应关系的特征对选择出来。对于非特征像素点利用插值等方法作处理推算出对应匹配关系，从而实现两幅图像之间逐像素的配准。
(3)基于对图像的理解和解释的配准算法。这种配准算法不仅能自动识别相应像点，而且还可以由计算机自动识别各种目标的性质和相互关系，具有极高的可靠性和精度。这种基于理解和解释的图像配准涉及到诸如计算机视觉、模式识别、人工智能等许多领域。不仅依赖于这些领域中理论上的突破，而且有待于高速度并行处理计算机的研制。
从自动化角度来看，可以将配准过程分为自动、半自动和手动配准。
存在问题：如何提高图像的配准速度将是大范围遥感图像自动配准问题的要点；选取何种自动配准方案以保证图像的配准精度将是大范围遥感图像自动配准问题的另一要点。)
f2(x,yg[f1(h(x, y其中，h表示二维空间坐标变换。g表示灰度或辐射变换，描述因传感器类型的不同以及成像时气候等环境的影响所带来的图像灰度的变换。配准问题的实质就是要找到最优的空域变换h和灰度变换g，使得上述的等式成立，从而找到配准变换的参数
特征空间的选择通常要考虑以下几个因素：相似性；空间分布；唯一性。在自动图像配准中对特征的理解可以分为两类。(1)基于灰度的方法：基于灰度的方法将重点放在特征匹配上，在其过程中并没有真正提取特征。一般所说的模板匹配法就是这种方法的代表。这种方法实际上将图像的灰度分布直接作为特征而构成匹配的基础。(2)基于特征的方法：基于特征的方法需要在图像中提取显著的特征：区域(森林、湖泊、农田等)、线(区域的边界、道路等)和点(区域的角点、线的交点、曲线上的高曲率点等)。特征应该可以分布在图像任何地方并且可以被提取出来。
一般图像配准的过程主要涉及到图像的特征空间、相似性测度和搜索策略这三个方面。我们称这三个方面为图像配准的三要素，它们决定了图像配准的精度和速度。
按照配准过程中采用的特征类型，图像配准可分成两类：基于灰度的配准和基于特征的配准的方法。
基于图像灰度的配准方法是直接利用图像的灰度值来确定配准的空间变换，其中充分利用图像中所包含的信息，从而也称为基于图像整体内容的配准方法。这类方法的核心思想是认为参考图像和待配准图像上的对应点及其周围区域具有相同或者相似的灰度，并以灰度相似为基础采用相似度函数，然后寻找一组最优的几何变换参数使得相似度函数最大，从而实现图像的配准。在两幅图像灰度信息相似的情况下，常用的匹配方法有：互相关法(Cross-correlation)，序贯相似检测算法(Sequential Similarity Detection Algorithms, SSDA)以及最大互信息法。
虽然基于灰度的图像配准方法实现简单，但存在着如下缺点：(1)对图像的灰度变化比较敏感，尤其是非线性的光照变化，将大大降低算法的性能；(2)计算的复杂度高；(3)对目标的旋转，形变以及遮挡比较敏感。因此这种方法通常并不单独用在遥感图像配准中。
基于特征的图像配准方法可以克服利用图像灰度信息进行图像配准的缺点，主要体现在以下三个方面：(1)图像的特征点比图像的象素点要少很多，因此大大减少了配准过程的计算量；(2)特征点的匹配度量值对位置的变化比较敏感，可以大大提高配准的精确程度；(3)特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的适应能力。因此，其在图像配准领域得到了广泛应用。基于特征的图像配准方法有两个重要环节：特征提取和特征匹配。
待配准图像 图像预处理特征提取 特征集合 选择匹配基元 参考图像 搜索策略 选择匹配基元 特征提取特征集合配准结果重采样 模型参数求解 匹配结果 图2-13 基于特征的图像配准方法的基本步骤 基于特征点的配准方法的缺点：目前大多数的遥感图像配准系统都采用基于特征点的配准方法，以交互或自动的方式选择必要的控制点，但这些系统不能很好地适用于自动处理大量的数据，原因是特征点或控制点的选取是一项耗时、耗力的工作，在要求实时处理的应用中，这种方法是不现实的。同时自动配准要考虑是精度问题，因为在卫星遥感图像中自动地确定有效的、精确的控制点有时是困难的，太少的点、不准确的点或者分布不均匀的点被选取都可能导致配准的误差，而且这种情况是经常发生的。
基于特征的要求图像比较清晰，能选出特征点，线，区域即：基于特征点的局部自动配准的一个前提是，能够从图像中准确提取点特征。图像模糊，这必然使得点特征的提取比较困难，更加容易漏选特征点和产生伪特征点，从而导致配准精度不高。
1.基于小波变换的遥感图像自动配准算法
其基本思想是：在对大尺度遥感图像进行配准时，为了降低运算量，提高速度，利用小波变换的多分辨率特性，首先在低分辨率图像上获得一组配准参数，然后以此为初始值，再向高分辨率方向上逐层映射；算法在实现上，遵循一种由粗到精的搜索策略，即首先利用相似性度量获得图像间的一个粗略的变换参数估计，逐层迭代搜索，最终获得精确的配准参数。
基于图像灰度的全局配准，全局配准则是利用整幅图像直接对映射函数进行搜索。
基于小波变换的配准原理：图像配准过程中，如果对整幅图像进行搜索，计算量大、耗时长。为了减少搜索空间，可以利用小波变换构造多尺度图像金字塔，采取由粗到细的搜索策略，即只在最高层进行全搜索，逐层缩小搜索范围，大大提高搜索效率。图像经小波分解后分别得到低频和高频分量数据，低频子图像反映了原图像的平滑特征，高频系数分别反映了原图像水平、垂直和对角方法的亮度突变特征。该突变特征可用于图像配准的特征点(控制点)，而且小波分解后子图尺寸减小2l(l表示分解层数)倍。因此为了减小计算量，需要找到小波分解后的子图配准与原图配准之间的关系。
基于小波变换的配准方案：基于小波变换的全局配准方案，其基本思想是：首先采用小波变换将原始图像逐级分解得到一个分辨率从低到高、规模由小到大的层次式结构(也称金字塔结构)；然后在分辨率低的图像层，通过线性搜索或其他策略得到该分辨率下最优解的初步变换参数估计，并将此估计作为下一级图像层处理的搜索中心，使得变换参数估计在较高分辨率下逐级得到校正和精化，随着分辨率的提高，估计的精度随之提高，同时搜索的范围也逐级缩小，最终在最高分辨率的图层上得到满足精度要求的最优解。可见，在分辨率最低的图像层，即使采用线性搜索策略，由于其数据量与原始图像相比己经很小，计算量也会大大减小，而到了分辨率较高的图层，由于搜索的范围越来越小，那么虽然图像规模变大，计算量也得到了有效的控制。该方案的基本流程如下：
(1)对参考图像和待配准图像均采用小波变换进行逐级分解，得到不同分辨率和大小的两组金字塔图像；
(2)给定变换参数的搜索范围，在分辨率最低的图层上进行全搜索：依次取出搜索空间中的变换参数，对待配准图像对应的图层进行几何变换，采用基于灰度的配准方法(互相关法、最大互信息法等)，得到该分辨率下最优解的初步变换参数估计，并将此估计作为下一级图像层处理的搜索中心；
(3)以上一层的搜索结果为搜索中心，在高一级分辨率下搜索变换参数，由粗到精逐步细化变换参数。最终在原始配准图像上得到满足精度要求的配准参数
该配准方案的特点可以归纳如下：
算法不需要人工干预，适合于大数据量的遥感图像自动配准。 与基于点特征的自动配准方案相比，在缺乏先验知识的情况下，避免了点-点匹配的方法因缺乏充足和准确的控制点而导致较大的配准误差。 利用了多分辨率小波的优势，采用由粗到精的搜索策略，减少了搜索空间，加速了处理过程，提高了图像配准的速度。
2.高分辨率SAR影像同名点自动匹配技术 图像自动配准大致包括以下3大步骤:(1)在主、辅影像中提取特征点,通过实施同名点搜索来获取同名点;(2)利用同名点信息来解求主、辅影像之间的变换函数;(3)对辅影像进行几何变换,并通过重采样来获得纠正后的配准影像。
在这3大步骤中,之所以同名点对的确定是自动配准流程中的关键环节,首先,因为它的配准精度将直接决定变换函数的解求及解求精度;其次,因为同名点搜索计算复杂度通常情况下较复杂,其在整个影像配准流程中占有较高的机时量。鉴于此,研究一种高精度、高效率的同名点搜索技术将显得格外重要。本文提出的同名点自动匹配算法大致包括以下3大步骤:(1)创建金字塔影像,并通过在金字塔影像上进行回溯搜索来确定初始变换函数类型及相应 的变换参数;(2)通过分层回溯逐层加密控制点来解求最佳变换函数类型及相应变换参数;(3)在原始影像分辨率下修正同名点坐标,以获取最终匹配同名点对。
3.图像配准技术研究进展
将配准技术概括为8个方面,包括:配准对象、特征提取、特征匹配、变换模型、优化策略、坐标变换与插值、系统实现及算法评估,并考虑每项内容的技术特性进行细分,然后依据某一算法的创新点进行分类。
4.图像配准方法及其在目标跟踪中的应用
图像配准方法可以分为基于灰度的配准和基于特征的配准。基于特征的图像配准方法有两个重要环节:特征提取和特征匹配。可以选取的特征包括点、线与区域。基于特征的图像配准方法主要有两方面优点:a.图像的特征点比图像的像素点要少很多,大大减少了匹配过程的计算量;b.特征点的提取过程可以减少噪声的影响,对灰度变化、图像形变以及遮挡等都有较好的适应能力。
基于点特征的图像配准方法：特征点的提取——特征点匹配——误匹配点剔除——配准参数计算
5.图像配准技术研究
图像之间的配准一般可分为以下5个步骤：
(l)从基准图像和参考图像中提取共有的控制结构，这种控制结构可以是物体的点、边缘和边界等；
(2)对每幅图像中的控制结构(特征点)进行匹配;(3)选择几何变换模型，并利用匹配特征点对来估计变换参数;(4)对图像实行坐标变换和灰度插值;(5)对配准的效果进行评估。
所有图像配准方法都可以归纳为对三个元素选择问题，即特征空间、相似性准则和搜索策。特征空间从图像中提取用于配准的信息，搜策略从图像转换集中选择用于匹配的变换方，相似性准则决定配准的相对价值，然后基于一结果继续搜索，直到找到能使相似性度量有人满意的结果的图像变换方式。根据图像配准这三个基元素选择的区别，图像配准方法通常分为三类：
(l)基于象素的配准方法，即根据待配准图像的相关函数、Fourier变换和各阶矩量之间的关系式来计算配准参数。
(2)基于特征的配准方法，即根据需要配准图像重要相同特征之间的几何关系确定配准参数。这类方法首先需要提取特征，如图像的边缘、角、点、线、曲率等具有不变性的特征。提取特征可在空间域内进行，也可在变换域内进行。在空间域内常使用的特征包括边缘、区域线的端点、线交叉点、区域中心、曲率不连续点等。其中边缘和区域边界最常用，可以由边缘检测方法和区域分割方法得到;基于特征的配准方法是图像配准中最常见的方法，对于不同特性的图像，选择图像中容易提取，并能够在一定程度上代表待配准图像相似性的特征作为配准依据。基于特征的配准方法在图像配准方法中具有最强的适应性。
(3)基于模型的配准方法，这种方法是根据图像失真的数学模型来进行非线性校正式的配准。
前两种方法是全局图像配准技术，需要假设图像中的对象仅是刚性地改变位置、姿态和刻度，改变的原因往往是由受试者运动引起的。第三类方法只适合图像中对象之间局部的非线性的、非刚性的变形校正，这种失真通常由于成像系统空间编码的非线性引起的。所以，它需要根据成像系统的非线性失真模型来实现配准。前两类方法多用于图像的初步配准，且能够解析求解，后一类方法多用于图像的精细配准，通常利用非线性规划的方法数值求解。
3.26：
图像的配准和融合方法较多,主要分为三类:基于像素的配准方法,基于特征的配准方法和基于模型的配准方法。基于像素的配准方法多用于图像的初步配准,计算量小;基于特征的配准方法定位准确,计算量较大且要首先进行特征提取;基于模型的配准方法多用于图像的精细配准,但只适合图像中的对象之间的局部的非线性的非刚性的变形的校正。对于像素相关性大的图像,可利用图像间相同位置的特征点进行配准;对于像素相似性小的图像,需要先对图像进行特征提取,通过提取的特征点进行配准。
基于特征点的图像配准技术主要有两类方法: a)比较两幅图像的特征点及其周围像素的灰度、曲率等情况来计算特征点之间的相似程度,建立特征点之间的一一对应关系[1, 2]。由于仅考虑单个特征点之间的相似程度,常存在特征点误匹配的情况。b)改进的方法是建立特征点集之间的变换关系,主要使用Hausdorff距离来匹配两个特征点集[3, 4]。这类方法可以容忍点与点之间匹配的不准确,但是要求预先确定图像之间变换模型的参数搜索范围,而且在图像差异较大时计算量很大。
配准方法可分为以下几种:(l)基于控制点的匹配方式。控制结构为图像中的显著点(称为控制点)，控制点可以是用户提供的，也可以由算法估计，然后对控制点进行匹配，估计几何变换参数并进行配准。(2)基于矩(monent一based)的配准方式口控制结构是复杂的图像矩，每幅图像被标准化，即与一个矩被归一化的参数位置进行匹配。(3)基于边缘的配准方式。控制结构是图像的边缘.通过比较边缘像素的密度或在符号层次上比较边缘来实施边缘匹配。几何变换参数直接导出并对其中一幅图像实施相应的变换.(4)基于相似性判据最优化的方式。选择一个几何变化并以各种参数值施于一幅图像上。对于每一个值，评价由相似性判据提取的控制结构。该值表明了控制结构匹配的程度，因此可以从判据的最优值实现配准。图像配准主要包括以下四个步骤:(l)从待配准的每幅图像中提取控制结构;(2)在每幅图像中对控制结构进行匹配;(3)从前两步中选择几何变换并对其参数 进行估计;根据图像配准的这三个基元素选择的区别，图像配准的方法通常可分为三类:(l)基于象素的配准方法，即根据待配准图像的相关函数、Fourier变换和各阶矩量之间的关系式来计算配准参数。(2)基于特征的配准方法，即根据需要配准图像重要相同特征之间的几何关系确定配准参数。这类方法首先需要提取特征，如图像的边缘、角、点、线、曲率等具有不变性的特征。提取特征可在空间域内进行，也可在变换域内进行。在空间域内常使用的特征包括边缘、区域线的端点、线交叉点、区域中心、曲率不连续点等。其中边缘和区域边界最常用，可以由边缘检测方法和区域分割方法得到;基于特征的配准方法是图像配准中最常见的方法，对于不同特性的图像，选择图像中容易提取，并能够在一定程度上代表待配准图像相似性的特征作为配准依据。基于特征的配准方法在图像配准方法中具有最强的适应性。(3)基于模型的配准方法，这种方法是根据图像失真的数学模型来进行非线性校正式的配准。前两种方法是全局图像配准技术，需要假设图像中的对象仅是刚性地改变位置、姿态和刻度，改变的原因往往是由受试者运动引起的。第三类方法只适合图像中对象之间局部的非线性的、非刚性的变形校正，这种失真通常由于成像系统空间编码的非线性引起的。所以，它需要根据成像系统的非线性失真模型来实现配准。前两类方法多用于图像的初步配准，且能够解析求解，后一类方法多用于图像的精细配准，通常利用非线性规划的方法数值求解。
第二篇：图像放大算法总结及MATLAB源程序
1，插值算法（3种）：
（1）最邻近插值（近邻取样法）：
最邻近插值的的思想很简单，就是把这个非整数坐标作一个四舍五入，取最近的整数点坐标处的点的颜色。可见，最邻近插值简单且直观，速度也最快，但得到的图像质量不高。
最邻近插值法的MATLAB源代码为：
A = imread('F:lena.jpg');%读取图像信息 imshow(A);%显示原图 title('原图128*128');
Row = size(A,1);Col = size(A,2);%图像行数和列数 nn=8;%放大倍数
m = round(nn*Row);%求出变换后的坐标的最大值 n = round(nn*Col);
B = zeros(m,n,3);%定义变换后的图像
for i = 1 : m
for j = 1 : n
x = round(i/nn);y = round(j/nn);%最小临近法对图像进行插值
if x==0 x = 1;end
if y==0 y = 1;end
if x>Row x = Row;end
if y>Col y = Col;end B(i,j,:)= A(x,y,:);
end end
B = uint8(B);%将矩阵转换成8位无符号整数 figure;imshow(B);
title('最邻近插值法放大8倍1024*1024');
运行程序后，原图如图1所示：
图1
用最邻近插值法放大4倍后的图如图2所示：
图2
（2）双线性内插值法：
在双线性内插值法中，对于一个目的像素，设置坐标通过反向变换得到的浮点坐标为(i+u,j+v)，其中i、j均为非负整数，u、v为[0,1)区间的浮点数，则这个像素得值 f(i+u,j+v)可由原图像中坐标为(i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所对应的周围四个像素的值决定，即：
f(i+u,j+v)=(1-u)(1-v)f(i,j)+(1-u)vf(i,j+1)+ u(1-v)f(i+1,j)+ uvf(i+1,j+1)其中f(i,j)表示源图像(i,j)处的的像素值，以此类推。
这就是双线性内插值法。双线性内插值法计算量大，但缩放后图像质量高，不会出现像素值不连续的的情况。由于双线性插值具有低通滤波器的性质，使高频分量受损，所以可能会使图像轮廓在一定程度上变得模糊。
在MATLAB中，可用其自带的函数imresize()来实现双线性内插值算法。
双线性内插值算法的MATLAB源代码为：
A=imread('F:lena.jpg');imshow(A);
title('原图128*128');
C=imresize(A,8,'bilinear');%双线性插值 figure;imshow(C);
title('双线性内插值法放大8倍1024*1024');
程序运行后，原图如图3所示：
图3
双线性内插值法放大8倍后的图如图4所示：
图4
（3）双三次插值法：
双三次插值法能够在很大程度上克服以上两种算法的不足，该算法计算精度高，但计算量大，它考虑一个浮点坐标(i+u,j+v)周围的16个邻点。
目的像素值f(i+u,j+v)可由如下插值公式得到：f(i+u,j+v)= [A] * [B] * [C] 其中[A]=[ S(u + 1)S(u + 0)S(u2)];[C]=[ S(v + 1)S(v + 0)S(v2)];而[B]是周围16个邻点组成的4*4的矩阵；S(x)是对 Sin(x*π)/x 的逼近。
在MATLAB中，可用其自带的函数imresize()来实现双三次插值算法。MATLAB源代码为：
A=imread('F:lena.jpg');%读取原图像
D=imresize(A,8,'bicubic');%双三次插值放大8倍 figure;
T
imshow(D);title('三次卷积法放大8倍1024*1024');
MATLAB自带双三次插值法运行结果如图5所示：
图5
也可以自己编写双三次插值算法MATLAB代码如下：
clc,clear;
ff=imread('F:lena.jpg');%读取图像到ff
k=8;%设置放大倍数 [m,n,color]=size(ff);
f=zeros(m,n);%将彩色图像ff转换为黑白图像f for i=1:m
for j=1:n
f(i,j)=ff(i,j);
end end
a=f(1,:);c=f(m,:);%将待插值图像矩阵前后各扩展两行两列,共扩展四行四列 b=[f(1,1),f(1,1),f(:,1)',f(m,1),f(m,1)];d=[f(1,n),f(1,n),f(:,n)',f(m,n),f(m,n)];a1=[a;a;f;c;c];a1';
b1=[b;b;a1';d;d];f=b1';f1=double(f);
for i=1:k*m %利用双三次插值公式对新图象所有像素赋值 u=rem(i,k)/k;i1=floor(i/k)+2;A=[sw(1+u)sw(u)sw(1-u)sw(2-u)];
for j=1:k*n
v=rem(j,k)/k;j1=floor(j/k)+2;C=[sw(1+v);sw(v);sw(1-v);sw(2-v)];
B=[f1(i1-1,j1-1)f1(i1-1,j1)f1(i1-1,j1+1)f1(i1-1,j1+2)f1(i1,j1-1)f1(i1,j1)f1(i1,j1+1)f1(i1,j1+2)f1(i1,j1-1)f1(i1+1,j1)f1(i1+1,j1+1)f1(i1+1,j1+2)f1(i1+2,j1-1)f1(i1+2,j1)f1(i1+2,j1+1)f1(i1+2,j1+2)];g1(i,j)=(A*B*C);
end end
g=uint8(g1);%将矩阵转换成8位无符号整数 imshow(g);
title('自编双三次插值法放大8倍图像');
其中子函数sw代码如下： function A=sw(w1)w=abs(w1);if w<1&&w>=0 A=1-2*w^2+w^3;elseif w>=1&&w<2 A=4-8*w+5*w^2-w^3;else
A=0;end
与MATLAB自带函数相比，以上手工编写的MATLAB代码只能完成黑白图像输出，且运行时间远比MATLAB自带函数的运行时间长。手工编写双三次插值算法MATLAB代码的运行结果如图6所示：
图6
2，其他算法简介：
传统的图像放大方法有重复放大线性放大和高次多项式插值放大。重复放大最简单,但会产生明显的方块效应线性放大消除了方块效应,但会造成图像的模糊 高次多项式插值放大效果较好,但运算复杂。由于传统方法的固有缺陷,诞生了新一代图像放大方法,主要有小波放大、邻域交换内插和分形放大等。
下面简单介绍一下增强系数小波放大算法： 算法示意图如图7所示：
图7 通过二维离散小波变换,经分析高通滤波器和分析低通滤波器,可将一幅分辨率为p的二维图像分解为分辨率为p/2的离散逼近信号A1和水平、垂直、对角三个细节信号H1、V1、D1。这四个分量都只有原图像大小的1/4。之后又可以对A1进行同样的分解如图7所示。这个过程可以一直重复下去。通过二维离散小波反变换,用相应的综合高通滤波器和综合低通滤波器可将各分量重构为原图像。
对于一个图像，低频成分包含了基本特征，即原图像的近似，高频成分反应其细节。基于此，我们将原图像作为低频成分A1，其他3个细节部分置0，进行小波重构，便可得到放大4倍的图像。但是由于能量守恒,放大后的图像能量分散会显得较暗。可以将原图像灰度值矩阵乘2，再进行上述变换，便可解决这一问题。小波分解重构是一种全局运算，不会造成重复放大中的方块效应，同时较好地保持图像边缘的清晰。
第三篇：算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。
这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。
首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。
③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。
第四篇：算法总结
算法分块总结
为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。
图论模型的应用
分层图思想的应用：
用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。
这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：
最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：
容量有上下界的最大流的应用：
欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：
求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：
抽象成数学模型就是：
设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k 首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。 假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树； 2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。 加边和去边过程，利用动态规划优化特别值得注意。 次小生成树： 加边和去边很值得注意。 每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法： 首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。 最短路径的应用： Dijkstra 算法应用： Folyed 算法应用： Bellman-Ford 算法的应用： 差分约束系统的应用： 搜索算法 搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用： IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索： 可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。 动态规划 动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。 状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP： 状态划分比较困难的题目： 树形DP： 四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2) 高档数据结构的应用 并查集的应用： 巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用： 总结用线段树解题的方法 根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等 树的每个节点根据题目所需，设置变量记录要求的值 用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。 在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。 Trie的应用：； Trie图的应用探索： 后缀数组的应用研究： 在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。 树状数组的应用探索：； 计算几何 掌握基本算法的实现。凸包的应用：； 半平面交算法的应用：； 几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：； 转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：； 经典算法：找平面上的最近点对。 贪心 矩形切割 二分思想应用 活用经典算法 利用归并排序算法思想求数列的逆序对数： 利用快速排序算法思想，查询N个数中的第K小数： 博弈问题 博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。 第一类：推结论。典型题目： 第二类：递推。典型题目： 比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质： 1． 所有的结束位置都是P位置。 2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。 这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。 与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为： 1． 将所有的结束位置标为P位置。 2． 将所有能一步到达P位置的点标为N位置。 3． 找出所有只能到达N位置的点，将它们标为P位置。 4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。 关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为 g(x)min{n0,ng(y)对于所有yF(x)} 1． 对于所有的结束位置x，g(x)= 0。 2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。 3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四类：极大极小法。 典型题目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩阵妙用 矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目： 数学模型举例 向量思想的应用： UVA 10089：注意降维和向量的规范化 ； 利用复数思想进行向量旋转。 UVA 10253： 递推 数代集合 数代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。 组合数学 Polya定理则是解决同构染色计数问题的有力工具。 补集转化思想 ZOJ 单色三角形： 字符串相关 扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀； 填充问题 高精度运算 三维空间问题专题 无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。 其它问题的心得 解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广 源程序代码： } 一、自然数拆分（递归） } #include 二、快速排序（递归）int a[100];void spilt(int t)#include spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i; int value=a[from];printf(“please enter the number:”); while(from a[from]=a[to]; while(from ++from; a[to]=a[from]; } a[from]=value; return from; } void qsort(int a[],int from,int to){ int pivottag;if(from {pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to); } scanf(“%d”,&n); for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2); 三、删数字（贪心） #include int a[11]={3,0,0,0,9,8,1,4,7,5,1}; int k=0,i=0,j; int m; while(i<11) { printf(“%d ”,a[i]); i++;} printf(“n please input delete number:”); 四、全排列（递归）#include int i;char temp;if(k==n) for(i=0;i<=3;i++) {printf(“%c ”,a[i]);} else { for(i=k;i<=n;i++) { temp=a[i]; a[i]=a[k]; a[k]=temp; A(a,k+1,n); } } } main(){ int n; char a[4]={'a','b','c','d'},temp; A(a,0,3); getch(); return 0;} 五、多段图（动态规划）#include “stdio.h” #define n 12 //图的顶点数 { while(from scanf(“%d”,&m);for(k=0;k { for(i=0;i<=11-k;i++) { if(a[i]>a[i+1]) { for(j=i;j<10;j++) {a[j]=a[j+1];} break;//满足条件就跳转 } } } int quicksort(int a[],int n){ qsort(a,0,n);} } printf(“the change numbers:”); for(i=0;i<11-m;i++) { if(a[i]!=0) { printf(“%d ”,a[i]);} } } #define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组 int path[k];//存储最短路径的数组 void creatgraph()//创建图的(成本)邻接矩阵 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 } void printgraph()//输出图的成本矩阵 { int i,j; printf(“成本矩阵:n”); for(i=0;i { for(j=0;j printf(“%d ”,cost[i][j]); printf(“n”); } } //使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++) if(cost[i][j]>0 &&(cost[i][j])+v[j] {length=cost[i][j]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0;//起点 path[k-1]=n-1;//最后的目标 for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//将最短路径存入数组中 } //使用向后递推算法求多段图的最短路径 void BackPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i for(i=1;i<=n-1;i++) { for(length=MAX,j=i-1;j>=0;j--) if(cost[j][i]>0 &&(cost[j][i])+v[j] {length=cost[j][i]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0; path[k-1]=n-1; for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];} //输出最短路径序列 void printpath(){ int i; for(i=0;i printf(“%d ”,path[i]);} main(){ freopen(“E:1input.txt”,“r”,stdin); creatgraph(); printgraph(); FrontPath(); printf(“输出使用向前递推算法所得的最短路径:n”); printpath(); printf(“n输出使用向后递推算法所得的最短路径:n”); BackPath(); printpath();printf(“n”);} 六、背包问题（递归）int knap(int m, int n){ int x; x=m-mn; if x>0 sign=1; else if x==0 sign=0; else sign=-1; switch(sign){ case 0: knap=1;break; case 1: if(n>1) if knap(m-mn,n-1) knap=1; else knap= knap(m,n-1); else knap=0; case-1: if(n>1) knap= knap(m,n-1); else knap=0; } } 七、8皇后（回溯）#include int i; i=1; while(i if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k))) return 0; i++; } return 1;} void Nqueens(int X[N+1]){ int k, i; X[1]=0;k=1; while(k>0){ X[k]=X[k]+1; while((X[k]<=N)&&(!place(k,X))) X[k]=X[k]+1; if(X[k]<=N) if(k==N){ for(i=1;i<=N;i++) printf(“%3d”,X[i]);printf(“n”); } else{ k=k+1; X[k]=0; } else k=k-1; } } void main(){ int n, i; int X[N+1]={0}; clrscr(); Nqueens(X); printf(“The end!”);} 八、图着色（回溯）#include int j,t; while(1){ nextValue(k); if(X[k]==0) return 0; if(k==(N-1)){ for(t=0;t printf(“%3d”,X[t]); printf(“n”); count++; } else mcoloring(k+1); } } int nextValue(int k){ int j; while(1){ X[k]=(X[k]+1)%(M+1); if(X[k]==0) return 0; for(j=0;j if((GRAPH[k][j]==1)&&(X[k]==X[j])) break; } if(j==N){ return 0; } } } void main(){ int k; clrscr(); k=0; mcoloring(k); printf(“ncount=%dn”,count);} 矩阵链乘法（动态规划） 符号S[i, j]的意义： 符号S(i, j)表示，使得下列公式右边取最小值的那个k值 public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s) { int n=p.length-1; for(int i = 1;i <= n;i++)m[i][i] = 0; for(int r = 2;r <= n;r++) for(int i = 1;i <= n-r+1;i++){ int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for(int k = i+1;k < j;k++){ int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t < m[i][j]){ m[i][j] = t; s[i][j] = k;} } } } O的定义： 如果存在两个正常数c和n0，对于所有的n≥n0时，有： |f(n)|≤c|g(n)|，称函数f(n)当n充分大时的阶比g(n)低，记为 f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义： 如果存在正常数c和n0，对于所有n≥n0时，有： |f(n)|≥c|g(n)|，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，即f(n)的阶不低于g(n)的阶。记为： f(n)=Ω(g(n))。Θ的定义： 如果存在正常数c1，c2和n0，对于所有的n>n0，有： c1|g(n)|≤f(n)≤c2|g(n)|，则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法： O(1) (2)指数时间算法： O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 贪心方法基本思想： 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 多段图： COST[j]=c(j,r)+COST[r]; 回溯法： (假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。约束条件： (1)显式约束：限定每一个xi只能从给定的集合Si上取值。 (2)解 空 间：对于问题的一个实例，解向量满足显式 约束条件的所有多元组，构成了该实例 的一个解空间。 (3)隐式约束：规定解空间中实际上满足规范函数的元 组，描述了xi必须彼此相关的情况。基本做法： 在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 8皇后问题 约束条件 限界函数： 子集和数问题： 约束条件 限界函数： 回溯法－－术语： 活结点：已生成一个结点而它的所有儿子结点还没有 全部生成的结点称为活结点。 E-结点：当前正在生成其儿子结点的活结点叫E-结点。 死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。 使用限界函数的深度优先节点生成的方法成为回溯法；E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法 且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别： 分支限界法本质上就是含有剪枝的回溯法，根据递归的条件不同，是有不同的时间复杂度的。 回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解 一般如果只考虑时间复杂度二者都是指数级别的 可是因为分支限界法存在着各种剪枝，用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){ int j; X[k]=1; if(s+W[k]==M){ for(j=1;j<=k;j++) printf(“%d ”,X[j]); printf(“n”); } else if((s+W[k]+W[k+1])<=M){ sumofsub(s+W[k],k+1,r-W[k]); } if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){ X[k]=0; sumofsub(s,k+1,r-W[k]); } } void main(){ M=30; W[1]=15; W[2]=9; W[3]=8; W[4]=7; W[5]=6; W[6]=5; W[7]=4; W[8]=3; W[9]=2; W[10]=1; sumofsub(0,1,60);} P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L，则此问题L是NP-难度的。如果L是NP难度的且L NP，则此问题是NP-完全的第五篇：算法总结材料
点击咨询 