压缩感知重构算法之正交匹配追踪(OMP)
前面经过几篇的基础铺垫，本篇给出正交匹配追踪(OMP)算法的MATLAB函数代码，并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码、信号稀疏度K与重构成功概率关系曲线绘制例程代码。
0、符号说明如下：
压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< (1) y为观测所得向量，大小为M×1 (2)x为原信号，大小为N×1 (3)θ为K稀疏的，是信号在x在某变换域的稀疏表示 (4)Φ称为观测矩阵、测量矩阵、测量基，大小为M×N (5)Ψ称为变换矩阵、变换基、稀疏矩阵、稀疏基、正交基字典矩阵，大小为N×N (6)A称为测度矩阵、传感矩阵、CS信息算子，大小为M×N 上式中，一般有K< 1、OMP重构算法流程： 2、正交匹配追踪(OMP)MATLAB代码(CS_OMP.m) [plain]view plaincopy 1.function [ theta ] = CS_OMP( y,A,t ) 2.%CS_OMP Summary of this function goes here 3.%Version: 1.0 written by jbb0523 @2015-04-18 4.% Detailed explanation goes here 5.% y = Phi * x 6.% x = Psi * theta 7.% y = Phi*Psi * theta 8.% 令 A = Phi*Psi, 则y=A*theta 9.% 现在已知y和A，求theta 10. [y_rows,y_columns] = size(y); 11. if y_rows 12. y = y';%y should be a column vector 13. end 14. [M,N] = size(A);%传感矩阵A为M*N矩阵 15. theta = zeros(N,1);%用来存储恢复的theta(列向量) 16. At = zeros(M,t);%用来迭代过程中存储A被选择的列 17. Pos_theta = zeros(1,t);%用来迭代过程中存储A被选择的列序号 18. r_n = y;%初始化残差(residual)为y 19. for ii=1:t%迭代t次，t为输入参数 20. product = A'*r_n;%传感矩阵A各列与残差的内积 21. [val,pos] = max(abs(product));%找到最大内积绝对值，即与残差最相关的列 22. At(:,ii) = A(:,pos);%存储这一列 23. Pos_theta(ii) = pos;%存储这一列的序号 24. A(:,pos) = zeros(M,1);%清零A的这一列，其实此行可以不要，因为它与残差正交 25. %y=At(:,1:ii)*theta，以下求theta的最小二乘解(Least Square) 26. theta_ls = (At(:,1:ii)'*At(:,1:ii))^(-1)*At(:,1:ii)'*y;%最小二乘解 27. %At(:,1:ii)*theta_ls是y在At(:,1:ii)列空间上的正交投影 28. r_n = y - At(:,1:ii)*theta_ls;%更新残差 29. end 30. theta(Pos_theta)=theta_ls;%恢复出的theta 31.end 3、OMP单次重构测试代码(CS_Reconstuction_Test.m) 代码中，直接构造一个K稀疏的信号，所以稀疏矩阵为单位阵。 [plain]view plaincopy 1.%压缩感知重构算法测试 2.clear all;close all;clc; 3.M = 64;%观测值个数 4.N = 256;%信号x的长度 5.K = 10;%信号x的稀疏度 6.Index_K = randperm(N); 7.x = zeros(N,1); 8.x(Index_K(1:K)) = 5*randn(K,1);%x为K稀疏的，且位置是随机的 9.Psi = eye(N);%x本身是稀疏的，定义稀疏矩阵为单位阵x=Psi*theta 10.Phi = randn(M,N);%测量矩阵为高斯矩阵 11.A = Phi * Psi;%传感矩阵 12.y = Phi * x;%得到观测向量y 13.%% 恢复重构信号x 14.tic 15.theta = CS_OMP(y,A,K); 16.x_r = Psi * theta;% x=Psi * theta 17.toc 18.%% 绘图 19.figure; 20.plot(x_r,'k.-');%绘出x的恢复信号 21.hold on; 22.plot(x,'r');%绘出原信号x 23.hold off; 24.legend('Recovery','Original') 25.fprintf('\n恢复残差：'); 26.norm(x_r-x)%恢复残差 运行结果如下：（信号为随机生成，所以每次结果均不一样） 1）图： 2）Command Windows Elapsed time is 0.849710 seconds. 恢复残差： ans = 5.5020e-015 4、测量数M与重构成功概率关系曲线绘制例程代码 [plain]view plaincopy 1.%压缩感知重构算法测试CS_Reconstuction_MtoPercentage.m 2.% 绘制参考文献中的Fig.1 3.% 参考文献：Joel A. Tropp and Anna C. Gilbert 4.% Signal Recovery From Random Measurements Via Orthogonal Matching 5.% Pursuit，IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 53, NO. 12, 6.% DECEMBER 200 7. 7.% Elapsed time is 1171.606254 seconds.(@20150418night) 8.clear all;close all;clc; 9.%% 参数配置初始化 https://www.doczj.com/doc/c712843805.html,T = 1000;%对于每组(K,M,N)，重复迭代次数 11.N = 256;%信号x的长度 12.Psi = eye(N);%x本身是稀疏的，定义稀疏矩阵为单位阵x=Psi*theta 13.K_set = [4,12,20,28,36];%信号x的稀疏度集合 14.Percentage = zeros(length(K_set),N);%存储恢复成功概率 15.%% 主循环，遍历每组(K,M,N) 16.tic 17.for kk = 1:length(K_set) 18. K = K_set(kk);%本次稀疏度 19. M_set = K:5:N;%M没必要全部遍历，每隔5测试一个就可以了 20. PercentageK = zeros(1,length(M_set));%存储此稀疏度K下不同M的恢复成功概率 21. for mm = 1:length(M_set) 22. M = M_set(mm);%本次观测值个数 23. P = 0; 24. for cnt = 1:CNT %每个观测值个数均运行CNT次 25. Index_K = randperm(N); 26. x = zeros(N,1); 27. x(Index_K(1:K)) = 5*randn(K,1);%x为K稀疏的，且位置是随机的 28. Phi = randn(M,N);%测量矩阵为高斯矩阵 29. A = Phi * Psi;%传感矩阵 30. y = Phi * x;%得到观测向量y 31. theta = CS_OMP(y,A,K);%恢复重构信号theta 32. x_r = Psi * theta;% x=Psi * theta 33. if norm(x_r-x)<1e-6%如果残差小于1e-6则认为恢复成功 34. P = P + 1; 35. end 36. end 37. PercentageK(mm) = P/CNT*100;%计算恢复概率 38. end 39. Percentage(kk,1:length(M_set)) = PercentageK; 40.end 41.toc 42.save MtoPercentage1000 %运行一次不容易，把变量全部存储下来 43.%% 绘图 44.S = ['-ks';'-ko';'-kd';'-kv';'-k*']; 45.figure; 46.for kk = 1:length(K_set) 47. K = K_set(kk); 48. M_set = K:5:N; 49. L_Mset = length(M_set); 50. plot(M_set,Percentage(kk,1:L_Mset),S(kk,:));%绘出x的恢复信号 51. hold on; 52.end 53.hold off; 54.xlim([0 256]); 55.legend('K=4','K=12','K=20','K=28','K=36'); 56.xlabel('Number of measurements(M)'); 57.ylabel('Percentage recovered'); 58.title('Percentage of input signals recovered correctly(N=256)(Gaussian)'); 本程序在联想ThinkPadE430C笔记本（4GB DDR3内存，i5-3210）上运行共耗时1171.606254秒，程序中将所有数据均通过“save MtoPercentage1000”存储了下来，以后可以再对数据进行分析，只需“load MtoPercentage1000”即可。 程序运行结果比文献[1]的Fig.1要好，原因不详。 本程序运行结果： 文献[1]中的Fig.1： 5、信号稀疏度K与重构成功概率关系曲线绘制例程代码 [plain]view plaincopy 1.%压缩感知重构算法测试CS_Reconstuction_KtoPercentage.m 2.% 绘制参考文献中的Fig.2 3.% 参考文献：Joel A. Tropp and Anna C. Gilbert 4.% Signal Recovery From Random Measurements Via Orthogonal Matching 5.% Pursuit，IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 53, NO. 12, 6.% DECEMBER 200 7. 7.% Elapsed time is 1448.966882 seconds.(@20150418night) 8.clear all;close all;clc; 9.%% 参数配置初始化 https://www.doczj.com/doc/c712843805.html,T = 1000;%对于每组(K,M,N)，重复迭代次数 11.N = 256;%信号x的长度 12.Psi = eye(N);%x本身是稀疏的，定义稀疏矩阵为单位阵x=Psi*theta 13.M_set = [52,100,148,196,244];%测量值集合 14.Percentage = zeros(length(M_set),N);%存储恢复成功概率 15.%% 主循环，遍历每组(K,M,N) 16.tic 17.for mm = 1:length(M_set) 18. M = M_set(mm);%本次测量值个数 19. K_set = 1:5:ceil(M/2);%信号x的稀疏度K没必要全部遍历，每隔5测试一个就可以了 20. PercentageM = zeros(1,length(K_set));%存储此测量值M下不同K的恢复成功概率 21. for kk = 1:length(K_set) 22. K = K_set(kk);%本次信号x的稀疏度K 23. P = 0; 24. for cnt = 1:CNT %每个观测值个数均运行CNT次 25. Index_K = randperm(N); 26. x = zeros(N,1); 27. x(Index_K(1:K)) = 5*randn(K,1);%x为K稀疏的，且位置是随机的 28. Phi = randn(M,N);%测量矩阵为高斯矩阵 29. A = Phi * Psi;%传感矩阵 30. y = Phi * x;%得到观测向量y 31. theta = CS_OMP(y,A,K);%恢复重构信号theta 32. x_r = Psi * theta;% x=Psi * theta 33. if norm(x_r-x)<1e-6%如果残差小于1e-6则认为恢复成功 34. P = P + 1; 35. end 36. end 37. PercentageM(kk) = P/CNT*100;%计算恢复概率 38. end 39. Percentage(mm,1:length(K_set)) = PercentageM; 40.end 41.toc 42.save KtoPercentage1000test %运行一次不容易，把变量全部存储下来 43.%% 绘图 44.S = ['-ks';'-ko';'-kd';'-kv';'-k*']; 45.figure; 46.for mm = 1:length(M_set) 47. M = M_set(mm); 48. K_set = 1:5:ceil(M/2); 49. L_Kset = length(K_set); 50. plot(K_set,Percentage(mm,1:L_Kset),S(mm,:));%绘出x的恢复信号 51. hold on; 52.end 53.hold off; 54.xlim([0 125]); 55.legend('M=52','M=100','M=148','M=196','M=244'); 56.xlabel('Sparsity level(K)'); 57.ylabel('Percentage recovered'); 58.title('Percentage of input signals recovered correctly(N=256)(Gaussian)'); 本程序在联想ThinkPadE430C笔记本（4GB DDR3内存，i5-3210）上运行共耗时1448.966882秒，程序中将所有数据均通过“save KtoPercentage1000”存储了下来，以后可以再对数据进行分析，只需“load KtoPercentage1000”即可。 程序运行结果比文献[1]的Fig.2要好，原因不详。 本程序运行结果： 贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 第10卷 第5期 信 息 与 电 子 工 程 Vo1．10，No．5 2012年10月 INFORMATION AND ELECTRONIC ENGINEERING Oct．，2012 文章编号：1672-2892(2012)05-0579-05 一种改进的用于稀疏表示的正交匹配追踪算法 王燕霞，张 弓 (南京航空航天大学 电子信息工程学院，江苏 南京 210016) 摘 要：稀疏表示理论在军事目标识别、雷达目标参数估计等领域应用越来越广，而目标信号的稀疏表示通常不唯一，因此产生了大量的稀疏表示算法。本文基于现有稀疏表示算法的研究，提出一种改进的正交匹配追踪(OMP)算法。首先采用非线性下降的阈值更快速地选择原子，确定备选原子集，提高了算法速度；其次用正则化的二次筛选剔除备选原子集中能量较低的原子，保证了算法精确度；并设置迭代停止条件实现算法的稀疏度自适应。实验结果表明，本文算法可以实现稀疏表示求解精确度和速度上的平衡，求解速度比基追踪(BP)算法快，精确度比OMP 、正则化OMP(ROMP)、基于自适应OMP 回溯(BAOMP)算法高。 关键词：过完备字典；稀疏表示；正交匹配追踪；正则化 中图分类号：TN850.6；TP753 文献标识码：A An improved orthogonal matching pursuit algorithm for sparse representation WANG Yan -xia，ZHANG Gong (College of Electronics and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 210016，China) Abstract：Usually sparse representation of signal is not unique, which results in a large number of sparse representation algorithms. An improved Orthogonal Matching Pursuit(OMP) algorithm is proposed. The atoms are selected more quickly with nonlinear decline threshold and the set of alternative atoms is determined, which improves the algorithm speed. Regularized secondary screening can remove lower -energy atoms from the alternative atoms set to ensure the accuracy. A stop condition for iteration is preset to realize the adaptive sparsity of new algorithm. Simulation results show that, the improved algorithm can keep a balance between accuracy and speed for sparse solving with a faster speed than Basis Pursuit(BP) algorithm and a higher accuracy than OMP, Regularized OMP(ROMP) and Backtracking -based Adaptive OMP(BAOMP) algorithms. Key words：over -complete dictionary；sparse representation；orthogonal matching pursuit；regularized 稀疏表示理论在军事目标识别[1]、雷达目标参数估计[2]等领域的应用越来越广，2010年Vishal 和Nasser 等人基于科曼奇族前视红外数据库将稀疏表示用于军事目标的识别，稀疏求解的结果表明算法取得了较好的识别效果[1]。对于稀疏表示理论应用于各种目标信号处理来说，信号的表示应该能对自身不同性质，以及各性质间的差异提供明确信息，这就促进了信号在基于大量波形的过完备字典上的分解[1]。然而过完备库中的波形数远远超过信号的维数，因此它对给定信号的表示不是唯一的，由此产生了信号处理工作中大量的稀疏表示算法。 基于过完备字典的稀疏表示起源于20世纪90年代，Mallat 和Zhang 首次提出了匹配追踪(Matching Pursuit ，MP)算法来解决该稀疏分解问题[3?4]，通常这些算法可以分为3类：基于p l 范数正则化的方法、迭代收缩算法和贪婪追踪算法。基于p l 范数正则化的方法通过求解在重构条件下系数的p l 范数最小化来寻找稀疏解，此类比较典型的算法有基追踪(BP)[5]；迭代收缩算法首先要获得系数的初始集，然后迭代修正获得稀疏表示，早期的这类方法有噪声整形(Noise Shaping ，NS)[6]等；贪婪追踪算法力求从字典中选取与余量最匹配的原子作为信号的近似表示，并通过减去与该原子相关的分量来更新余量，此类算法研究的成果较多，典型的有MP [5],OMP [7],ROMP [8]及BAOMP [9]等。 收稿日期：2011-12-14；修回日期：2012-02-09 压缩感知重构算法之分段正交匹配追踪(StOMP) 分段正交匹配追踪(StagewiseOMP)或者翻译为逐步正交匹配追踪，它是OMP另一种改进算法，每次迭代可以选择多个原子。此算法的输入参数中没有信号稀疏度K，因此相比于ROMP及CoSaMP有独到的优势。 0、符号说明如下： 压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< 2、分段正交匹配追踪(StOMP)Matlab代码(CS_StOMP.m) 代码参考了文献[4]中的SolveStOMP.m，也可参考文献[5]中的StOMP.m。其实文献[4]是斯坦福的SparseLab 中的一个函数而已，链接为https://www.doczj.com/doc/c712843805.html,/，最新版本为2.1，SolveStOMP.m在目录 SparseLab21-Core\SparseLab2.1-Core\Solvers里面。 1.function[theta]=CS_StOMP(y,A,S,ts) 2.%CS_StOMP Summary ofthisfunctiongoes here 3.%Version:1.0 writtenbyjbb0523@2015-04-29 4.%Detailedexplanationgoeshere 5.%y =Phi*x 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 压缩感知重构算法之正则化正交匹配追踪(ROMP) 正交匹配追踪算法每次迭代均只选择与残差最相关的一列，自然人们会想：“每次迭代是否可以多选几列呢?”，正则化正交匹配追踪(RegularizedOMP)就是其中一种改进方法。本篇将在上一篇《压缩感知重构算法之正交匹配追踪(OMP)》的基础上给出正则化正交匹配追踪(ROMP)算法的MATLAB函数代码，并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码。 0、符号说明如下： 压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< 我将原子选择过程封装成了一个MATLAB函数，代码如下(Regularize.m)： 1.function [val,pos] = Regularize(product,Kin) 2.%Regularize Summary of this function goes here 3.% Detailed explanation goes here 4.% product = A'*r_n;%传感矩阵A各列与残差的内积 5.% K为稀疏度 6.% pos为选出的各列序号 7.% val为选出的各列与残差的内积值 8.% Reference:Needell D，Vershynin R. Uniform uncertainty principle and 9.% signal recovery via regularized orthogonal matching pursuit. 10.% Foundations of Computational Mathematics, 2009,9(3): 317-334. 11. productabs = abs(product);%取绝对值 12. [productdes,indexproductdes] = sort(productabs,'descend');%降序排列 13. for ii = length(productdes):-1:1 14. if productdes(ii)>1e-6%判断productdes中非零值个数 15. break; 16. end 17. end 18. %Identify:Choose a set J of the K biggest coordinates 19. if ii>=Kin 20. J = indexproductdes(1:Kin);%集合J 21. Jval = productdes(1:Kin);%集合J对应的序列值 22. K = Kin; 23. else%or all of its nonzero coordinates,whichever is smaller 24. J = indexproductdes(1:ii);%集合J 25. Jval = productdes(1:ii);%集合J对应的序列值 26. K = ii; 27. end 28. %Regularize:Among all subsets J0∈J with comparable coordinates 29. MaxE = -1;%循环过程中存储最大能量值 30. for kk = 1:K 31. J0_tmp = zeros(1,K);iJ0 = 1; 32. J0_tmp(iJ0) = J(kk);%以J(kk)为本次寻找J0的基准(最大值) 33. Energy = Jval(kk)^2;%本次寻找J0的能量 34. for mm = kk+1:K 35. if Jval(kk)<2*Jval(mm)%找到符合|u(i)|<=2|u(j)|的 36. iJ0 = iJ0 + 1;%J0自变量增1 37. J0_tmp(iJ0) = J(mm);%更新J0 38. Energy = Energy + Jval(mm)^2;%更新能量 39. else%不符合|u(i)|<=2|u(j)|的 40. break;%跳出本轮寻找，因为后面更小的值也不会符合要求 41. end 42. end 43. if Energy>MaxE%本次所得J0的能量大于前一组 44. J0 = J0_tmp(1:iJ0);%更新J0 45. MaxE = Energy;%更新MaxE，为下次循环做准备 46. end 47. end 48. pos = J0; 49. val = productabs(J0); 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 压缩感知重构算法之正交匹配追踪(OMP) 前面经过几篇的基础铺垫，本篇给出正交匹配追踪(OMP)算法的MATLAB函数代码，并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码、信号稀疏度K与重构成功概率关系曲线绘制例程代码。 0、符号说明如下： 压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< 2、正交匹配追踪(OMP)MATLAB代码(CS_OMP.m) [plain]view plaincopy 1.function [ theta ] = CS_OMP( y,A,t ) 2.%CS_OMP Summary of this function goes here 3.%Version: 1.0 written by jbb0523 @2015-04-18 4.% Detailed explanation goes here 5.% y = Phi * x 6.% x = Psi * theta 7.% y = Phi*Psi * theta 8.% 令 A = Phi*Psi, 则y=A*theta 9.% 现在已知y和A，求theta 10. [y_rows,y_columns] = size(y); 11. if y_rows 答：贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。其有以下特性： ⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 ⑵ 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 ⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 ⑷ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。 ⑸ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 ⑹ 最后，目标函数给出解的值。 贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0 1. 信号的稀疏表示(sparse representation of signals) 给定一个过完备字典矩阵，其中它的每列表示一种原型信号的原子。给定一个信号y，它可以被表示成这些原子的稀疏线性组合。信号y 可以被表达为y = Dx ，或者 。字典矩阵中所谓过完备性，指的是原子的个数远远大于信号y的长度(其长度很显然是n)，即n< 实验报告 课程算法设计与分析实验实验名称贪心算法设计与应用第 1 页一、实验目的 理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用； 二、实验内容 (一)Huffman编码和译码问题： 1．问题描述 给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现： 1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频 率，建立相应的Huffman树，求出S中各个字符的Huffman编码。 2.输入一个由S中的字符组成的序列L，求L的Huffman 编码。 3. 输入一个二进制位串B，对B进行Huffman译码，输出对应的字符序列； 若不能译码，则输出无解信息。 提示：对应10 个字符的Huffman树的节点个数<211。 2．测试数据 Input n=5 字符集合S={a, b, c, d, e}, 对应的频率分别为 a: 20 b: 7 c: 10 d: 4 e: 18 字符序列L=ebcca 二进制位串B=01100111010010 Output S中各个字符的Huffman编码：（设Huffman树中左孩子的权<=右孩子的权）a: 11 b: 010 c: 00 d: 011 e: 10 L的Huffman 编码：10010000011 B对应的字符序列： dcaeeb 若输入的B=01111101001，则无解 (二) 加油问题（Problem Set 1702）： 1.问题描述 一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个 城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0 贪心算法浅析 摘要：本文讲述了贪心算法的基本思路及实现过程，贪心算法的特点、存在的问题以及应用。并通过贪心算法的特点举例列出了几个经典问题，通过对问题的探讨和研究，对贪心算法有了更加深入的了解。 关键词：贪心算法；最优解；最优子结构问题；删数问题；活动安排问题 贪心算法的基本思路及实现过程 1贪心的基本思想 用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。 利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解； （2）如何选择贪心标准，以得到问题的最优/较优解。 2贪心算法的实现过程 （1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题； （2）从问题的某一初始解出发： While（能朝给定目标前进一步） 求出可行解的一个解元素； （3）由所有解元素组合成问题的一个可行解。 贪心算法的特点 贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点： （1）如何贪心 怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。 具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。 （2）贪心的正确性 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。 贪心算法存在的问题 （1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑； （2）贪心算法只能用来求某些最大或最小解的问题； （3）贪心算法只能确定某些问题的可行性范围 贪心算法的应用 1哈夫曼编码 2 0-1背包问题 3磁盘文件的存储 4生产调度问题 5信息查询 贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心法是指从问题的初始状态出发，通过若干次的贪心选择而得出最优解或较优解的一种阶梯方法。事实上，从贪心算法“贪心”一词便可以看出，贪心法总是做出在当前看来是最优的选择，也就是说贪心法不是从整体上加以考虑他所做出的选择只是在某种意义上的局部最优解，而血多问题自身的特性决定了该题可以用贪心算法就能得到最优解。 贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 【问题举例】 11-1-1 购买新年贺卡 问题描述： 新年快到了，笑笑打算给他的好友们发新年贺卡，而且他已经选好了子要购买的样式。俗话说得好，货比三家，笑笑来到了商店，看了各个商铺同一种贺卡的价钱。不仅如此，笑笑还记住了每个商铺的存货量。已知笑笑打算购买m 张贺卡，问他最少花多少钱。 输入格式： 第一行有两个整数m和n。其中m表示要购买的贺年卡的数量，n表示商铺的个数。以下n行，每行有两个整数，分别表示该商铺这种贺年卡的单价和存货量。 输出格式： 进一个数，表示笑笑所化的最少的钱数。 输入样例： 10 4 4 3 6 2 8 10 3 6 输出样例： 36 数据规模： 0 贪心算法的实际应用 姓名： 班级： 学号： 指导老师： 定义： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 贪心算法经典例题 在求解最优问题的过程中，依据某种贪心策略，从问题的初始状态出发，求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 【例1】均分纸牌（全国信息学奥林匹克分区联赛（NOIP）2002提高组（TG））。[问题描述]：有N堆纸牌，编号分别为1，2，…, N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N 的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4堆纸牌数分别为： ①9②8 ③17 ④6 移动3次可达到目的： 从③取4张牌放到④（9，8，13，10）→从③取3张牌放到②（9，11，10，10）→从②取1张牌放到①（10，10，10，10）。 [输入]：键盘输入文件名。 N（纸牌堆数，1<=N<=100） A1 A2 … AN（每堆初始纸牌张数，l<=Ai<=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。[输入输出样例]： a.in 4 9 8 17 6 屏幕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 这里用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0贪心算法经典例题
一种改进的用于稀疏表示的正交匹配追踪算法
分段正交匹配追踪算法StOMP
【精选】贪心算法的应用
贪心算法详解分析
贪婪算法中ROMP算法的原理介绍及MATLAB仿真
贪心算法的应用
贪婪算法中正交匹配追踪算法OMP的原理及仿真
贪婪算法
贪心算法的应用实例
mp&omp 匹配追踪 正交匹配追踪
贪心算法设计与应用
贪心算法浅析
贪心算法
贪心算法的实际应用
贪心算法经典例题
相关主题
文本预览