小波分析算法资料整理总结

第一篇：小波分析算法资料整理总结

一、小波分析基本原理：

信号分析是为了获得时间和频率之间的相互关系。傅立叶变换提供了有关频率域的信息，但有关时间的局部化信息却基本丢失。与傅立叶变换不同，小波变换是通过缩放母小波（Mother wavelet）的宽度来获得信号的频率特征，通过平移母小波来获得信号的时间信息。对母小波的缩放和平移操作是为了计算小波系数，这些小波系数反映了小波和局部信号之间的相关程度。相关原理详见附件资料和系统设计书。

注：小波分析相关数学原理较多，也较复杂，很多中文的著作都在讨论抽象让非数学相关专业人难理解的数学。本人找到了相对好理解些的两个外文的资料： Tutorial on Continuous Wavelet Analysis of Experimental Data.doc Ten.Lectures.of.Wavelets.pdf

二、搜索到的小波分析源码简介（仅谈大体印象，还待继续研读）：

１、83421119WaveletVCppRes.rar 源码类型：VC++程序

功能是：对简单的一维信号在加上了高斯白噪声之后进行Daubechies小波、Morlet小波和Haar小波变换，从而得到小波分解系数；再通过改变分解得到的各层高频系数进行信号的小波重构达到消噪的目的。

说明：在这一程序实现的过程中能直观地理解信号小波分解重构的过程和在信号消噪中的重要作用，以及在对各层高频系数进行权重处理时系数的选取对信号消噪效果的影响。但这是为专业应用写的算法，通用性差。

２、WA.FOR（南京气象学院常用气象程序中的小波分析程序）

源码类型：fortran程序

功能是：对简单的一维时间序列进行小波分析。

说明：用的是墨西哥帽小波。程序短小，但代码写得较乱，思路不清，还弄不明白具体应用。

３、中科院大气物理学所.zip（原作者是美国Climate Diagnostics Center的C.Torrence 等）

源码类型：fortran和matlab程序各一份

功能是：气象应用。用小波分析方法对太平洋温度的南方涛动指数进行分析。

说明：用的是Morlet和墨西哥帽小波。程序编写规范，思路清晰，但这是为专业应用写的算法，通用性差。

４、Morlet小波变换源程序.rar 源码类型：matlab程序

功能是：对简单的一维时间序列进行小波分析。

说明：用的是墨西哥帽小波。程序短小，但代码写得较乱，思路不清，还弄不明白具体应用。

５、Morlet小波计算函数封装源程序.rar 源码类型：matlab程序

功能是：对一维时间序列信号进行连续小波变换程序。

说明：用的是Morlet小波。程序短小，代码调用了matlab内置函数wave，并使用了卷积进行求解，源码中的多个参数的选择和设置原理和依据还弄不明白。６、计算关于时间序列数据的的小波变换fortran程序.rar 源码类型：fortran程序

功能是：对简单的一维时间序列进行小波变换。

说明：用的是DOG小波、Morlet小波、Paul小波。程序较长，代码写得较乱，还弄不明白具体应用。

三、小波分析底层基本算法实现的困难：

１、小波分析中用的小波基函数的种类很多，选择不同基小波函数的，变换内核的计算实现方法不同。

２、小波分析的应用领域非常多，不同的应用领域的小波算法框架不同。

３、小波分析的输入输出参数较多，但在应用时灵活度不强，对不同小波基函数和不同的应用有着不同的参数选择和设定方法，同时表现出不同的性质。

因而，很多时候小波在不同的实际应用时的算法和编码实现有差别非常大。从目前本人收集到的５个小波分析源程序的分析来看，这６个源程序的具体实现思路、参数选择和设置各不相同。总之，很难设定一个比较标准通用的小波分析底层算法。

第二篇：小波变换快速算法及应用小结

离散小波变换的快速算法

Mallat算法[经典算法] 在小波理论中,多分辨率分析是一个重要的组成部分。多分辨率分析是一种对信号的空间分解方法,分解的最终目的是力求构造一个在频率上高度逼近L2(R)空间的正交小波基,这些频率分辨率不同的正交小波基相当于带宽各异的带通滤波器。因此,对于一个能量有限信号,可以通过多分辨率分析的方法把其中的逼近信号和细节信号分离开,然后再根据需要逐一研究。多分辨率分析的概念是S.Mallat在构造正交小波基的时候提出的,并同时给出了著名的Mallat算法。Mallat算法在小波分析中的地位相当于快速傅立叶变换在经典傅立叶变换中的地位,为小波分析的应用和发展起到了极大的推动作用。MALLAT算法的原理

