第一篇：VJ壓縮算法總結(jié)
VJ壓縮算法總結(jié)
算法介紹
VJ壓縮算法是一種適用于串行鏈路的TCP/IP頭壓縮算法，對小包有較高的壓縮率，可以有效提高串行鏈路的鏈路利用率，并有效提高交互式應(yīng)用的響應(yīng)速度
算法概述
在一個(gè)TCP/IP連接活動期間，在連接上發(fā)送的TCP/IP包的包頭有大部分信息是保持不變的，這部分信息可以被壓縮掉。如果發(fā)送方把這部分被壓縮掉的信息用一個(gè)連接ID來替代，接收方保存上一次收到的TCP/IP包頭，則接收方就可以根據(jù)存儲的信息恢復(fù)被壓縮掉的數(shù)據(jù)，鏈路上的TCP/IP頭壓縮就得以實(shí)現(xiàn)。
算法原理
1.壓縮
發(fā)送方通過串行鏈路驅(qū)動來發(fā)送IP數(shù)據(jù)報(bào)，IP數(shù)據(jù)報(bào)經(jīng)過壓縮器，壓縮器檢查這個(gè)IP數(shù)據(jù)報(bào)是否封裝了一個(gè)TCP報(bào)文段，如果不是就把它標(biāo)記為TYPE_IP，并封裝后發(fā)送；否則就在本地存儲的一個(gè)包頭數(shù)組中搜索該TCP報(bào)文段對應(yīng)的連接，如果找到，就壓縮這個(gè)IP數(shù)據(jù)報(bào)，把包頭拷貝到查找到的槽位，標(biāo)記這個(gè)包為COMPRESSED_TCP并成幀后發(fā)送；如果未找到對應(yīng)的連接，就把數(shù)組中最舊的條目刪除，并復(fù)制TCP/IP頭到這個(gè)槽位，同時(shí)標(biāo)記這個(gè)包為UNCOMPRESSED_TCP，并發(fā)送到對端。UNCOMPRESSED_TCP標(biāo)記的包沒有被壓縮，它和正常的IP數(shù)據(jù)報(bào)的唯一區(qū)別是其“協(xié)議”字段被連接ID替代。連接ID是該TCP/IP數(shù)據(jù)報(bào)頭在包頭數(shù)組中的位置索引。這也是發(fā)送法用來同步接受方的方法。接受方收到這個(gè)報(bào)文后把它按照連接ID存放在數(shù)組中，用以解壓后續(xù)的壓縮數(shù)據(jù)包。
2.解壓縮
解壓縮器根據(jù)收到的不同類型的包做不同的轉(zhuǎn)換：
1）對TYPE_IP類型的包，簡單地把它提交給上層協(xié)議(IP層)2）對UNCOMPRESSED_TCP類型的包，從IP頭的協(xié)議類型字段提取出連接ID，并把該字段恢復(fù)成IPPROTO_TCP，連接ID被用于在本地?cái)?shù)組中存儲恢復(fù)后的TCP/IP頭，連接ID即是該報(bào)文頭在數(shù)組中的索引。
3）對COMPRESSED_TCP類型的包，用包頭的連接ID定位到保存的包頭，根據(jù)存儲的包頭恢復(fù)壓縮的數(shù)據(jù)包頭，并用恢復(fù)后的包頭更新存儲的包頭。壓縮/解壓縮的流程如圖1所示
圖1 SLIP VJ壓縮/解壓縮算法實(shí)現(xiàn)
3.壓縮包的格式
被壓縮過的TCP/IP報(bào)文頭部如圖2所示：
圖2 壓縮后的TCP/IP報(bào)頭
Byte 0 是一個(gè)報(bào)頭變化掩碼，用以指示這個(gè)報(bào)頭相對與上一個(gè)報(bào)頭變化的字段，Byte 1是連接標(biāo)識號，接收方可用它來定位這個(gè)連接上一個(gè)被存儲的報(bào)頭。Byte 2 – 3是TCP的校驗(yàn)和，接下來就是變化掩碼所指定的變化的字段。Delta標(biāo)示發(fā)送的是差值。由于一個(gè)連接可能持續(xù)較長時(shí)間，而在這段時(shí)間內(nèi)，連接標(biāo)識符是不變的，也可以被壓縮掉，C標(biāo)志位被清除的時(shí)候表示連接標(biāo)識符不變。
算法參考實(shí)現(xiàn)
1.壓縮器
壓縮器對輸入的IP包做如下檢驗(yàn)：
1)如果四層協(xié)議不是TCP，把它標(biāo)記為TYPE_IP并發(fā)送 2)如果分組是IP分片，不做壓縮，標(biāo)記為TYPE_IP并發(fā)送
3)如果TCP的SYN, FIN, 或是RST標(biāo)志被設(shè)置或是ACK標(biāo)志沒有設(shè)置，則認(rèn)為該TCP段不可壓縮，標(biāo)記為TYPE_IP并發(fā)送
4)通過前3個(gè)檢查的包將以UNCOMPRESSED_TCP或COMPRESSED_TCP的形式發(fā)送
5)如果沒有找到對應(yīng)該報(bào)文的連接，則老化一個(gè)連接(使用LRU算法)，并存儲該報(bào)文頭，把改報(bào)文的協(xié)議類型字段替換為連接號，把它作為UNCOMPRESSED_TCP類型的報(bào)文發(fā)送
6)如果找到了對應(yīng)該報(bào)文的連接，則把存儲的包頭和當(dāng)前包頭做比較，如果protocol version, header length, type of service, don’t fragment, time-to-live, data offset, IP options和TCP options字段有變化，則發(fā)送一個(gè)UNCOMPRESSED_TCP類型的報(bào)文 7)如果第6步中列舉的字段都沒有變化，則壓縮該TCP/IP報(bào)頭。
a)如果URG標(biāo)志被設(shè)置，則把緊急指針字段拷入壓縮后的報(bào)文頭，并設(shè)置變化掩碼的U位。如果URG標(biāo)志未設(shè)置，則比較當(dāng)前報(bào)文頭和保存報(bào)文頭的緊急指針字段，如果有變化，則不壓縮當(dāng)前報(bào)文，把它作為UNCOMPRESSED_TCP處理。
b)計(jì)算當(dāng)前報(bào)文頭和存儲報(bào)文頭窗口字段的差值，如果不為0，在壓縮報(bào)文中存儲該差值，并設(shè)置change mask的W位
c)計(jì)算TCP確認(rèn)序列號字段的差值，如果結(jié)果小于0或是大于2-1，則不壓縮報(bào)文，把它作為UNCOMPRESSED_TCP處理，否則，如果結(jié)構(gòu)非0，在壓縮報(bào)頭中記錄該差值并設(shè)置change mask的A位
d)計(jì)算TCP序號之間的差值，如果結(jié)果小于0或是大于2-1，則不壓縮報(bào)文，把它作為UNCOMPRESSED_TCP處理，否則，如果結(jié)構(gòu)非0，在壓縮報(bào)頭中記錄該差值并設(shè)置change mask的S位
e)U, A, S, W位計(jì)算完之后開始檢查特殊情況：
? 如果U, S和W位都被設(shè)置，則不執(zhí)行壓縮，發(fā)送一個(gè)UNCOMPRESSED_TCP的包。
? 如果只有S位被設(shè)置，檢查序號的改變值是否等于上一個(gè)分組中的用戶數(shù)據(jù)長度，如果相等，修改change mask 為SAWU，并丟棄壓縮報(bào)文中的序號變化值 ? 如果只有S和A被設(shè)置，檢查它們的變化量是否相等，并等于上一個(gè)分組的用戶數(shù)據(jù)長度，如果相等，設(shè)這change mask為SWU，并丟棄已計(jì)算出的序號和確認(rèn)序號改變值。
? 如果報(bào)頭沒有任何改變，查看該分組是否有用戶數(shù)據(jù)(在這種情況下，這個(gè)TCP段可能是一個(gè)重復(fù)的ACK或是窗口探針)或者前一個(gè)分組包含用戶數(shù)據(jù)(在這種
1616情況下這個(gè)分組是一個(gè)重傳的分組)，如果這兩種情況中的任何一種出現(xiàn)，發(fā)送一個(gè)UNCOMPRESSED_TCP類型的分組。
f)計(jì)算packet ID字段的差值，如果不是1，設(shè)置change mask的I位，并保存差值 g)如果PUSH標(biāo)志被設(shè)置，則設(shè)置change mask的P位 h)把當(dāng)前的TCP/IP報(bào)頭拷貝到報(bào)頭數(shù)組中 i)在原始報(bào)文中用壓縮后的報(bào)頭替換原始報(bào)頭 j)壓縮后的報(bào)文傳給下層傳輸
2.解縮壓器
解壓縮器工作在接收端，它根據(jù)壓縮器的指示處理壓縮報(bào)頭。解壓縮器可能收到4種報(bào)文：壓縮器產(chǎn)生的3種報(bào)文以及由接收器在檢測到幀錯(cuò)誤時(shí)產(chǎn)生的TYPE_ERROR偽報(bào)文。解壓縮器根據(jù)報(bào)文的不同類型做不同的處理：
如果是TYPE_ERROR或是未知類型的報(bào)文，設(shè)置狀態(tài)中的一個(gè)toss標(biāo)志以丟棄所有COMPRESSED_TCP類型的報(bào)文，直到設(shè)置C標(biāo)志的COMPRESSED_TCP類型的報(bào)文到達(dá)或是UNCOMPRESSED_TCP類型的報(bào)文到達(dá)。此時(shí)不返回任何報(bào)文
如果是TYPE_IP類型的報(bào)文，不做任何處理，直接返回。
如果是UNCOMPRESSED_TCP類型的報(bào)文，檢查IP PROTOCOL的連接號字段，如果非法，則設(shè)置toss標(biāo)志，并停止處理；否則清除toss標(biāo)志，拷貝TCP/IP頭到該字段指定的位置，并記錄這個(gè)連接，恢復(fù)IP PROTOCOL字段為TCP(6)并返回這個(gè)報(bào)文。
如果是COMPRESSED_TCP類型的報(bào)文，做如下處理：
? 如果change mask 的C位被設(shè)置，則檢查壓縮報(bào)頭中的connection number字段，如果非法，設(shè)置toss標(biāo)志并停止處理，否則記錄這個(gè)連接，并清除toss標(biāo)志 ? 如果change mask 的C標(biāo)志沒有設(shè)置，并且toss被置位，丟棄該分組。? 把壓縮報(bào)頭的TCP校驗(yàn)和拷貝到存儲報(bào)頭中。
? 如果change mask的P標(biāo)志被置位，則設(shè)置存儲報(bào)頭的PUSH標(biāo)志
? 如果change mask的S, A, W, U位都被設(shè)置，計(jì)算上一個(gè)分組用戶數(shù)據(jù)的長度(用存儲報(bào)頭的total length字段減去TCP和IP頭的長度)，并加上存儲報(bào)頭的TCP序號字段作為新的TCP序號。
? 如果S, W, U位被設(shè)置，而A沒有設(shè)置，則計(jì)算上一個(gè)TCP段中用戶數(shù)據(jù)的長度，并把它分別加上存儲報(bào)頭的TCP序號和ACK序號作為新的序號。? 否則按照壓縮器設(shè)置的順序來解釋change mask的各個(gè)字段
上述過程結(jié)束后，重新計(jì)算IP的total length（收到的用戶數(shù)據(jù)長度加上存儲的TCP/IP報(bào)頭長度）和IP頭校驗(yàn)和，至此完全解壓了壓縮的TCP/IP頭。
第二篇：基于壓縮感知理論的重構(gòu)算法介紹
壓縮感知重構(gòu)算法綜述
李珅
1,2，馬彩文，李艷，陳萍
111（1.中國科學(xué)院西安光學(xué)精密機(jī)械研究所 光電跟蹤與測量室,陜西省 西安市 710119;2.中國科學(xué)
院研究生院,北京 100039）
摘要：現(xiàn)代社會信息量的激增帶來了信號采樣、傳輸和存儲的巨大壓力，而近年來出現(xiàn)的壓縮感知理論(Compressed Sensing,CS)為解決該問題提供了契機(jī)。該理論指出：對于稀疏或可壓縮的信號，能夠以遠(yuǎn)低于奈奎斯特頻率對其進(jìn)行采樣，并通過設(shè)計(jì)重構(gòu)算法來精確的恢復(fù)該信號。本文介紹了壓縮感知理論的基本框架，綜述了壓縮感知理論的重構(gòu)算法，其中著重介紹了最優(yōu)化算法和貪婪算法并比較了各種算法之間的優(yōu)劣，最后探討了壓縮感知理論重構(gòu)算法未來的研究重點(diǎn)。
關(guān)鍵詞：信號采樣;壓縮感知;稀疏;重構(gòu)算法 中圖法分類號： TP301.6 文獻(xiàn)標(biāo)識碼：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 引言
隨著現(xiàn)代科技的飛速發(fā)展，人們對信息量的需求也在劇增。傳統(tǒng)的信息采樣是基于香農(nóng)采樣定理，它指出信號的采樣率不低于最高頻率的兩倍，信號才能被精確的重構(gòu)。該理論支配著幾乎所有信號的獲取、處理、存儲和傳輸。
一方面，在許多實(shí)際應(yīng)用中（如超寬帶通信，核磁共振，空間探測，高速AD轉(zhuǎn)換器等），信息在存儲和處理時(shí)，為達(dá)到采樣率而需要大量的采樣數(shù)據(jù)，從而導(dǎo)致采樣硬件成本昂貴，獲取效率低下甚至在某些情況難以實(shí)現(xiàn)。另一方面，在數(shù)據(jù)的存儲和傳輸方面，傳統(tǒng)的做法是先按照Nyquist方式獲取數(shù)據(jù)，然后將獲得的*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
數(shù)據(jù)進(jìn)行壓縮，最后將壓縮后的數(shù)據(jù)進(jìn)行存儲或傳輸。顯然，這樣的方式造成很大程度的資源浪費(fèi)，同時(shí)也提出了一個(gè)問題[1]：既然在壓縮中需要丟棄大多數(shù)數(shù)據(jù)，為什么不在采樣時(shí)直接取得我們需要的重要數(shù)據(jù)？ 近年來，D.Donoho、E.Candes及華裔科學(xué)家T.Tao等人提出了一種新的信息獲取理論－壓縮感知(Compressive Sensing)，以下簡稱為CS。該理論指出[1]：對于可壓縮的信號，可以通過低于或遠(yuǎn)低于奈奎斯特標(biāo)準(zhǔn)的方式對其進(jìn)行數(shù)據(jù)采樣并精確重構(gòu)該信號。與香農(nóng)定理不同的是，壓縮感知并不是直接測量信號本身，它使用非自適應(yīng)線性投影（感知矩陣）來獲得信號的整體構(gòu)造從而直接得到重要的信息，忽略那些在有損壓縮中會被丟棄的信息。一般來說，壓縮感知涉及三個(gè)比較重要的層面 [2]：
一、信號稀疏域的選取，是壓縮感知理論的基礎(chǔ)和前提。
二、觀測矩陣的選取，已經(jīng)證明大部分具有一致分布的隨機(jī)矩陣都可以作為觀測矩陣。
三、重構(gòu)算法的設(shè)計(jì)，由于壓縮感知采用的是全局非自適應(yīng)測量方法，觀測數(shù)量遠(yuǎn)遠(yuǎn)少于信號長度，從而數(shù)據(jù)采集量大大減少。但是需要付出的代價(jià)是信號重建算法的軟件成本。因此，CS重構(gòu)算法的好壞直接影響到CS理論是否實(shí)用。
其中S是投影系數(shù)si??,?i??iT?構(gòu)成的N×1維列向量。顯然，X和S是同一個(gè)信號的等價(jià)表示，其中X是在時(shí)域或空間域的表示，S是在Ψ域的表示。當(dāng)信號可以僅被K個(gè)基向量線性表示時(shí)，則稱信號x為K-稀疏。當(dāng)K<
sp?p????si??i?1/p?R(2)
傳統(tǒng)思路中壓縮信號就是采用這種正交變換的方式，其編碼解碼的策略為：編碼首先構(gòu)造正交基矩陣Ψ，作變換S??X,保留S中最重要的K個(gè)分量及其對應(yīng)的位置。解碼將K個(gè)分量放回到其對應(yīng)的位置，并將其他位置填0，以此構(gòu)造Ψ，最后進(jìn)行反變換???S求得重構(gòu)信號。
顯然，這種以Nyquist-Shanon采樣定理為準(zhǔn)則的編碼和解碼方法有很多缺點(diǎn)。
一、采樣后再進(jìn)行壓縮的方式浪費(fèi)了大量的采樣資源，如果采樣后的信號長度仍然很長，那么變換會消耗很長時(shí)間；
二、由于需要保留的K個(gè)重要分量的位置是隨著信號的不同而不同，所以這種編解碼方式是自適應(yīng)的，需要分配多余的存儲空間以保留K個(gè)重要分量的位置。
三、K個(gè)重要分量有可能在傳輸過程中丟失其中的某幾個(gè)分量從而造成較差的抗干擾能力。
近幾年出現(xiàn)的壓縮感知理論，對傳統(tǒng)的理念是一次革新，它表明我們可以用比傳統(tǒng)途徑少得多的采樣和測量來恢復(fù)信號。該理論主要依賴于兩個(gè)原則[4]，稀疏（sparsity）和不相關(guān)(incoher-ence)，稀疏關(guān)于感興趣的信號，它所表達(dá)的意思是：連續(xù)時(shí)間信號的信息率可能比根據(jù)其帶寬所建議的小得多，離散時(shí)間信號所依賴自由度的T 壓縮感知理論簡介
1.1基本思想 可壓縮（稀疏）的定義：考慮一個(gè)一維信號
Nx∈RN×1，都可以用N×1維基向量??i?i?1線性表示。為了簡化問題，假設(shè)基向量為規(guī)范正交向量，使用N×N的基矩陣????1|?2|...|?N?,信號x可以被表示為：
x??si?ii?1Nor???S可以說，許多自然界的(1)
數(shù)量比它的長度少得多。
信號在某種程度上都是稀疏的或可壓縮的，當(dāng)以*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
合適的基Ψ來表示時(shí)，信號可以有很多簡練的表達(dá)式。不相關(guān)表達(dá)了一種含義即以Ψ稀疏表示的信號一定可以在其所需要的域中展開?；谶@兩個(gè)原則，壓縮感知理論指出，長度為n的信號X在某組正交基或緊框架?n?n上的變換系數(shù)是稀疏的，如果我們可以用一個(gè)與變換基Ψ不相關(guān)的觀測基Ф（??Rm?n大多數(shù)隨機(jī)矩陣都滿足RIP，如高斯隨機(jī)測量系和伯努利隨機(jī)測量系。文獻(xiàn)[13]的工作告訴我們：在某種意義上說，選擇隨機(jī)測量對于稀疏矩陣來講是一種最佳策略，只需要幾乎最少的m個(gè)測量便可恢復(fù)稀疏度為S≤m/log(n/m)的信號，而且分析時(shí)所需要的常量都很小。第二類為非相關(guān)測量系，即測量矩陣和變換基Ψ是不相關(guān)的，其不相關(guān)性可以通過測量它們之間的相關(guān)系數(shù)，文獻(xiàn)[14]給出了測量矩陣Ф和變換基Ψ的相關(guān)系數(shù)μ = N1/2maxi,k|<Ψi, Фi>|，μ越小說明測量矩陣Ф和變換基Ψ的不相關(guān)性越大，測量所需要的數(shù)目也越少。
第三步：重構(gòu)信號x，區(qū)別于奈奎斯特理論的線性感知問題，由于觀測數(shù)量m遠(yuǎn)遠(yuǎn)小于信號長度n，重構(gòu)面臨著求解一個(gè)欠定方程組的問題。當(dāng)信號x是稀疏或可壓縮的，求解欠定方程組的問題可以轉(zhuǎn)化為最小0范數(shù)問題如式(4)：，m??n）對系數(shù)向量進(jìn)行線性變換，并得到觀測集合?m?1，則可以通過求解最優(yōu)化問題來精確地重構(gòu)信號X。
1.2 壓縮感知采樣過程
基于CS理論實(shí)現(xiàn)信號壓縮的采樣過程為： 第一步：找到某個(gè)基或緊框架Ψ，使得信號x在Ψ上是稀疏的，并求出變換系數(shù)：S ＝ ΨT X，其中S是X的等價(jià)或逼近的稀疏表示。變換基Ψ的選擇可以為某種已被廣泛應(yīng)用的基，如小波基、傅里葉基、局部傅里葉基等[5][6]，其中關(guān)于正交基的選擇，可以參考文獻(xiàn)[1]和文獻(xiàn)[7]。另外，可以使用緊框架（原子字典）來對信號進(jìn)行稀疏表示，如曲線波Curvelets[8]和輪廓波Contourlets[9]，這兩類變換基具有更好的方向性，并且各向異性，少量系數(shù)即可有效地捕捉圖像的邊緣輪廓，在邊緣表示方面優(yōu)于小波。第二步：需要設(shè)計(jì)一個(gè)平穩(wěn)的、與變換基Ψ不相關(guān)的m×n維觀測矩陣Ф，對S進(jìn)行觀測得到觀測集合Y=ФS＝ФΨTX，該過程也可以表示為信號x通過矩陣Acs進(jìn)行非自適應(yīng)觀測：Y=AcsX(其中Acs =ФΨT，稱為CS信息算子)。需要關(guān)注的問題是觀測矩陣Ф的選取，需要保證稀疏向量S從n維降到m維時(shí)重要信息不被破壞。在壓縮感知理論中，受限等距屬性（Restricted Isometry Property, RIP）N[10][11]
min?TX0s..tAcsX???TX?Y(4)
然而統(tǒng)計(jì)理論和組合優(yōu)化理論告訴我們，組合優(yōu)化是一個(gè)NP難問題，當(dāng)N很大時(shí)，數(shù)值上無法有效實(shí)現(xiàn)，且抗噪聲能力很差；Candes, Tao和Donoho等人已證明，當(dāng)測量矩陣?滿足約束等距性質(zhì)(Restricted Isometry Property, RIP)時(shí)，組合優(yōu)化問題(或稱，l0約束優(yōu)化問題)可轉(zhuǎn)化為數(shù)值上容易處理l1約束的凸優(yōu)化問題：
min?TX1s..tAcsX???TX?Y(5)
除此之外還有一些其它方法可以重構(gòu)信號,如:1）將l0范數(shù)松弛為lp范數(shù)；2）通過先驗(yàn)分布引入稀疏性，再用Bayesian方法實(shí)現(xiàn)信號稀疏重構(gòu)；3）使用啟發(fā)式算法(heuristic algorithms)，如借鑒圖模型和編碼理論中的belief-propagation和消息傳遞技術(shù)。
是判斷矩陣是否可以成為測量矩陣的一個(gè)重要的標(biāo)準(zhǔn)。對于k稀疏向量S∈R來說，當(dāng)它滿足式(3)時(shí)，測量矩陣Ф滿足RIP。
（1-?）s2??s2?（1??）s(3)壓縮感知理論對于測量系有兩個(gè)主要的分類：第一類為隨機(jī)測量系，文獻(xiàn)[10][12]已證明壓縮感知重構(gòu)算法研究
2.1 重構(gòu)算法介紹
*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
現(xiàn)階段CS重構(gòu)算法大致可以分為以下幾類。
第一類是貪婪迭代算法，針對組合優(yōu)化問題提出，該類算法主要是將信號與原子字典之間的聯(lián)系作為測量原子（系數(shù)）更加有效或非零的一種方式?；驹瓌t就是通過迭代的方式尋找稀疏向量的支撐集，并且使用受限支撐最小二乘估計(jì)來重構(gòu)信號。這類算法包括：匹配追蹤算法(MP ，matching pursuit）、正交匹配追蹤算法
[15]
比其他重構(gòu)算法更優(yōu)越的重構(gòu)精度。目前該類算法包括：新期望極大值(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是貝葉斯學(xué)習(xí)中很重要的一類算法，SBLMSBL算法與l1范數(shù)凸優(yōu)化算法不同的是，后者全局最小化通常并不是最稀疏解，而前者的全局最小值則是最稀疏的，并且全局最小值比一些典型的算法（如FOCUSS算法）更少。通過關(guān)注時(shí)間相關(guān)性對現(xiàn)有算法性能的影響，文獻(xiàn)[29]提出了AR(autoregressive)-SBL算法，該算法將每一個(gè)信號源的建模都作為一次一階自動回歸過程，同時(shí)對數(shù)據(jù)本身進(jìn)行學(xué)習(xí)得到AR系數(shù)。
(OMP，[16] orthogonal matching pursuit）、分段OMP算法(StOMP，stagewise orthogonal matching pursuit)、規(guī)范OMP算法[17](ROMP，Regularized Orthogonal Matching Pursuit)、CoSaMP算法[18](compressive sampling matching pursuit）、迭代硬閾值法
[19](iterative hard thresholding，IHT）以及GraDeS[20](gradient descent with sparsification)等。算法的復(fù)雜度大多是由找到正確支撐集所需要的迭代次數(shù)決定的，算法計(jì)算速度快但是需要的測量數(shù)據(jù)多且精度低。
第二類是凸優(yōu)化算法或最優(yōu)化逼近方法，這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的逼近，其中最常用的方法為基礎(chǔ)追蹤算法（BP，Basic Pursuit），該算法提出使用l1范數(shù)替代l0范數(shù)來解決最優(yōu)化問題，以便使用線性編程方法來執(zhí)行。另一種算法為FOCUSS算法[21]，該算法使用lp范數(shù)（p<=1）替代l0范數(shù)求解最優(yōu)化問題。另外，文獻(xiàn)[22]還提出了通過極小化l0范數(shù)的平滑轉(zhuǎn)換求解問題，稱之為SL0方法。該類算法計(jì)算速度慢(計(jì)算復(fù)雜性為N^3)，但需要的測量數(shù)據(jù)少(O(K*log(N/K))且精度高。另外兩種比較常見的凸松弛算法包括GPSR(Gradient Projection for Sparse Reconstruction)算法approximation)算法[24]
[23]
其他算法：這類方法有的要求信號的采樣支持通過分組快速測試重建，如傅立葉采樣，鏈?zhǔn)阶粉櫤虷HS(Heavg Hitters On Steroids)追蹤。有的將貪婪算法和最優(yōu)化算法相結(jié)合，如文獻(xiàn)[30]提出的貝葉斯追蹤算法(BPA)，算法將簡單的貪婪追蹤算法和最優(yōu)化貝葉斯框架相結(jié)合，在信號的稀疏表示中找到有效的原子。BPA可以看作是對迭代檢測估計(jì)(IDE,Iterative Detection Estima-tion)算法的修改。2.2 l1范數(shù)凸優(yōu)化算法
基于l1范數(shù)凸優(yōu)化算法的稀疏重構(gòu)模型主要有兩類[31]：
(LS?)miny??xxx2s..tx??1和
(BPminx1s..t?)y??x??2（6）
SpaRSA(sparse reconstruction by separable。GPSR算法通過使用梯度降的方法求解有界約束最優(yōu)化問題，算法要求投影在可行域中以確保迭代過程的可行性。第三類算法是基于貝葉斯框架提出的重構(gòu)算法，該類算法考慮到了信號的時(shí)間相關(guān)性，特別是當(dāng)信號具有較強(qiáng)的時(shí)間相關(guān)性時(shí)，能夠提供
其中，(LS?)式為LASSO(Least Absolute Shrinkage and Selection Operator)問題[32]，(BP?)式為基追蹤去噪(Basis Pursuit Denoise, BPDN)問題[33], 當(dāng)沒有噪聲時(shí)，就退化為單一的基追蹤(BP)問題[34]。處理實(shí)際問題時(shí)，通過對系統(tǒng)測量條件的分析，可以得到噪聲水平σ的大致估計(jì)。相比之下，要先驗(yàn)地估計(jì)原信號的l1范*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
數(shù)值τ是十分困難的，因此研究(BP?)問題的求解更具有實(shí)際意義，但是(LS?)問題可以作為求解(BP?)問題的中間手段。
求解形如(LS?)和(BP?)的約束優(yōu)化問題時(shí)，可將約束條件轉(zhuǎn)換為懲罰項(xiàng)，構(gòu)造非約束優(yōu)化問題。即：
2x冗余的。匹配追蹤的任務(wù)就是通過每一次匹配把待分析信號f(t)分解成庫中一組成員gi(t)(i=1,2,…,N)的線性組合，且N越小越好，實(shí)際就是通過對一系列單一原子進(jìn)行逼近的方法來逐步搜索信號的稀疏解。
匹配跟蹤算法雖然簡單，但由于它找到的是OMP是恢復(fù)稀疏信號算法中較早出現(xiàn)的一類算空間上克服了上述缺陷。
基于壓縮感知理論，OMP算法可以通過已知的關(guān)于信號的O(mlnd)個(gè)隨機(jī)線性測量來恢復(fù)d維空間中的信號。假設(shè)S是Rd 空間的k-稀疏信號，Ф為n×d維測量矩陣，列向量為φ1 到φd。數(shù)據(jù)向量v（v＝Фs）的列是從Ф中選取的某些列的組合。
算法的基本思想源于K-稀疏，是為了找到K個(gè)關(guān)鍵的分量，既然是關(guān)鍵，顯然它的絕對值應(yīng)該比其他（N－K）個(gè)分量大的多?；谏厦娴募僭O(shè)，算法就是要從測量矩陣Ф中找到參與信號x測量的列向量。方法是：設(shè)置一個(gè)剩余向量r和序號集合Λ，在每一次迭代中，從Ф中選出與數(shù)據(jù)v剩下部分即余量r最相關(guān)的那一列，將該列號添加到集合Λ中并從數(shù)據(jù)v中去掉該列所作的貢獻(xiàn)并重新計(jì)算余量，直到m次迭代結(jié)束。算法最終會得到正確的列序號集合Λ以及數(shù)據(jù)v的N維近似值am和N維余量rm。需要注意的是，迭代過程中余量rt始終和Фt 的列向量正交。具體的算法可以參考文獻(xiàn)[15]。
文獻(xiàn)[15]中Tropp和Gilbert分析了OMP算法執(zhí)行的性能，提出了合適的測量矩陣為N×d維隨機(jī)矩陣，且具有（M0）獨(dú)立性、（M1）歸一化、（M2）聯(lián)合相關(guān)性和（M3）最小奇異值四個(gè)性質(zhì)。文獻(xiàn)[36]也證明了當(dāng)測量矩陣Ф滿足RIP條件時(shí)（其中參數(shù)?k?1?1/(1?2K)）,OMP算法可通過K個(gè)步驟精確地恢復(fù)任意K-稀疏信號。同時(shí)該文對OMP算法進(jìn)行了改進(jìn)，提出了MOMP
逼近結(jié)果的稀疏度較差。(QP?)miny??x2??x(7)
次優(yōu)解，故算法收斂慢、事實(shí)上，（QP?）問題中的控制參數(shù)λ可視為求解約束優(yōu)化問題(LS?)和(BP?)中的拉格朗日乘數(shù)。因此，若參數(shù)σ、λ和τ選取合適，以上三個(gè)問題的解是一致的。其中（QP?）問題是一個(gè)二階錐規(guī)劃(second-order cone program)問題，可利用內(nèi)點(diǎn)法(interior-point)[9,35]求解。
文獻(xiàn)[11]比較了各種不同的恢復(fù)算法，總結(jié)出了l1凸優(yōu)化算法，如LASSO或BPDN[33,36]
法，通過把信號矢量投影到由選取原子張成的子，通過求解式（8）可以在稀疏計(jì)算的復(fù)雜度和精度之間提供最佳的平衡點(diǎn)。
minx12y??x2??x(8)2迭代閾值技術(shù)（iterative thresholding algorithm）在稀疏優(yōu)化算法中經(jīng)常被采用，一些迭代閾值算法被用在解決LASSO問題上，可以使迭代過程中每一次迭代的計(jì)算量減小，這樣就可以將LASSO用于解決高維方面的問題[8]。在迭代閾值技術(shù)中，迭代收縮算法解決
[20]凸優(yōu)化問題十分有效，包括IHT [19]、GraDeS、PCD(parallel coordinate descent)以及FISTA(fast-iterative-shrinkage thresholding algorithm)等。對于IHT和GraDes算法，由于該算法使用負(fù)梯度作為搜索方向，即Landweber迭代，所以造成算法執(zhí)行效率偏低。2.3 貪婪算法
MP算法最初是Mallat等人在1993年提出的匹配追蹤算法，基本原理就是首先建立一個(gè)來分析信號的基本庫函數(shù)D，不要求庫中所有基本函數(shù)gi(t)（也叫“原子”）相互正交，但要求其二范數(shù)||gi(t)||2=1。因此這組函數(shù)并非相互獨(dú)立，是有*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
（multi-candidate OMP）算法。該算法對OMP的改進(jìn)在于：在每一次的迭代中，OMP算法只選擇一個(gè)候選列加入到原子集合中，而MOMP算法選擇多個(gè)候選列加入到最優(yōu)原子集合，從而減少迭代的次數(shù)，降低重構(gòu)信號的計(jì)算復(fù)雜度。文獻(xiàn)[34]中，Rauhut研究了使用傅里葉矩陣作為測量矩陣的OMP算法的執(zhí)行性能，通過大量的試驗(yàn)，他們證明了通過O(Klog(n))個(gè)測量就可以精確的恢復(fù)K-稀疏信號。同時(shí)，Kunis和Rauhut提出，對于m-稀疏信號給出的O（mlnd）次測量，在第一次迭代中，OMP方法可以從測量矩陣中選出正確的列，但是由于矩陣列向量之間存在的微小隨機(jī)相關(guān)性，很難對OMP算法后續(xù)的迭代進(jìn)行分析。于是D.Needell 和 R.Vershynin就在文獻(xiàn)[17]中提出了對OMP算法的改進(jìn)，稱為ROMP算法（Regularized Orthogonal Matching Pursuit），該算法可以通過選擇替代信號的最大元素并采用正則化的方式來確保沒有太多的錯(cuò)誤元素被選擇，ROMP算法比OMP算法更快速且重構(gòu)結(jié)果更加均衡穩(wěn)定。文獻(xiàn)[37]中Nam H.Nguyen和Trac D.Tran使用ROMP方法從含噪測量中穩(wěn)定地重構(gòu)可壓縮信號。Donoho也在文獻(xiàn)[16]中提出了分段OMP算法(stagewise orthogonal matching pursuit)，該算法對OMP算法進(jìn)行了簡化，通過設(shè)置閾值的方法來找到替代的信號，同時(shí)以逼近精度為代價(jià)進(jìn)一步提高了計(jì)算速度，更適合求解大規(guī)模問題。除此之外，2005年Chinh和Minh提出了樹型正交匹配算法[38]（TOMP, Tree-based Orthogonal Matching Pursuit），該算法是通過構(gòu)造稀疏樹并在樹中追蹤重要的系數(shù)來實(shí)現(xiàn)的。TOMP算法考慮到了信號的多尺度分解時(shí)稀疏信號在各奇異子帶位置的關(guān)系，從而構(gòu)建了比BP和OMP算法更加快速且重構(gòu)精度更高的算法。
壓縮感知追蹤算法（CoSaMP,Compressed Sampling Matching Pursuit）是最近由Needell和Tropp提出的[18]，和大多數(shù)貪婪算法一樣，CoSaMP算法采用了正交測量矩陣Ф（Ф*TФ近似歸一化），因此算法中的替代信號p = Ф*TФS的最大元素與S的非零輸入相關(guān)聯(lián)。算法的執(zhí)行是將p的最大元素加入到運(yùn)行支撐集中，并使用最小二乘法來獲取信號的估計(jì)。最后，修正最小二乘估計(jì)并更新錯(cuò)誤余量。2.4 一些新想法
最近，很多學(xué)者提出了一些新想法，其中之一就是將消息傳遞用于解決壓縮感知的信號重構(gòu)問題。其中，Donoho等提出了一種算法稱之為AMP（approximate message passing）[39]，這種算法既具有迭代閾值算法的低復(fù)雜度，同時(shí)也具備基追蹤算法較強(qiáng)的信號重構(gòu)能力。事實(shí)上，AMP是將一些廣泛采用的算法集合成的一個(gè)實(shí)例，是一類新的低復(fù)雜度迭代閾值算法，用于解決從較少的線性測量中重構(gòu)稀疏信號的問題。
考慮式子：
y?AS0??，S0?RN,y,w?Rn
(9)
其中S0是稀疏向量，ω為噪聲。一般的AMP算法的迭代公式如下：
xt?1??0(xt?ATzt;?t)z?y?Ax?
ttItnzt?(10)
x和z的初始值為x0=0,z0=y，其中，?0(x;?)?(x???)sign(x)屬于軟閾值函數(shù)；It 是xt的有效集合。具體的迭代算法和一些相關(guān)算法可參見文獻(xiàn)[39-44]，這里就不再詳述。算法對比及特點(diǎn)評述
BP算法的優(yōu)勢在于它可以當(dāng)作線性編程問題來解決，因而可以使用標(biāo)準(zhǔn)的技術(shù)軟件來處理。但是在實(shí)際應(yīng)用中，對于稀疏信號的重構(gòu)，商業(yè)化的軟件并不能很好的工作，因?yàn)榻庀蛄渴窍∈璧?，而測量向量是稠密的，所以即使是常見的圖像尺寸，計(jì)算也相當(dāng)耗時(shí)且執(zhí)行復(fù)雜度很高。除此之外，由于l1范數(shù)無法區(qū)分稀疏尺度的位置，所以盡管整體上重構(gòu)信號在*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JM8021）作者簡介：李珅（1980—），女，河北樂亭人，在讀博士，主要從事壓縮感知和圖像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn
歐氏距離上逼近原信號，但存在低尺度能量搬移到高尺度的現(xiàn)象，從而容易出現(xiàn)一些人工效應(yīng)，如一維信號會在高頻出現(xiàn)振蕩。
貪婪算法是CS重構(gòu)算法中使用比較頻繁的一類算法（主要為OMP算法及其改進(jìn)算法），基本思想是根據(jù)殘差向量與測量矩陣之間相關(guān)性最大的分量，逐步找到原信號的支撐集，并在與信號支撐集相對應(yīng)的子矩陣上進(jìn)行類似于最小二乘的計(jì)算。該算法較凸優(yōu)化算法來說，大大提高了計(jì)算效率，同時(shí)在算法中可以加入額外的先驗(yàn)信息，提高了重構(gòu)信號的精度。如基于模型的壓縮感知方法[45](model based compressed sensing）和前面提到過的貝葉斯壓縮感知方法（BCS）。其中BCS算法借助傳統(tǒng)的貝葉斯方法與機(jī)器學(xué)習(xí)中的主動學(xué)習(xí)方法,將關(guān)于稀疏性的先驗(yàn)信息用垂直先驗(yàn)分布來建模，提出了自適應(yīng)的感知方法以及相應(yīng)的恢復(fù)方法。而基于模型的壓縮感知方法利用小波樹模型和塊稀疏模型，僅需要與稀疏程度相當(dāng)?shù)臏y量數(shù)目即可實(shí)現(xiàn)信號的魯棒性恢復(fù)[46]。
當(dāng)信號稀疏性不是很好且測量中噪聲較大時(shí)，貪婪算法效果沒有凸優(yōu)化算法好。同時(shí)，貪婪算法中涉及到的最小二乘過程要進(jìn)行矩陣求逆，需大量的矩陣-向量乘法，當(dāng)算子Φ存在快速算法時(shí)也難以應(yīng)用。近兩年，隨著梯度投影、迭代閾值等算法的出現(xiàn)，最小l1范數(shù)方法的計(jì)算效率大幅度提高，同時(shí)還可以充分利用算子Φ的快速算法。
CS重構(gòu)算法各有優(yōu)缺點(diǎn)，在設(shè)計(jì)算法時(shí)，應(yīng)根據(jù)所應(yīng)用的領(lǐng)域和信號的特點(diǎn)來進(jìn)行選擇。主要目的是配合CS測量矩陣盡可能減少測量數(shù)據(jù)并保證重構(gòu)信號的精度，同時(shí)根據(jù)需求進(jìn)行合理權(quán)衡。的對于信號重構(gòu)所采用的最小二乘優(yōu)化算法已經(jīng)不夠充分，采用不同方式的凸優(yōu)化算法和貪婪算法來重構(gòu)信號是壓縮感知研究的一個(gè)重點(diǎn)。本文對壓縮感知理論的框架做了一個(gè)簡單的描述，著重放在了對壓縮感知重構(gòu)算法的綜述上，主要介紹了一些常用的CS重構(gòu)算法如貪婪算法、凸優(yōu)化算法等，同時(shí)對各算法的特點(diǎn)進(jìn)行了評述。縱觀現(xiàn)在的壓縮算法，可以看出今后對于壓縮算法的改進(jìn)主要集中在三個(gè)方面：1）構(gòu)造更穩(wěn)定、計(jì)算復(fù)雜度低且需要較少的觀測次數(shù)的重構(gòu)算法來精確地恢復(fù)可壓縮信號；2）構(gòu)造有效的重構(gòu)算法來精確恢復(fù)含噪信號或在采樣過程中被引入噪聲的信號；3）將理論與實(shí)際相結(jié)合，根據(jù)特定的領(lǐng)域或應(yīng)用構(gòu)造具有針對性的有效可行的壓縮算法。參考文獻(xiàn)
[1] D L Donoho．Compressed sensing[J].IEEE Transactions on Information Theory.2006,52(4): 1289-1306.[2] 石光明,劉丹華,高大化.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào).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 結(jié)束語
對于稀疏信號或可壓縮信號來說，壓縮感知理論作為一種新的信號獲取方式，比傳統(tǒng)的采樣方式更加有效。在壓縮感知理論中，傳統(tǒng)*基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（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 *基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（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] 劉吉英.壓縮感知理論及在成像中的應(yīng)用[D].國防科技技術(shù)大學(xué)研究生院博士學(xué)位論文, 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://004km.cn
第三篇：算法總結(jié)
算法分析與設(shè)計(jì)總結(jié)報(bào)告
71110415 錢玉明
在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學(xué)生，學(xué)習(xí)算法無疑會增強(qiáng)自己的競爭力，修煉自己的“內(nèi)功”。
下面我將談?wù)勎覍@門課程的心得與體會。
一、數(shù)學(xué)是算法的基礎(chǔ)
經(jīng)過這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。
①主定理
本門課中它主要應(yīng)用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個(gè)大問題分解為a個(gè)子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級高于nlogba時(shí)，我們可以設(shè)法降低子問題組合時(shí)的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴(kuò)大問題的規(guī)?；蛘邷p小子問題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。
②隨機(jī)算法中的許多定理的運(yùn)用
在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯(cuò)率的計(jì)算，算法性能的評價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。
這些算法都給予了我很大啟發(fā)，要想學(xué)好算法，學(xué)好數(shù)學(xué)是必不可少的。沒有深厚的數(shù)學(xué)功力作為地基，即使再漂亮的算法框架，代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。
二、算法的核心是思想
我們學(xué)習(xí)這門課不是僅僅掌握那幾個(gè)經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個(gè)例子。有同學(xué)曾問我這樣一個(gè)問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個(gè)星期。現(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個(gè)瓶子的水，每個(gè)瓶子可以只喝一點(diǎn)。問如何解決？其實(shí)一開始我也一頭霧水，但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。
①算法最基本的設(shè)計(jì)方法包括分治法，動態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個(gè)元素中最大元和最小元的量級，降低n位二進(jìn)制x和y相乘的量級，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨(dú)立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。
動態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復(fù)的，后面的問題可以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時(shí)最小計(jì)算次數(shù)問題，尋找最長公共子序列等等。
貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。
周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。
回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時(shí)，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問題，平面點(diǎn)集的凸包問題和0-1背包問題。
分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。
②評價(jià)算法性能的方法如平攤分析中的聚集法，會計(jì)法和勢能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來。會計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去，以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢能法計(jì)算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。
這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學(xué)會去應(yīng)用，在具體的問題中去判斷分析。
三、算法與應(yīng)用緊密相關(guān)
我認(rèn)為學(xué)習(xí)算法不能局限于書本上的理論運(yùn)算，局限于如何提高性能以降低復(fù)雜度，我們要將它與實(shí)際生活聯(lián)系起來。其實(shí)算法問題的產(chǎn)生就來自于生活，設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長公共子序列算法可以應(yīng)用在生物信息學(xué)中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個(gè)字符串的相近性，這可應(yīng)用在數(shù)據(jù)挖掘中?？焖俑盗⑷~變換（FFT）可應(yīng)用在計(jì)算多項(xiàng)式相乘上來降低復(fù)雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對于解決網(wǎng)絡(luò)流量分配問題起了很大的幫助，等等。
這些應(yīng)用給了我很大的啟發(fā)：因?yàn)閱渭冎v一個(gè)Union-Find算法，即使了解了它的實(shí)現(xiàn)原理，遇到具體的實(shí)際問題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問題結(jié)合起來，不能停留在思想方法階段，要學(xué)以致用，做到具體問題具體分析。
四、對計(jì)算模型和NP問題的理解
由于對這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。
首先談到計(jì)算模型，就不得不提到圖靈計(jì)算，他將基本的計(jì)算抽象化，造出一個(gè)圖靈機(jī)，得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問題都是可以計(jì)算的，否則就是不可計(jì)算的。由此引申出一個(gè)著名論題：任何合理的計(jì)算模型都是相互等價(jià)的。它說明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。
NP問題比較復(fù)雜，我認(rèn)為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個(gè)特殊的性質(zhì)，如果存在一個(gè)NP-C問題找到一個(gè)多項(xiàng)式時(shí)間的解法，則所有的NP-C問題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時(shí)可以找出精確解，但是規(guī)模大時(shí)，就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法，如漢諾塔問題。
最后談?wù)剬@門課程的建議
①對于這門算法課，我認(rèn)為應(yīng)該加強(qiáng)對算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會兒，或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制，誰能解決這個(gè)問題，平時(shí)成績加分。這在一定程度上會將強(qiáng)我們思考分析問題的能力。因?yàn)槲腋杏X到，一個(gè)問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點(diǎn)名回答問題可以一定程度上有效的防止不認(rèn)真聽課的現(xiàn)象。
②作業(yè)安排的不是很恰當(dāng)。本門課主要安排了三次作業(yè)，個(gè)人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼，沒有太多的技術(shù)含量。而且對于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因?yàn)檫@間接成為了程序設(shè)計(jì)題，不是算法設(shè)計(jì)題。
③本門課的時(shí)間安排的不太恰當(dāng)，因?yàn)楸緦W(xué)期的課程太多，壓力太大。沒有太多的時(shí)間去學(xué)習(xí)這門課程。因?yàn)槲蚁嘈糯蠹叶紝λ信d趣，比較重視，想花功夫，但苦于沒時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期，那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過，且課程的壓力也不是很大。錯(cuò)開時(shí)間的話，我覺得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。
第四篇：算法總結(jié)
算法分塊總結(jié)
為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié)，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中，時(shí)刻都要牢記要減少冗余，要以簡潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問題時(shí)，要想方設(shè)法進(jìn)行模型簡化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。
圖論模型的應(yīng)用
分層圖思想的應(yīng)用：
用此思想可以建立起更簡潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型，進(jìn)而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復(fù)制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進(jìn)行新層的存儲，甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性，很多計(jì)算結(jié)果都是相同的。所以我們只需對這些計(jì)算進(jìn)行一次，把結(jié)果存起來，而不需要反復(fù)計(jì)算。如此看來，雖然看起來圖變大了，但實(shí)際上問題的規(guī)模并沒有變大。層之間是拓?fù)溆行虻摹＿@也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。
這些特點(diǎn)說明這個(gè)分層圖思想還是很有潛力的，尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn)，有可能大大消除冗余計(jì)算，進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用： ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用：
最大網(wǎng)絡(luò)流算法的應(yīng)用：典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用：
容量有上下界的最大流的應(yīng)用：
歐拉路以及歐拉回路的應(yīng)用：主要利用求歐拉路的套圈算法。最小生成樹：
求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E)，后者一般應(yīng)用于稀疏圖，其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹：
抽象成數(shù)學(xué)模型就是：
設(shè)G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問題有解時(shí)k 的最小值：把v0點(diǎn)從圖中刪去后，圖中可能會出 現(xiàn)m 個(gè)連通分量，而這m 個(gè)連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當(dāng)k 首先，將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去，此時(shí)的圖可能不再連通，對各個(gè)連通分量，分別求最小生成樹。接著，對于每個(gè)連通分量V’，求一點(diǎn)v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個(gè)m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉(zhuǎn)化成以v0為根的有根樹。 假設(shè)已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關(guān)聯(lián)的邊后，必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大，則所得到的生成樹的權(quán)值和就越小。動態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn)，動態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 狀態(tài)共|V|個(gè)，狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1)，所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹； 2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當(dāng)dT(v0)=k時(shí)停止。 加邊和去邊過程，利用動態(tài)規(guī)劃優(yōu)化特別值得注意。 次小生成樹： 加邊和去邊很值得注意。 每加入一條不在樹上的邊，總能形成一個(gè)環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權(quán)值越大，新得到的生成樹的權(quán)值和越小。具體做法： 首先做一步預(yù)處理，求出樹上每兩個(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預(yù)處理，我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢？因?yàn)檫@是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。 最短路徑的應(yīng)用： Dijkstra 算法應(yīng)用： Folyed 算法應(yīng)用： Bellman-Ford 算法的應(yīng)用： 差分約束系統(tǒng)的應(yīng)用： 搜索算法 搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn)，凡是能用高效算法的地方盡量爭取用高效算法?；镜倪f歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應(yīng)用： 枚舉思想的應(yīng)用： ZOJ 1252 island of logic A*算法的應(yīng)用： IDA*算法的應(yīng)用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，動態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索： 可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。 動態(tài)規(guī)劃 動態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預(yù)處理（以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。 狀態(tài)壓縮DP，又叫帶集合的動態(tài)規(guī)劃：題目特點(diǎn)是有一維的維數(shù)特別小。類似TSP問題的DP： 狀態(tài)劃分比較困難的題目： 樹形DP： 四邊形不等式的應(yīng)用探索：四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2) 高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 并查集的應(yīng)用： 巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應(yīng)用： 總結(jié)用線段樹解題的方法 根據(jù)題目要求將一個(gè)區(qū)間建成線段樹，一般的題目都需要對坐標(biāo)離散。建樹時(shí)，不要拘泥于線段樹這個(gè)名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線段、或數(shù)組中一個(gè)值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等 樹的每個(gè)節(jié)點(diǎn)根據(jù)題目所需，設(shè)置變量記錄要求的值 用樹形結(jié)構(gòu)來維護(hù)這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí)，都只對O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn)，在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。 在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運(yùn)用子樹的收縮與葉子節(jié)點(diǎn)的釋放，避免重復(fù)操作。 Trie的應(yīng)用：； Trie圖的應(yīng)用探索： 后綴數(shù)組的應(yīng)用研究： 在字符串處理當(dāng)中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關(guān)于后綴數(shù)組則很少見于國內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹的一個(gè)非常精巧的替代品，它比后綴樹容易編程實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。 樹狀數(shù)組的應(yīng)用探索：； 計(jì)算幾何 掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用：； 半平面交算法的應(yīng)用：； 幾何+模擬類題目：幾何設(shè)計(jì)好算法，模擬控制好精度。掃描法：； 轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用：； 經(jīng)典算法：找平面上的最近點(diǎn)對。 貪心 矩形切割 二分思想應(yīng)用 活用經(jīng)典算法 利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)： 利用快速排序算法思想，查詢N個(gè)數(shù)中的第K小數(shù)： 博弈問題 博弈類題目通常用三類解法：第一類推結(jié)論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應(yīng)用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。 第一類：推結(jié)論。典型題目： 第二類：遞推。典型題目： 比如有向無環(huán)圖類型的博弈。在一個(gè)有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應(yīng)該具有如下性質(zhì)： 1． 所有的結(jié)束位置都是P位置。 2． 對于每一個(gè)N位置，至少存在一種移動可以將棋子移動到一個(gè)P位置。3． 對于每一個(gè)P位置，它的每一種移動都會將棋子移到一個(gè)N位置。 這樣，獲勝的策略就是每次都把棋子移動到一個(gè)P位置，因?yàn)樵谝粋€(gè)P位置，你的對手只能將棋子移動到一個(gè)N位置，然后你總有一種方法再把棋子移動到一個(gè)P位置。一直這樣移動，最后你一定會將棋子移動到一個(gè)結(jié)束位置（結(jié)束位置是P位置），這時(shí)你的對手將無法在移動棋子，你便贏得了勝利。 與此同時(shí)，得到了這些性質(zhì)，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為： 1． 將所有的結(jié)束位置標(biāo)為P位置。 2． 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。 3． 找出所有只能到達(dá)N位置的點(diǎn)，將它們標(biāo)為P位置。 4． 如果在第三步中沒有找到新的被標(biāo)為P位置的點(diǎn)，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應(yīng)用。 關(guān)于SG函數(shù)的基本知識：對于一個(gè)有向圖(X, F)來說，SG函數(shù)g是一個(gè)在X上的函數(shù)，并且它返回一個(gè)非負(fù)整數(shù)值，具體定義為 g(x)?min{n?0,n?g(y)對于所有y?F(x)} 1． 對于所有的結(jié)束位置x，g(x)= 0。 2． 對于每一個(gè)g(x)≠ 0的位置x，在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。 3．對于每一個(gè)g(x)＝ 0的位置x，所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。 定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類：極大極小法。 典型題目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項(xiàng)）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目： 數(shù)學(xué)模型舉例 向量思想的應(yīng)用： UVA 10089：注意降維和向量的規(guī)范化 ； 利用復(fù)數(shù)思想進(jìn)行向量旋轉(zhuǎn)。 UVA 10253： 遞推 數(shù)代集合 數(shù)代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個(gè)數(shù)不會超過100，因此可以考慮用一個(gè)數(shù)代替一個(gè)集合，首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來，到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。 組合數(shù)學(xué) Polya定理則是解決同構(gòu)染色計(jì)數(shù)問題的有力工具。 補(bǔ)集轉(zhuǎn)化思想 ZOJ 單色三角形： 字符串相關(guān) 擴(kuò)展的KMP算法應(yīng)用：；最長回文串； 最長公共子串； 最長公共前綴； 填充問題 高精度運(yùn)算 三維空間問題專題 無論什么問題，一旦擴(kuò)展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實(shí)現(xiàn)能力。 其它問題的心得 解決一些判斷同構(gòu)問題的方法：同構(gòu)的關(guān)鍵在于一一對應(yīng)，而如果枚舉一一對應(yīng)的關(guān)系，時(shí)間復(fù)雜度相當(dāng)?shù)母?，利用最小表示，就能把一個(gè)事物的本質(zhì)表示出來。求最小表示時(shí)，我們一定要仔細(xì)分析，將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當(dāng)?shù)摹⒏咝У钠ヅ渌惴ǎɡ鏚MP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進(jìn)行推廣 源程序代碼： } 一、自然數(shù)拆分（遞歸） } #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); 三、刪數(shù)字（貪心） #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;} 五、多段圖（動態(tài)規(guī)劃）#include “stdio.h” #define n 12 //圖的頂點(diǎn)數(shù) { 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;//滿足條件就跳轉(zhuǎn) } } } 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 //圖的段數(shù) #define MAX 23767 int cost[n][n];//成本值數(shù)組 int path[k];//存儲最短路徑的數(shù)組 void creatgraph()//創(chuàng)建圖的(成本)鄰接矩陣 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//獲取成本矩陣數(shù)據(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;//起點(diǎn) path[k-1]=n-1;//最后的目標(biāo) for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//將最短路徑存入數(shù)組中 } //使用向后遞推算法求多段圖的最短路徑 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);} 矩陣鏈乘法（動態(tài)規(guī)劃）? 符號S[i, j]的意義： 符號S(i, j)表示，使得下列公式右邊取最小值的那個(gè)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的定義： 如果存在兩個(gè)正常數(shù)c和n0，對于所有的n≥n0時(shí)，有： |f(n)|≤c|g(n)|，稱函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低，記為 f(n)=O(g(n))。計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù) Ω的定義： 如果存在正常數(shù)c和n0，對于所有n≥n0時(shí)，有： |f(n)|≥c|g(n)|，則稱函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個(gè)下界，即f(n)的階不低于g(n)的階。記為： f(n)=Ω(g(n))。Θ的定義： 如果存在正常數(shù)c1，c2和n0，對于所有的n>n0，有： c1|g(n)|≤f(n)≤c2|g(n)|，則記f(n)=Θ(g(n))意味著該算法在最好和最壞的情況下計(jì)算時(shí)間就一個(gè)常因子范圍內(nèi)而言是相同的。(1)多項(xiàng)式時(shí)間算法： O(1) (2)指數(shù)時(shí)間算法： O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 貪心方法基本思想： 貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 多段圖： COST[j]=c(j,r)+COST[r]; 回溯法： (假定集合Si的大小是mi)不斷地用修改過的規(guī)范函數(shù)Pi(x1,…,xi)去測試正在構(gòu)造中的n-元組的部分向量(x1,…,xi)，看其是否可能導(dǎo)致最優(yōu)解。如果判定(x1,…,xi)不可能導(dǎo)致最優(yōu)解，那么就將可能要測試的mi+1…mn個(gè)向量略去。約束條件： (1)顯式約束：限定每一個(gè)xi只能從給定的集合Si上取值。 (2)解 空 間：對于問題的一個(gè)實(shí)例，解向量滿足顯式 約束條件的所有多元組，構(gòu)成了該實(shí)例 的一個(gè)解空間。 (3)隱式約束：規(guī)定解空間中實(shí)際上滿足規(guī)范函數(shù)的元 組，描述了xi必須彼此相關(guān)的情況?；咀龇ǎ?/p> 在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解：如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 8皇后問題 約束條件 限界函數(shù)： 子集和數(shù)問題： 約束條件 限界函數(shù)： 回溯法－－術(shù)語： 活結(jié)點(diǎn)：已生成一個(gè)結(jié)點(diǎn)而它的所有兒子結(jié)點(diǎn)還沒有 全部生成的結(jié)點(diǎn)稱為活結(jié)點(diǎn)。 E-結(jié)點(diǎn)：當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫E-結(jié)點(diǎn)。 死結(jié)點(diǎn)：不再進(jìn)一步擴(kuò)展或其兒子結(jié)點(diǎn)已全部生成的結(jié)點(diǎn)稱為死結(jié)點(diǎn)。 使用限界函數(shù)的深度優(yōu)先節(jié)點(diǎn)生成的方法成為回溯法；E-結(jié)點(diǎn)一直保持到死為止的狀態(tài)生成的方法 稱之為分支限界方法 且用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹的狀態(tài)空間的檢索方法。區(qū)別： 分支限界法本質(zhì)上就是含有剪枝的回溯法，根據(jù)遞歸的條件不同，是有不同的時(shí)間復(fù)雜度的。 回溯法深度優(yōu)先搜索堆?；蚬?jié)點(diǎn)的所有子節(jié)點(diǎn)被遍歷后才被從棧中彈出找出滿足約束條件的所有解 分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊(duì)列，優(yōu)先隊(duì)列每個(gè)結(jié)點(diǎn)只有一次成為活結(jié)點(diǎn)的機(jī)會找出滿足約束條件下的一個(gè)解或特定意義下的最優(yōu)解 一般如果只考慮時(shí)間復(fù)雜度二者都是指數(shù)級別的 可是因?yàn)榉种藿绶ù嬖谥鞣N剪枝，用起來時(shí)間還是很快的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是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問題的集合 如果可滿足星月化為一個(gè)問題L，則此問題L是NP-難度的。如果L是NP難度的且L NP，則此問題是NP-完全的第五篇：算法總結(jié)材料
點(diǎn)擊咨詢 