第一篇：VJ压缩算法总结
VJ压缩算法总结
算法介绍
VJ压缩算法是一种适用于串行链路的TCP/IP头压缩算法，对小包有较高的压缩率，可以有效提高串行链路的链路利用率，并有效提高交互式应用的响应速度
算法概述
在一个TCP/IP连接活动期间，在连接上发送的TCP/IP包的包头有大部分信息是保持不变的，这部分信息可以被压缩掉。如果发送方把这部分被压缩掉的信息用一个连接ID来替代，接收方保存上一次收到的TCP/IP包头，则接收方就可以根据存储的信息恢复被压缩掉的数据，链路上的TCP/IP头压缩就得以实现。
算法原理
1.压缩
发送方通过串行链路驱动来发送IP数据报，IP数据报经过压缩器，压缩器检查这个IP数据报是否封装了一个TCP报文段，如果不是就把它标记为TYPE_IP，并封装后发送；否则就在本地存储的一个包头数组中搜索该TCP报文段对应的连接，如果找到，就压缩这个IP数据报，把包头拷贝到查找到的槽位，标记这个包为COMPRESSED_TCP并成帧后发送；如果未找到对应的连接，就把数组中最旧的条目删除，并复制TCP/IP头到这个槽位，同时标记这个包为UNCOMPRESSED_TCP，并发送到对端。UNCOMPRESSED_TCP标记的包没有被压缩，它和正常的IP数据报的唯一区别是其“协议”字段被连接ID替代。连接ID是该TCP/IP数据报头在包头数组中的位置索引。这也是发送法用来同步接受方的方法。接受方收到这个报文后把它按照连接ID存放在数组中，用以解压后续的压缩数据包。
2.解压缩
解压缩器根据收到的不同类型的包做不同的转换：
1）对TYPE_IP类型的包，简单地把它提交给上层协议(IP层)2）对UNCOMPRESSED_TCP类型的包，从IP头的协议类型字段提取出连接ID，并把该字段恢复成IPPROTO_TCP，连接ID被用于在本地数组中存储恢复后的TCP/IP头，连接ID即是该报文头在数组中的索引。
3）对COMPRESSED_TCP类型的包，用包头的连接ID定位到保存的包头，根据存储的包头恢复压缩的数据包头，并用恢复后的包头更新存储的包头。压缩/解压缩的流程如图1所示
图1 SLIP VJ压缩/解压缩算法实现
3.压缩包的格式
被压缩过的TCP/IP报文头部如图2所示：
图2 压缩后的TCP/IP报头
Byte 0 是一个报头变化掩码，用以指示这个报头相对与上一个报头变化的字段，Byte 1是连接标识号，接收方可用它来定位这个连接上一个被存储的报头。Byte 2 – 3是TCP的校验和，接下来就是变化掩码所指定的变化的字段。Delta标示发送的是差值。由于一个连接可能持续较长时间，而在这段时间内，连接标识符是不变的，也可以被压缩掉，C标志位被清除的时候表示连接标识符不变。
算法参考实现
1.压缩器
压缩器对输入的IP包做如下检验：
1)如果四层协议不是TCP，把它标记为TYPE_IP并发送 2)如果分组是IP分片，不做压缩，标记为TYPE_IP并发送
3)如果TCP的SYN, FIN, 或是RST标志被设置或是ACK标志没有设置，则认为该TCP段不可压缩，标记为TYPE_IP并发送
4)通过前3个检查的包将以UNCOMPRESSED_TCP或COMPRESSED_TCP的形式发送
5)如果没有找到对应该报文的连接，则老化一个连接(使用LRU算法)，并存储该报文头，把改报文的协议类型字段替换为连接号，把它作为UNCOMPRESSED_TCP类型的报文发送
6)如果找到了对应该报文的连接，则把存储的包头和当前包头做比较，如果protocol version, header length, type of service, don’t fragment, time-to-live, data offset, IP options和TCP options字段有变化，则发送一个UNCOMPRESSED_TCP类型的报文 7)如果第6步中列举的字段都没有变化，则压缩该TCP/IP报头。
a)如果URG标志被设置，则把紧急指针字段拷入压缩后的报文头，并设置变化掩码的U位。如果URG标志未设置，则比较当前报文头和保存报文头的紧急指针字段，如果有变化，则不压缩当前报文，把它作为UNCOMPRESSED_TCP处理。
b)计算当前报文头和存储报文头窗口字段的差值，如果不为0，在压缩报文中存储该差值，并设置change mask的W位
c)计算TCP确认序列号字段的差值，如果结果小于0或是大于2-1，则不压缩报文，把它作为UNCOMPRESSED_TCP处理，否则，如果结构非0，在压缩报头中记录该差值并设置change mask的A位
d)计算TCP序号之间的差值，如果结果小于0或是大于2-1，则不压缩报文，把它作为UNCOMPRESSED_TCP处理，否则，如果结构非0，在压缩报头中记录该差值并设置change mask的S位
e)U, A, S, W位计算完之后开始检查特殊情况：
如果U, S和W位都被设置，则不执行压缩，发送一个UNCOMPRESSED_TCP的包。
如果只有S位被设置，检查序号的改变值是否等于上一个分组中的用户数据长度，如果相等，修改change mask 为SAWU，并丢弃压缩报文中的序号变化值 如果只有S和A被设置，检查它们的变化量是否相等，并等于上一个分组的用户数据长度，如果相等，设这change mask为SWU，并丢弃已计算出的序号和确认序号改变值。
如果报头没有任何改变，查看该分组是否有用户数据(在这种情况下，这个TCP段可能是一个重复的ACK或是窗口探针)或者前一个分组包含用户数据(在这种
1616情况下这个分组是一个重传的分组)，如果这两种情况中的任何一种出现，发送一个UNCOMPRESSED_TCP类型的分组。
f)计算packet ID字段的差值，如果不是1，设置change mask的I位，并保存差值 g)如果PUSH标志被设置，则设置change mask的P位 h)把当前的TCP/IP报头拷贝到报头数组中 i)在原始报文中用压缩后的报头替换原始报头 j)压缩后的报文传给下层传输
2.解缩压器
解压缩器工作在接收端，它根据压缩器的指示处理压缩报头。解压缩器可能收到4种报文：压缩器产生的3种报文以及由接收器在检测到帧错误时产生的TYPE_ERROR伪报文。解压缩器根据报文的不同类型做不同的处理：
如果是TYPE_ERROR或是未知类型的报文，设置状态中的一个toss标志以丢弃所有COMPRESSED_TCP类型的报文，直到设置C标志的COMPRESSED_TCP类型的报文到达或是UNCOMPRESSED_TCP类型的报文到达。此时不返回任何报文
如果是TYPE_IP类型的报文，不做任何处理，直接返回。
如果是UNCOMPRESSED_TCP类型的报文，检查IP PROTOCOL的连接号字段，如果非法，则设置toss标志，并停止处理；否则清除toss标志，拷贝TCP/IP头到该字段指定的位置，并记录这个连接，恢复IP PROTOCOL字段为TCP(6)并返回这个报文。
如果是COMPRESSED_TCP类型的报文，做如下处理：
如果change mask 的C位被设置，则检查压缩报头中的connection number字段，如果非法，设置toss标志并停止处理，否则记录这个连接，并清除toss标志 如果change mask 的C标志没有设置，并且toss被置位，丢弃该分组。 把压缩报头的TCP校验和拷贝到存储报头中。
如果change mask的P标志被置位，则设置存储报头的PUSH标志
如果change mask的S, A, W, U位都被设置，计算上一个分组用户数据的长度(用存储报头的total length字段减去TCP和IP头的长度)，并加上存储报头的TCP序号字段作为新的TCP序号。
如果S, W, U位被设置，而A没有设置，则计算上一个TCP段中用户数据的长度，并把它分别加上存储报头的TCP序号和ACK序号作为新的序号。 否则按照压缩器设置的顺序来解释change mask的各个字段
上述过程结束后，重新计算IP的total length（收到的用户数据长度加上存储的TCP/IP报头长度）和IP头校验和，至此完全解压了压缩的TCP/IP头。
第二篇：基于压缩感知理论的重构算法介绍
压缩感知重构算法综述
李珅
1,2，马彩文，李艳，陈萍
111（1.中国科学院西安光学精密机械研究所 光电跟踪与测量室,陕西省 西安市 710119;2.中国科学
院研究生院,北京 100039）
摘要：现代社会信息量的激增带来了信号采样、传输和存储的巨大压力，而近年来出现的压缩感知理论(Compressed Sensing,CS)为解决该问题提供了契机。该理论指出：对于稀疏或可压缩的信号，能够以远低于奈奎斯特频率对其进行采样，并通过设计重构算法来精确的恢复该信号。本文介绍了压缩感知理论的基本框架，综述了压缩感知理论的重构算法，其中着重介绍了最优化算法和贪婪算法并比较了各种算法之间的优劣，最后探讨了压缩感知理论重构算法未来的研究重点。
关键词：信号采样;压缩感知;稀疏;重构算法 中图法分类号： TP301.6 文献标识码：A
Survey on reconstruction algorithm based on compressive
sensing
Li Shen1,2, Ma Cai-wen1, Li Yan1, Chen Ping1
(1.Xi’an Institute of Optics and Precision Mechanics of CAS, Xi’an Shaanxi 710119, China；2.Graduate University of Chinese Academy of Sciences, Beijing 100039, China）
Abstract：With the rapid demanding for information, the existing systems are very difficult to meet the challenges of high speed sampling, large volume data transmission and storage.Recently, a new sampling theory called compressive sensing(CS)provides a golden opportunity for solving this problem.CS theory asserts that a signal or image, unknown but supposed to be sparse or compressible in some basis, can be subjected to fewer measurements than traditional methods use, and yet be accurately reconstructed.This paper gives a brief overview of the CS theory framework and reviews the reconstruction algorithm of CS theory.Next, this paper introduces the basis pursuit algorithm and greedy algorithms and explores the difference between them.In the end, we briefly discuss possible implication in the areas of CS data reconstruction.Key words：information sampling;compressive sensing;sparse;reconstruction algorithm
0 引言
随着现代科技的飞速发展，人们对信息量的需求也在剧增。传统的信息采样是基于香农采样定理，它指出信号的采样率不低于最高频率的两倍，信号才能被精确的重构。该理论支配着几乎所有信号的获取、处理、存储和传输。
一方面，在许多实际应用中（如超宽带通信，核磁共振，空间探测，高速AD转换器等），信息在存储和处理时，为达到采样率而需要大量的采样数据，从而导致采样硬件成本昂贵，获取效率低下甚至在某些情况难以实现。另一方面，在数据的存储和传输方面，传统的做法是先按照Nyquist方式获取数据，然后将获得的*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
数据进行压缩，最后将压缩后的数据进行存储或传输。显然，这样的方式造成很大程度的资源浪费，同时也提出了一个问题[1]：既然在压缩中需要丢弃大多数数据，为什么不在采样时直接取得我们需要的重要数据？ 近年来，D.Donoho、E.Candes及华裔科学家T.Tao等人提出了一种新的信息获取理论－压缩感知(Compressive Sensing)，以下简称为CS。该理论指出[1]：对于可压缩的信号，可以通过低于或远低于奈奎斯特标准的方式对其进行数据采样并精确重构该信号。与香农定理不同的是，压缩感知并不是直接测量信号本身，它使用非自适应线性投影（感知矩阵）来获得信号的整体构造从而直接得到重要的信息，忽略那些在有损压缩中会被丢弃的信息。一般来说，压缩感知涉及三个比较重要的层面 [2]：
一、信号稀疏域的选取，是压缩感知理论的基础和前提。
二、观测矩阵的选取，已经证明大部分具有一致分布的随机矩阵都可以作为观测矩阵。
三、重构算法的设计，由于压缩感知采用的是全局非自适应测量方法，观测数量远远少于信号长度，从而数据采集量大大减少。但是需要付出的代价是信号重建算法的软件成本。因此，CS重构算法的好坏直接影响到CS理论是否实用。
其中S是投影系数si,iiT构成的N×1维列向量。显然，X和S是同一个信号的等价表示，其中X是在时域或空间域的表示，S是在Ψ域的表示。当信号可以仅被K个基向量线性表示时，则称信号x为K-稀疏。当K<
sppsii1/pR(2)
传统思路中压缩信号就是采用这种正交变换的方式，其编码解码的策略为：编码首先构造正交基矩阵Ψ，作变换SX,保留S中最重要的K个分量及其对应的位置。解码将K个分量放回到其对应的位置，并将其他位置填0，以此构造Ψ，最后进行反变换S求得重构信号。
显然，这种以Nyquist-Shanon采样定理为准则的编码和解码方法有很多缺点。
一、采样后再进行压缩的方式浪费了大量的采样资源，如果采样后的信号长度仍然很长，那么变换会消耗很长时间；
二、由于需要保留的K个重要分量的位置是随着信号的不同而不同，所以这种编解码方式是自适应的，需要分配多余的存储空间以保留K个重要分量的位置。
三、K个重要分量有可能在传输过程中丢失其中的某几个分量从而造成较差的抗干扰能力。
近几年出现的压缩感知理论，对传统的理念是一次革新，它表明我们可以用比传统途径少得多的采样和测量来恢复信号。该理论主要依赖于两个原则[4]，稀疏（sparsity）和不相关(incoher-ence)，稀疏关于感兴趣的信号，它所表达的意思是：连续时间信号的信息率可能比根据其带宽所建议的小得多，离散时间信号所依赖自由度的T 压缩感知理论简介
1.1基本思想 可压缩（稀疏）的定义：考虑一个一维信号
Nx∈RN×1，都可以用N×1维基向量ii1线性表示。为了简化问题，假设基向量为规范正交向量，使用N×N的基矩阵1|2|...|N,信号x可以被表示为：
xsiii1NorS可以说，许多自然界的(1)
数量比它的长度少得多。
信号在某种程度上都是稀疏的或可压缩的，当以*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
合适的基Ψ来表示时，信号可以有很多简练的表达式。不相关表达了一种含义即以Ψ稀疏表示的信号一定可以在其所需要的域中展开。基于这两个原则，压缩感知理论指出，长度为n的信号X在某组正交基或紧框架nn上的变换系数是稀疏的，如果我们可以用一个与变换基Ψ不相关的观测基Ф（Rmn大多数随机矩阵都满足RIP，如高斯随机测量系和伯努利随机测量系。文献[13]的工作告诉我们：在某种意义上说，选择随机测量对于稀疏矩阵来讲是一种最佳策略，只需要几乎最少的m个测量便可恢复稀疏度为S≤m/log(n/m)的信号，而且分析时所需要的常量都很小。第二类为非相关测量系，即测量矩阵和变换基Ψ是不相关的，其不相关性可以通过测量它们之间的相关系数，文献[14]给出了测量矩阵Ф和变换基Ψ的相关系数μ = N1/2maxi,k|<Ψi, Фi>|，μ越小说明测量矩阵Ф和变换基Ψ的不相关性越大，测量所需要的数目也越少。
第三步：重构信号x，区别于奈奎斯特理论的线性感知问题，由于观测数量m远远小于信号长度n，重构面临着求解一个欠定方程组的问题。当信号x是稀疏或可压缩的，求解欠定方程组的问题可以转化为最小0范数问题如式(4)：，mn）对系数向量进行线性变换，并得到观测集合m1，则可以通过求解最优化问题来精确地重构信号X。
1.2 压缩感知采样过程
基于CS理论实现信号压缩的采样过程为： 第一步：找到某个基或紧框架Ψ，使得信号x在Ψ上是稀疏的，并求出变换系数：S ＝ ΨT X，其中S是X的等价或逼近的稀疏表示。变换基Ψ的选择可以为某种已被广泛应用的基，如小波基、傅里叶基、局部傅里叶基等[5][6]，其中关于正交基的选择，可以参考文献[1]和文献[7]。另外，可以使用紧框架（原子字典）来对信号进行稀疏表示，如曲线波Curvelets[8]和轮廓波Contourlets[9]，这两类变换基具有更好的方向性，并且各向异性，少量系数即可有效地捕捉图像的边缘轮廓，在边缘表示方面优于小波。第二步：需要设计一个平稳的、与变换基Ψ不相关的m×n维观测矩阵Ф，对S进行观测得到观测集合Y=ФS＝ФΨTX，该过程也可以表示为信号x通过矩阵Acs进行非自适应观测：Y=AcsX(其中Acs =ФΨT，称为CS信息算子)。需要关注的问题是观测矩阵Ф的选取，需要保证稀疏向量S从n维降到m维时重要信息不被破坏。在压缩感知理论中，受限等距属性（Restricted Isometry Property, RIP）N[10][11]
minTX0s..tAcsXTXY(4)
然而统计理论和组合优化理论告诉我们，组合优化是一个NP难问题，当N很大时，数值上无法有效实现，且抗噪声能力很差；Candes, Tao和Donoho等人已证明，当测量矩阵满足约束等距性质(Restricted Isometry Property, RIP)时，组合优化问题(或称，l0约束优化问题)可转化为数值上容易处理l1约束的凸优化问题：
minTX1s..tAcsXTXY(5)
除此之外还有一些其它方法可以重构信号,如:1）将l0范数松弛为lp范数；2）通过先验分布引入稀疏性，再用Bayesian方法实现信号稀疏重构；3）使用启发式算法(heuristic algorithms)，如借鉴图模型和编码理论中的belief-propagation和消息传递技术。
是判断矩阵是否可以成为测量矩阵的一个重要的标准。对于k稀疏向量S∈R来说，当它满足式(3)时，测量矩阵Ф满足RIP。
（1-）s2s2（1）s(3)压缩感知理论对于测量系有两个主要的分类：第一类为随机测量系，文献[10][12]已证明压缩感知重构算法研究
2.1 重构算法介绍
*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
现阶段CS重构算法大致可以分为以下几类。
第一类是贪婪迭代算法，针对组合优化问题提出，该类算法主要是将信号与原子字典之间的联系作为测量原子（系数）更加有效或非零的一种方式。基本原则就是通过迭代的方式寻找稀疏向量的支撑集，并且使用受限支撑最小二乘估计来重构信号。这类算法包括：匹配追踪算法(MP ，matching pursuit）、正交匹配追踪算法
[15]
比其他重构算法更优越的重构精度。目前该类算法包括：新期望极大值(Expectation-Maximization, EM)算法[25]、贝叶斯压缩感知(BCS,Bayesian Compressive Sensing)算法[26]、基于单测量向量(SMV，single measurement vector)模型提出的SBL[27](sparse Bayesian Learning)算法和基于多测量向量(MMV，Multiple Measurement Vectors)模型提出的MSBL[28]。SBL是贝叶斯学习中很重要的一类算法，SBLMSBL算法与l1范数凸优化算法不同的是，后者全局最小化通常并不是最稀疏解，而前者的全局最小值则是最稀疏的，并且全局最小值比一些典型的算法（如FOCUSS算法）更少。通过关注时间相关性对现有算法性能的影响，文献[29]提出了AR(autoregressive)-SBL算法，该算法将每一个信号源的建模都作为一次一阶自动回归过程，同时对数据本身进行学习得到AR系数。
(OMP，[16] orthogonal matching pursuit）、分段OMP算法(StOMP，stagewise orthogonal matching pursuit)、规范OMP算法[17](ROMP，Regularized Orthogonal Matching Pursuit)、CoSaMP算法[18](compressive sampling matching pursuit）、迭代硬阈值法
[19](iterative hard thresholding，IHT）以及GraDeS[20](gradient descent with sparsification)等。算法的复杂度大多是由找到正确支撑集所需要的迭代次数决定的，算法计算速度快但是需要的测量数据多且精度低。
第二类是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法为基础追踪算法（BP，Basic Pursuit），该算法提出使用l1范数替代l0范数来解决最优化问题，以便使用线性编程方法来执行。另一种算法为FOCUSS算法[21]，该算法使用lp范数（p<=1）替代l0范数求解最优化问题。另外，文献[22]还提出了通过极小化l0范数的平滑转换求解问题，称之为SL0方法。该类算法计算速度慢(计算复杂性为N^3)，但需要的测量数据少(O(K*log(N/K))且精度高。另外两种比较常见的凸松弛算法包括GPSR(Gradient Projection for Sparse Reconstruction)算法approximation)算法[24]
[23]
其他算法：这类方法有的要求信号的采样支持通过分组快速测试重建，如傅立叶采样，链式追踪和HHS(Heavg Hitters On Steroids)追踪。有的将贪婪算法和最优化算法相结合，如文献[30]提出的贝叶斯追踪算法(BPA)，算法将简单的贪婪追踪算法和最优化贝叶斯框架相结合，在信号的稀疏表示中找到有效的原子。BPA可以看作是对迭代检测估计(IDE,Iterative Detection Estima-tion)算法的修改。2.2 l1范数凸优化算法
基于l1范数凸优化算法的稀疏重构模型主要有两类[31]：
(LS)minyxxx2s..tx1和
(BPminx1s..t)yx2（6）
SpaRSA(sparse reconstruction by separable。GPSR算法通过使用梯度降的方法求解有界约束最优化问题，算法要求投影在可行域中以确保迭代过程的可行性。第三类算法是基于贝叶斯框架提出的重构算法，该类算法考虑到了信号的时间相关性，特别是当信号具有较强的时间相关性时，能够提供
其中，(LS)式为LASSO(Least Absolute Shrinkage and Selection Operator)问题[32]，(BP)式为基追踪去噪(Basis Pursuit Denoise, BPDN)问题[33], 当没有噪声时，就退化为单一的基追踪(BP)问题[34]。处理实际问题时，通过对系统测量条件的分析，可以得到噪声水平σ的大致估计。相比之下，要先验地估计原信号的l1范*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
数值τ是十分困难的，因此研究(BP)问题的求解更具有实际意义，但是(LS)问题可以作为求解(BP)问题的中间手段。
求解形如(LS)和(BP)的约束优化问题时，可将约束条件转换为惩罚项，构造非约束优化问题。即：
2x冗余的。匹配追踪的任务就是通过每一次匹配把待分析信号f(t)分解成库中一组成员gi(t)(i=1,2,…,N)的线性组合，且N越小越好，实际就是通过对一系列单一原子进行逼近的方法来逐步搜索信号的稀疏解。
匹配跟踪算法虽然简单，但由于它找到的是OMP是恢复稀疏信号算法中较早出现的一类算空间上克服了上述缺陷。
基于压缩感知理论，OMP算法可以通过已知的关于信号的O(mlnd)个随机线性测量来恢复d维空间中的信号。假设S是Rd 空间的k-稀疏信号，Ф为n×d维测量矩阵，列向量为φ1 到φd。数据向量v（v＝Фs）的列是从Ф中选取的某些列的组合。
算法的基本思想源于K-稀疏，是为了找到K个关键的分量，既然是关键，显然它的绝对值应该比其他（N－K）个分量大的多。基于上面的假设，算法就是要从测量矩阵Ф中找到参与信号x测量的列向量。方法是：设置一个剩余向量r和序号集合Λ，在每一次迭代中，从Ф中选出与数据v剩下部分即余量r最相关的那一列，将该列号添加到集合Λ中并从数据v中去掉该列所作的贡献并重新计算余量，直到m次迭代结束。算法最终会得到正确的列序号集合Λ以及数据v的N维近似值am和N维余量rm。需要注意的是，迭代过程中余量rt始终和Фt 的列向量正交。具体的算法可以参考文献[15]。
文献[15]中Tropp和Gilbert分析了OMP算法执行的性能，提出了合适的测量矩阵为N×d维随机矩阵，且具有（M0）独立性、（M1）归一化、（M2）联合相关性和（M3）最小奇异值四个性质。文献[36]也证明了当测量矩阵Ф满足RIP条件时（其中参数k11/(12K)）,OMP算法可通过K个步骤精确地恢复任意K-稀疏信号。同时该文对OMP算法进行了改进，提出了MOMP
逼近结果的稀疏度较差。(QP)minyx2x(7)
次优解，故算法收敛慢、事实上，（QP）问题中的控制参数λ可视为求解约束优化问题(LS)和(BP)中的拉格朗日乘数。因此，若参数σ、λ和τ选取合适，以上三个问题的解是一致的。其中（QP）问题是一个二阶锥规划(second-order cone program)问题，可利用内点法(interior-point)[9,35]求解。
文献[11]比较了各种不同的恢复算法，总结出了l1凸优化算法，如LASSO或BPDN[33,36]
法，通过把信号矢量投影到由选取原子张成的子，通过求解式（8）可以在稀疏计算的复杂度和精度之间提供最佳的平衡点。
minx12yx2x(8)2迭代阈值技术（iterative thresholding algorithm）在稀疏优化算法中经常被采用，一些迭代阈值算法被用在解决LASSO问题上，可以使迭代过程中每一次迭代的计算量减小，这样就可以将LASSO用于解决高维方面的问题[8]。在迭代阈值技术中，迭代收缩算法解决
[20]凸优化问题十分有效，包括IHT [19]、GraDeS、PCD(parallel coordinate descent)以及FISTA(fast-iterative-shrinkage thresholding algorithm)等。对于IHT和GraDes算法，由于该算法使用负梯度作为搜索方向，即Landweber迭代，所以造成算法执行效率偏低。2.3 贪婪算法
MP算法最初是Mallat等人在1993年提出的匹配追踪算法，基本原理就是首先建立一个来分析信号的基本库函数D，不要求库中所有基本函数gi(t)（也叫“原子”）相互正交，但要求其二范数||gi(t)||2=1。因此这组函数并非相互独立，是有*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
（multi-candidate OMP）算法。该算法对OMP的改进在于：在每一次的迭代中，OMP算法只选择一个候选列加入到原子集合中，而MOMP算法选择多个候选列加入到最优原子集合，从而减少迭代的次数，降低重构信号的计算复杂度。文献[34]中，Rauhut研究了使用傅里叶矩阵作为测量矩阵的OMP算法的执行性能，通过大量的试验，他们证明了通过O(Klog(n))个测量就可以精确的恢复K-稀疏信号。同时，Kunis和Rauhut提出，对于m-稀疏信号给出的O（mlnd）次测量，在第一次迭代中，OMP方法可以从测量矩阵中选出正确的列，但是由于矩阵列向量之间存在的微小随机相关性，很难对OMP算法后续的迭代进行分析。于是D.Needell 和 R.Vershynin就在文献[17]中提出了对OMP算法的改进，称为ROMP算法（Regularized Orthogonal Matching Pursuit），该算法可以通过选择替代信号的最大元素并采用正则化的方式来确保没有太多的错误元素被选择，ROMP算法比OMP算法更快速且重构结果更加均衡稳定。文献[37]中Nam H.Nguyen和Trac D.Tran使用ROMP方法从含噪测量中稳定地重构可压缩信号。Donoho也在文献[16]中提出了分段OMP算法(stagewise orthogonal matching pursuit)，该算法对OMP算法进行了简化，通过设置阈值的方法来找到替代的信号，同时以逼近精度为代价进一步提高了计算速度，更适合求解大规模问题。除此之外，2005年Chinh和Minh提出了树型正交匹配算法[38]（TOMP, Tree-based Orthogonal Matching Pursuit），该算法是通过构造稀疏树并在树中追踪重要的系数来实现的。TOMP算法考虑到了信号的多尺度分解时稀疏信号在各奇异子带位置的关系，从而构建了比BP和OMP算法更加快速且重构精度更高的算法。
压缩感知追踪算法（CoSaMP,Compressed Sampling Matching Pursuit）是最近由Needell和Tropp提出的[18]，和大多数贪婪算法一样，CoSaMP算法采用了正交测量矩阵Ф（Ф*TФ近似归一化），因此算法中的替代信号p = Ф*TФS的最大元素与S的非零输入相关联。算法的执行是将p的最大元素加入到运行支撑集中，并使用最小二乘法来获取信号的估计。最后，修正最小二乘估计并更新错误余量。2.4 一些新想法
最近，很多学者提出了一些新想法，其中之一就是将消息传递用于解决压缩感知的信号重构问题。其中，Donoho等提出了一种算法称之为AMP（approximate message passing）[39]，这种算法既具有迭代阈值算法的低复杂度，同时也具备基追踪算法较强的信号重构能力。事实上，AMP是将一些广泛采用的算法集合成的一个实例，是一类新的低复杂度迭代阈值算法，用于解决从较少的线性测量中重构稀疏信号的问题。
考虑式子：
yAS0，S0RN,y,wRn
(9)
其中S0是稀疏向量，ω为噪声。一般的AMP算法的迭代公式如下：
xt10(xtATzt;t)zyAx
ttItnzt(10)
x和z的初始值为x0=0,z0=y，其中，0(x;)(x)sign(x)属于软阈值函数；It 是xt的有效集合。具体的迭代算法和一些相关算法可参见文献[39-44]，这里就不再详述。算法对比及特点评述
BP算法的优势在于它可以当作线性编程问题来解决，因而可以使用标准的技术软件来处理。但是在实际应用中，对于稀疏信号的重构，商业化的软件并不能很好的工作，因为解向量是稀疏的，而测量向量是稠密的，所以即使是常见的图像尺寸，计算也相当耗时且执行复杂度很高。除此之外，由于l1范数无法区分稀疏尺度的位置，所以尽管整体上重构信号在*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
欧氏距离上逼近原信号，但存在低尺度能量搬移到高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。
贪婪算法是CS重构算法中使用比较频繁的一类算法（主要为OMP算法及其改进算法），基本思想是根据残差向量与测量矩阵之间相关性最大的分量，逐步找到原信号的支撑集，并在与信号支撑集相对应的子矩阵上进行类似于最小二乘的计算。该算法较凸优化算法来说，大大提高了计算效率，同时在算法中可以加入额外的先验信息，提高了重构信号的精度。如基于模型的压缩感知方法[45](model based compressed sensing）和前面提到过的贝叶斯压缩感知方法（BCS）。其中BCS算法借助传统的贝叶斯方法与机器学习中的主动学习方法,将关于稀疏性的先验信息用垂直先验分布来建模，提出了自适应的感知方法以及相应的恢复方法。而基于模型的压缩感知方法利用小波树模型和块稀疏模型，仅需要与稀疏程度相当的测量数目即可实现信号的鲁棒性恢复[46]。
当信号稀疏性不是很好且测量中噪声较大时，贪婪算法效果没有凸优化算法好。同时，贪婪算法中涉及到的最小二乘过程要进行矩阵求逆，需大量的矩阵-向量乘法，当算子Φ存在快速算法时也难以应用。近两年，随着梯度投影、迭代阈值等算法的出现，最小l1范数方法的计算效率大幅度提高，同时还可以充分利用算子Φ的快速算法。
CS重构算法各有优缺点，在设计算法时，应根据所应用的领域和信号的特点来进行选择。主要目的是配合CS测量矩阵尽可能减少测量数据并保证重构信号的精度，同时根据需求进行合理权衡。的对于信号重构所采用的最小二乘优化算法已经不够充分，采用不同方式的凸优化算法和贪婪算法来重构信号是压缩感知研究的一个重点。本文对压缩感知理论的框架做了一个简单的描述，着重放在了对压缩感知重构算法的综述上，主要介绍了一些常用的CS重构算法如贪婪算法、凸优化算法等，同时对各算法的特点进行了评述。纵观现在的压缩算法，可以看出今后对于压缩算法的改进主要集中在三个方面：1）构造更稳定、计算复杂度低且需要较少的观测次数的重构算法来精确地恢复可压缩信号；2）构造有效的重构算法来精确恢复含噪信号或在采样过程中被引入噪声的信号；3）将理论与实际相结合，根据特定的领域或应用构造具有针对性的有效可行的压缩算法。参考文献
[1] D L Donoho．Compressed sensing[J].IEEE Transactions on Information Theory.2006,52(4): 1289-1306.[2] 石光明,刘丹华,高大化.压缩感知理论及其研究进展[J].电子学报.2009, 37:1070-1081.[3] Richard G.Baraniuk.Compressive Sensing[J], IEEE Signal Processing Magazine, 2007:118-124.[4] Emmanuel J.Candès, Michael B.Wakin.An Introduction To Compressive Sampling[J].IEEE Signal Processing Magazine,2008,25(2):21-30.[5] I.Daubechies, Ten Lectures on Wavelets.New York:SIAM, 1992.[6] S.Mallat, A Wavelet tour of signal processing, the sparse way, 2009.[7] Emmanuel J.Candès, Justin Romberg, Terence Tao.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathematics, 2006,59(8):1207-1223.[8] E.Cand`es and D.Donoho, New tight frames of curvelets and optimal representations of objects 4 结束语
对于稀疏信号或可压缩信号来说，压缩感知理论作为一种新的信号获取方式，比传统的采样方式更加有效。在压缩感知理论中，传统*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
with piecewise singularities, Comm.Pure Appl.Math.vol.57, pp.219-266, 2004.[9] D.D.-Y.Po and M.N.Do, Directional multiscale modeling of images using the contourlet transform, IEEE Transactions on Image Processing, vol.15(6), pp.1610–1620, 2006.[10] R.Baraniuk, M.Davenport, R.DeVore, and M.Wakin.A simple proof of the restricted isome-try property for random matrices.Constructive Approximation, 2007.[11] E.Cand`es.The restricted isometry property and its implications for compressed sensing.Compte Rendus de l’Academie des Sciences, Paris, 2008.[12] E.Cand`es and T.Tao.Near optimal signal recovery from random projections: Universal encoding strategies.IEEE Transactions on Information Theory, vol.52, pp.5406-5425, 2006.[13] Jérome Bobin, Jean-Luc Starck, Roland Ottensamer.Compressed Sensing in Astronomy[J].IEEE Journal of Selected Topics in Signal Processing, 2008,2(5):718-726 [14] Emmanuel J.Candès.Compressive sampling [A].Proceeding of the International Congress of Mathematicians[C].Madrid, Spain, 2006, 3: 1433-1452.[15] Joel A.Tropp, Anna C.Gilbert.Signal Recovery From Random Measurements Via Orth-ogonal Matching Pursuit[J].IEEE Transactions on Information Theory.2007, 53(12): 4655-4666.[16] D.L.Donoho,Y.Tsaig, I.Drori, and J.L.Starck, “Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit” Stanford Statistics Technical Report 2006-2, 2006.[17] D.Needell and R.Vershynin, “Uniform uncertainty principle and signal recovery via regularized orthogonal matching
pursuit,”
Foundations of Computational Mathematics, vol.9，no.3, pp.317–334, 2009.[18] Needell, D.,Tropp, J.A.CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis, 2009,26(3):301-321.[19] T.Blumensath and M.E.Davies, “Iterative hard thresholding for compressed sensing,” Applied and Computational Harmonic Analysis, vol.27, no.3, pp.265–274, 2009.[20] R.Garg and R.Khandekar, “Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property,” in Proceedings of the 26th International Confer-ence on Machine Learning, pp.337–344, 2009.[21] I.F.Gorodnitski and B.D.Rao, Sparse signal reconstruction from limited data using focuss: a re-weighted norm minimization algorithm[J].IEEE Transactions on Signal Processing, 1997,45(3):600 –616.[22] H.Mohimani, M.Babaie-zadeh, and C.Jutten.A fast approach for overcomplete sparse decomposition based on smoothed l0-norm[J].IEEE Transactions on Signal Processing, 2009, 57(1):289–301.[23] Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[J].IEEE J.Sel.Top.Sign.Proces: Special Issue on Convex Optimization Methods for Signal Processing, 2007,1:586-597.[24] S.J.Wright, R.D.Nowak, and M.A.T.Figueiredo, “Sparse reconstruction by separable approximation,” IEEE Transactions on Signal Processing, vol.57, no.7, pp.2479–2493, 2009.[25] H.Zayyani, M.Babaie-zadeh, C.Jutten.Decoding real-field codes by an iterative expectation-maximizaion algorithm[A].ICASSP [C], 2008, pp.3169–3172.[26] S.Ji, Y.Xue, and L.Carin.Bayesian *基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
compressive sensing[J].IEEE Transactions on Signal Processing, 2008,56(6):2346–2356.[27] D.P.Wipf and B.D.Rao, “Sparse Bayesian learning for basis selection,” IEEE Trans.on Signal Processing, vol.52, no.8, pp.2153–2164, 2004.[28] D.P.Wipf and B.D.Rao, “An empirical Bayesian strategy for solving the simultaneous sparse approximation problem,” IEEE Trans.on Signal Processing, vol.55, no.7, pp.3704–3716, 2007.[29] Z.Zhang and B.D.Rao, “Sparse signal recovery in the presence of correlated multiple measurement vectors,” in Proc.of the 35th International Conference on Acoustics, Speech, and Signal Processing(ICASSP 2010), Texas, USA, 2010, pp.3986–3989.[30] H.Zayyani, M.Babaie-Zadeh, C.Jutten.Bayesian Pursuit Algorithm
for
Sparse Representation[A].IEEE Int.Conf.on Acoustics, Speech, and Signal Processing(ICASSP)[C].Taipei, Taiwan, April 2009.[31] 刘吉英.压缩感知理论及在成像中的应用[D].国防科技技术大学研究生院博士学位论文, 2010 [32] R.Tibshirani.Regression shrinkage and selection via the Lasso[J].J.Roy.Statist.Soc.Ser.B., 1996, 58: 267-288 [33] S.S.Chen, D.L.Donoho, M.A.Saunders.Atomic decomposition by basis pursuit[J].SIAM Rev., 2001, 43: 129-159 [34] S.Kunis, H.Rauhut.Random sampling of sparse trigonometric polynomials ii-orthogonal matching pursuit versus basis pursuit[OL].http://dsp.rice.edu/cs.[35] E.J.Candes.l1-magic[EB/OL].[2011-09-29].http://www.xiexiebang.com
第三篇：算法总结
算法分析与设计总结报告
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-完全的第五篇：算法总结材料
点击咨询 