在对信号进行分解时，该算法采用二分树结构对原始输入信号x(n)进行滤波和二抽取，得到

111第一级的离散平滑逼近和离散细节逼近和，再采用同样的结构对进行滤波和二抽取

22得到第二级的离散平滑逼近和离散细节逼近和，再依次进行下去从而得到各级的离散123细节逼近对，…，即各级的小波系数。重构信号时，只要将分解算法中的步骤反过来进行即可，但要注意，此时的滤波器与分解算法中的滤波器不一定是同一滤波器，并且要将二抽取装置换成二插入装置才行。

多孔算法

[小波变换快速算法及其硬件实现的研究毛建华]

多孔算法是由M.shen于1992年提出的一种利用Mallat算法结构计算小波变换的快速算法，因在低通滤波器h0()和高通滤波器h1()中插入适当数目的零点而得名。它适用于a=2的二分树结构，与Mallat算法的电路实现结构相似。先将Mallat算法的电路实现的基本支路作一下变形。令h0 和h1()的z变换为H0（z）与H1（z），下两条支路完全等价，只不过是将插值和二抽取的顺序调换一下罢了。图中其它的上下两条支路也为等效支路，可仿照上面的方法证明。这样，我们便可由Mallat算法的二分树电路结构得出多孔算法的电路级联图，原Mallat算法中的电路支路由相应的等效支路所取代，所以整个电路形式与Mallat算法非常相似。如果舍去最后的抽取环节们实际上相当于把所有点的小波变换全部计算出来。

基干FFT的小波快速算法

[小波变换快速算法及其硬件实现的研究毛建华]

Mallat算法是由法国科学家StephaneG.Mallat提出的计算小波分解与重构的快速算法，能大大降低小波分解与重构的计算量，因此在数字信号处理和数字通信领域中得到了广泛的应用。但是如果直接采用该算法计算信号的分解和重构，其运算量还是比较大。主要体现在信号长度较大时，与小波滤波器组作卷积和相关的乘加法的计算量很大，不利于信号的实时处理。故有必要对该算法作进一步的改进。众所周知，FFT是计算离散傅里叶变换(DFT)的一种快速算法，如能将它和Mallat算法结合在一起，势必会进一步降低小波分解和重构的计算量，事实证明这一想法是可行的。

基于FFT的小波变换快速算法是通过离散傅里叶变换建立起FFT和mallat算法之何的桥梁，从而将、FFT引入到小波变换中来，达到改小波变换快速算法及硬件实现的研究进Mallat算法的目的。

当信号长度较小时，FFT算法效率不及直接算法;随着长度的增加，特别是对于长度是2的幕次方的信号，FFT算法比直接算法更适用，能大大降低计算t。当信号是长序列信号时，小波分解与重构中，滤波器要补很多的零，这对信号的实时计算很不利，我们可以采用长序列快速相关卷积算法对信号进行分段后再运用FFT算法，提高运算速度。

基于算术傅里叶变换的小波变换快速算法

[小波变换快速算法及其硬件实现的研究毛建华]

算术傅里叶变换(AFT)是1988年由Tufts和Sadasiv提出的一种用Mobius反演公式计算连续函数傅里叶系数的方法.它具有乘法运算t仅为O(N)算法简单、并行性好的优点。根据DPT和连续函数傅里叶系数的关系，可以用AFT计算DFT。同直接算法相比，APT方法可以将DFT的计算时间减少90%，尤其是对于含有较大素因子，特别是其长度本身为素数的DFT，它的速度比传统的FFT更快.另一方面，Mallat算法的分解和重构算法也可由DFT来计算，从而将AFT与Mallat算法联系了起来，从而为小波变换快速算法开辟了新的途径。对于尺度

为j的快速分解算法步骤如下: 1)选定滤波器系数h(n)和g(n)，再根据FFT的性质2，用N点的AFT分别计算出H(k)和G(k)，分别取共扼，进而得到H*(k)，G*(k)。

2)在已知cj(n)的情况下，用N点的AFT求出其DFTCj(k)3)分别计算出H*(k)Cj(k)，G*(k)Cj(k)，即C’j(k)和D’j(k)4)用N点的AFT求出C’j+1(k)和D’j+1(k)IDFT，得到C’j+1(n)和D’j+1(n)IDFT，再分别对它 们作二抽取，就可求出Cj+1(n)和Dj+1(n)。在进行分解计算时，H(k)G(k)只要计算一次即可。重复步骤(2)一(4)可实现下一尺度小波分解，直到达到规定的尺度为止。不过要注意:尺度增加一个级别，信号长度减半。对于尺度为j+1的快速重构算法为: 1)对Cj+1(n)和Dj+1(n)进行二插值，得到C’j+1(n)和D’j+1(n);2)用N点的AFT分别求出h(n)、g(n)的DFTH(k)和G(k)3)用N点的AFT分别求出C’j+1(n)和D’j+1(n)的DFTC’j+1(k)和D’j+1(k);4)根据(17)式求出Cj(k)，再用N点的AFT进行IDFT，可求出cj(n)。

基于Hermite插值的小波变换模极大值重构信号快速算法

[基于Hermite插值的小波变换模极大值重构信号快速算法韩民，田岚，翟广涛，崔国辉] 信号在不同尺度上的小波变换模极大值包含了信号中的重要信息，因此研究如何由小波变 换模极大值重构信号是很有意义的。论文提出了一种基于Hermite插值多项式由二进小波变换模极大值重构信号的快速算法。数值试验表明，与S.Mallat提出的经典交替投影算法相比，该算法可以在保证重构质量的前提下简化计算过程，提高计算效率，计算所需时间与交替投影算法相比大大减少，是一种实用性较强的信号重构算法。

Hermite插值[11]方法是一种具有重节点的多项式插值方法，由于它要求在节点处满足相应的导数条件，因此也称为切触差值。由于小波系数模极大值点的导数为零，这与Hermite插值对节点的导数要求不谋而合，因此我们选用Hermite插值多项式作为改进的插值方法。

强奇异积分方程小波Petrov-Galerkin快速算法

[强奇异积分方程小波Petrov-Galerkin快速算法隆广庆]

通过构造具有高阶消失矩、小支集和半双正交性质的分片多尺度小波基底, 给出第2类强奇异积分方程的小波Petrov-Galerkin快速算法, 并证明该算法收敛阶达到最佳, 条件数有界, 计算复杂性几乎最佳。构造配置泛函的思想, 构造分片多项式空间Xn上2列具有半双正交性的小波基,其中一列具有高阶消失矩性质。

小波变换的应用

小波分析在图像压缩编码中的应用

[小波变换算法在数字图像处理中的应用支春强中国电子科技集团公司第二十八研究所，江苏南京 210007摘] 数字图像信号像素间一般都具有相关性，相邻之间、相邻列之间的相关性最强，其相关系数呈指规律衰减。图像中相关性的存在，是图像压缩的理论依据，使得能针对性地采用某种相关的手段去除冗余信息，达到压缩的目的。利用变换编码可以有效地消除像素间的相关性，从而获得较好的压缩效果。其基本原理就是将在时域描述的信号（如声音信号）或在空域描述的信号（如图像信号）经变换到正交向量空间（即变换域）中进行描述，在变换域的描述中各信号分量之间的相关性很小或互不相关，即能量得以集中。

小波变换进行图像重构实质上是相当于分别对图像数据的行和列做一维小波逆变换。对通过水平跟垂直滤波，离散小波将一级变换后图像的4个子图进行合成。对多级变换后的图像，则先对其信息集中的图进行重构，然后逐层进行。

小波分析在图像处理边缘检测中的应用

小波变换在车牌定位中的应用张国才，王召巴（中北大学信息与通信工程学院，山西太原030051）

由于传统的边缘检测方法检测到的边缘信息复杂，要想从中找准车牌的位置十分困难，而小波可以在不同的分辨率层次上对图像进行分割，在低分辨率层次上进行粗分割，由于计算量较小，适用于寻找目标的大致轮廓，在较高分辨率上实现精细分割，而且粗分割的结果对精细分割具有一定的指导作用，可以减少计算量和提高目标的定位精度。所以有的学者将小波变换用在了车牌区域的定位方面，利用小波的特点对车牌图像进行分析，发现小波分解后的细节分量中有能较好体现出车牌位置的信息，特别是水平低频、垂直高频分量能提供更准确的车牌位置信息。利用小波变换对车牌定位，在小波变换的分解图像中这里只研究其低频子图像，对低频子图像利用最大类间方差法进行二值化分割。

在军事工程方面的应用

[小波变换及其在轨道检测中的应用俞峰 戴月辉 ] 目前小波分析应用于轨道检测主要有: ①用小波时域局部特征检测突变信号(如检测钢

轨焊接部位缺陷、钢轨表面磨损等);②当传统的功率谱无法区分信号谱特征时,采用小波分 层细化分解,提取信号谱特征。

在语音合成方面的应用

[语音处理中自适应小波变换的应用 Application of Adaptive Wavelet Transformations in Speech Processing徐静波,冉崇森XU Jing2bo , RAN Chong2sen(信息工程大学信息工程学院,河南郑州450002)] 对于含噪声语音信号,我们先分离小波变换中语音信号引起的模极大值点和噪声引起的模极 大值点,再根据语音信号引起的模极大值点来检测端点。一般地,原始信号的Lipschitz指数是正的,而白噪声的Lipschitz指数是负的。当尺度减少时,如果某些小波变换模极大值点的幅值急剧增加,则表明对应的奇异性具有负的Lipschitz指数,这些极大值点几乎被噪声控制。因为由噪声引起的模极大值点的平均密度与尺度成反比,所以,随着尺度的递增,至少有一半的模极大值点不能传递到较大尺度上。因此,那些不能从一个尺度上传递到较大尺度上的模极大值点,也是由噪声控制的。我们把噪声控制的模极大值点去掉,剩下的模极大值点就是由语音信号控制的。

在其他方面的应用

（1）小波分析在数字水印中的应用

使用小波域水印方法的优点与在JPEG 中使用小波是类似的，并且小波的多分辨率分析与人眼视觉特性是一致的，这对根据HVS 选择适当的水印嵌入位置和嵌入强度有很大的帮助。（2）小波分析在图像滤波中的应用

在小波变换域，可通过对小波系数进行切削、缩小幅度等非线性处理，以达到滤除噪声的目的。

（3）小波分析在地球物理勘探中的应用

提高物理勘探资料的信噪比和分辨率一直是物理勘探资料处理所追求的目标。在资料处理中所遇到的噪音主要有规则干扰和随机干扰两大类，利用小波变换时频两域都有局部化的特点，对信号进行多尺度分解同样可以抑制噪音。（4）医学检测方面的应用

小波能有效提取生理信号中的突变特征点，这在医学方面（如B超、CT、磁共振、心电图等）已有成熟的应用。在胃动力检测方面，利用小波包变换方法能很清除地分辨出人体胃运动的三相特征，这些在临床上都有重要的应用价值。

第三篇：小波分析小结

小波分析的形成

小波分析是一门数学分支，是继Fourier变换之后新的时频域分析工具。小波理论的形成经历了三个发展阶段：

Fourier变换阶段：

Fourier变换是将信号在整个时间轴上进行积分，它将信号的时域特征和频域特征联系起来，分别进行分析。设信号f(t)，其Fourier变换为：

F()f(t)eitdt

F()确定了f(t)在整个时间域上的频谱特性。但Fourier变换不能对信号从时域和频域结合起来分析，它是一种全局变换，在时间域上没有任何分辨率。

例：f(t)1,(2t2)，其Fourier变换对应图如下：

短时Fourier变换阶段：

短时Fourier变换即加窗Fourier变换，其思想是把信号分成许多小的时间间隔，用Fourier分析每个时间间隔，以确定该间隔存在的频率，达到时频局部化目的。其表达式为：

Gf(,)f(t),g(t)ejtf(t)g(t)ejtdt

R式中，g(t)为时限函数，即窗口函数，ejt起频限作用，Gf(,)大致反映了f(t)在时、频率为的信号成分含量。

由上式，短时Fourier变换能实现一定程度上的时频局部化，但窗口函数确定时，窗口大小和形状固定，所得时频分辨率单一。

小波分析阶段：

为了克服上述缺点，小波变换应运而生。小波变换在研究信号的低频成分时其窗函数在时间窗长度上增加，即在频率宽上减小；在研究信号的高频成分时其窗函数在时间窗长度上减小，而在频率宽上增加。对信号可以进行概貌和细节上的分析。

小波的定义：

()，若满足设(t)L2(R)（为能量有限的空间信号），其Fourier变换为容许条件：

|()|2||d

(0)(t)dt0，说明(t)具有波动则称(t)为母小波，由容许条件可得：性，在有限区间外恒为0或快速趋近于0.t12以Marr小波(t)(1t)e2为例，如下图：

22

将母小波进行伸缩平移所得小波系列称为子小波，定义式如下:

b,a(t)1tb(),a0

aa其中a为伸缩因子，b为平移因子。

a 以Marr小波为例，分别取伸缩平移因子a，b为0.5、1、2、4；-1、0、1，对应图形如下:

Daubichies小波

常见的小波有Daubechies、Symlets、Morlet、Mexican Hat、Meyer小波等，其对应的图形及性质如下：

Daubechies小波是正交小波，没有解析表达式（除Haar小波外）。其简写形式为dbN，N表示阶数，支集区间为（0，2N-1）。

Symlets小波与db小波的差别是sym小波有更好的对称性。

Morlet小波不具备正交性，不存在紧支集，不能做离散小波变换，没有解析尺度函数，其小波函数为：

(x)ex/2cos(5x)

Mexican Hat小波不具有正交性，不存在尺度函数，是高斯函数的二阶导数，小波函数为：

2(x)21/4x2/2e 3Meyer小波为在频域定义的具有解析形式的正交小波，不存在紧支集，但其频谱有限，具有对称性。

小波函数的特点：

正交性：小波函数与自身内积为1，而与其伸缩平移后的小波系列内积为0。正交小波的优点是小波变换可将信号分解到无重叠的子频带上，并且可以进行高效的离散小波变换。

对称性：不具有对称性的小波函数所重构的信号会有相位失真。

紧支性：具有紧支性的小波其小波函数仅在有限区间内是非零的，其局部化能力强，小波变换复杂度低。

正则性：用于刻画小波函数的光滑程度，正则性越高，函数越光滑。

消失矩：用于衡量小波逼近光滑函数时的能力。消失矩越大，压缩比越大。

尺度函数：若函数(t)L2(R)，其整数平移系列k(t)(tk)满足：

k(t),k(t)kk

则称(t)为尺度函数。

对尺度函数(t)进行平移和伸缩，可得一个尺度和位移均可变的函数集合：

j,k(t)2j/2(2jtk)k(2jt)

称每一个固定尺度j上的平移系列k(2jt)所张成的空间Vj为尺度j的尺度空间：

Vjspank(2jt),kZ

正交多分辨分析：Hilbert空间L2(R)中，若一列闭子空间{Vj}jz满足如下性质：嵌套性：VjVj1,(jz);逼近性：Vj{0},VjL2(R);

jzjz伸缩性：f(t)Vjf(2t)Vj1;

平移不变性：f(t)Vjf(tk)Vj,jZ;

正交性（Riesz基）：存在(t)V0，使得{(tk),kz}是V0的标准正交基。滤波器：在二尺度方程中，对系数系列{hk}kz和gk(1)kh1k,kz作Fourier 变换得H()和G()，其中H()11ikikheG()ge，称H()和kk2kz2kzG()分别为低通滤波器和高通滤波器。称{hk}kz和{gk}kz分别为低通滤波器系数和高通滤波器系数。小波变换

连续小波变换：设为一母小波，f(t)L2(R)，称

(Wf)(a,b)f,a,b|a|12f(t)(tb)dt a为f的连续小波变换。

离散小波变换

离散小波：通过离散化连续小波变换中的平移因子b和尺度因子a得到，通

mm常取aa0,bnb0a0,m,nZ.m2离散小波变换：(Wf)(a,b)f,a,b|a0|f(t)(a0mtnb0)dt

若取a02,b01，可以得到二进小波：m,n(t)2m/2(2mtn),m,nZ

信号的离散小波变换并不是直接由尺度函数(t)和对应的小波(t)与信号内积来实现，而是利用滤波器组h[n]和g[n]来实现，用矩阵形式表述如下：

cj[0]00cj1[0]c[1]h[0]h[1]h[k]0c[1]j00h[0]h[1]h[k]0j1 c[n1]c[n1]h[k]0000h[0]h[1]jj12dj[0]00cj1[0]d[1]g[0]g[1]g[k]0c[1]j00g[0]g[1]g[k]0 j1d[n1]c[n1]g[k]0000g[0]g[1]jj12其中，设滤波器长度为k。并且两滤波器系数间有如下关系：

gk(1)kh1k,kz

|hkzk|22； 2； h2k11;kzhkzkzkh2khkzk2nkh2n0,nz

以db5小波为例，其低通滤波器系数如下（这里取二尺度方程为(t)2hk(2tk)）所得的系数：

kzh[0]=0.160102397974;h[1]=0.603829269797;h[2]=0.724308528438;h[3]=0.***1;h[4]=-0.242294887066;h[5]=-0.032244869585;h[6]=0.077571493840;h[7]=-0.006241490213;h[8]=-0.012580751999;h[9]=0.003335725285;变换所得系数cj和dj分别为离散小波变换的不同尺度下的低频和高频系数。

小波逆变换即信号的重建运算，重构是从尺度最低的近似系数cj和细节系数dj开始，通过低频和高频重构滤波器恢复出上一尺度的近似信号cj1，继续这个过程，直到恢复原始信号。其计算公式为：

cj1,mcj,kh(m2k)dj,kg(m2k),kZ

kk离散小波变换与重构实例如下：

所采用的信号为添加白噪声的正弦信号，信号共1000个采样，采用db4小波做3层分解，其原始信号、低频系数、高频系数和重构信号如下图：

第四篇：算法总结

算法分析与设计总结报告

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{n0,ng(y)对于所有yF(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 Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广