第一篇：總結 圖像配準算法范文
圖像配準定義為：對從不同傳感器、不同時相、不同角度所獲得的兩幅或多幅圖像進行最佳匹配的處理過程[2]。圖像配準需要分析各分量圖像上的幾何畸變，然后采用一種幾何變換將圖像歸化到統一的坐標系統中。在配準過程中，通常取其中的一幅圖像作為配準的標準，稱之為參考圖像；另一幅圖像作為配準圖像。
圖像的獲取參考圖像輸入圖像 圖像的預處理 特征提取 特征匹配 空間變換模型類型的確定 模型參數的估計 圖像的插值與變換 配準結果 配準系統的評價 圖像配準
圖1-1 圖像配準的基本流程
圖像配準算法分類按全局與局部劃分按配準的四要素劃分從自動化角度劃分全局配準點點匹配搜索空間特征空間搜索策略相似性度量互相關函數絕對差和相位相關Hausdorff距離…手工配準剛性變換仿射變換投影變換多項式變換局部變換灰度特征區域特征線特征點特征…窮盡搜索逐級求精樹圖匹配動態規劃…半自動配準自動配準
圖1-2 圖像配準方法分類-根據配準使用的特征，圖像配準的方法大致可分為三類：
(1)基于圖像灰度的配準算法。首先從參考圖像中提取目標區作為配準的模板，然后用該模板在待配準圖像中滑動，通過相似性度量(如相關系數法、差的平方和法、差的絕對值法、協方差法)來尋找最佳匹配點。
(2)基于圖像特征的配準算法。該算法是以圖像中某些顯著特征(點、線、區域)為配準基元，算法過程分為兩步：特征提取和特征匹配。首先從兩幅圖像中提取灰度變化明顯的點、線、區域等特征形成特征集。然后在兩幅圖像對應的特征集中利用特征匹配算法盡可能地將存在對應關系的特征對選擇出來。對于非特征像素點利用插值等方法作處理推算出對應匹配關系，從而實現兩幅圖像之間逐像素的配準。
(3)基于對圖像的理解和解釋的配準算法。這種配準算法不僅能自動識別相應像點，而且還可以由計算機自動識別各種目標的性質和相互關系，具有極高的可靠性和精度。這種基于理解和解釋的圖像配準涉及到諸如計算機視覺、模式識別、人工智能等許多領域。不僅依賴于這些領域中理論上的突破，而且有待于高速度并行處理計算機的研制。
從自動化角度來看，可以將配準過程分為自動、半自動和手動配準。
存在問題：如何提高圖像的配準速度將是大范圍遙感圖像自動配準問題的要點；選取何種自動配準方案以保證圖像的配準精度將是大范圍遙感圖像自動配準問題的另一要點。)
f2(x,y?g[f1(h(x, y其中，h表示二維空間坐標變換。g表示灰度或輻射變換，描述因傳感器類型的不同以及成像時氣候等環境的影響所帶來的圖像灰度的變換。配準問題的實質就是要找到最優的空域變換h和灰度變換g，使得上述的等式成立，從而找到配準變換的參數
特征空間的選擇通常要考慮以下幾個因素：相似性；空間分布；唯一性。在自動圖像配準中對特征的理解可以分為兩類。(1)基于灰度的方法：基于灰度的方法將重點放在特征匹配上，在其過程中并沒有真正提取特征。一般所說的模板匹配法就是這種方法的代表。這種方法實際上將圖像的灰度分布直接作為特征而構成匹配的基礎。(2)基于特征的方法：基于特征的方法需要在圖像中提取顯著的特征：區域(森林、湖泊、農田等)、線(區域的邊界、道路等)和點(區域的角點、線的交點、曲線上的高曲率點等)。特征應該可以分布在圖像任何地方并且可以被提取出來。
一般圖像配準的過程主要涉及到圖像的特征空間、相似性測度和搜索策略這三個方面。我們稱這三個方面為圖像配準的三要素，它們決定了圖像配準的精度和速度。
按照配準過程中采用的特征類型，圖像配準可分成兩類：基于灰度的配準和基于特征的配準的方法。
基于圖像灰度的配準方法是直接利用圖像的灰度值來確定配準的空間變換，其中充分利用圖像中所包含的信息，從而也稱為基于圖像整體內容的配準方法。這類方法的核心思想是認為參考圖像和待配準圖像上的對應點及其周圍區域具有相同或者相似的灰度，并以灰度相似為基礎采用相似度函數，然后尋找一組最優的幾何變換參數使得相似度函數最大，從而實現圖像的配準。在兩幅圖像灰度信息相似的情況下，常用的匹配方法有：互相關法(Cross-correlation)，序貫相似檢測算法(Sequential Similarity Detection Algorithms, SSDA)以及最大互信息法。
雖然基于灰度的圖像配準方法實現簡單，但存在著如下缺點：(1)對圖像的灰度變化比較敏感，尤其是非線性的光照變化，將大大降低算法的性能；(2)計算的復雜度高；(3)對目標的旋轉，形變以及遮擋比較敏感。因此這種方法通常并不單獨用在遙感圖像配準中。
基于特征的圖像配準方法可以克服利用圖像灰度信息進行圖像配準的缺點，主要體現在以下三個方面：(1)圖像的特征點比圖像的象素點要少很多，因此大大減少了配準過程的計算量；(2)特征點的匹配度量值對位置的變化比較敏感，可以大大提高配準的精確程度；(3)特征點的提取過程可以減少噪聲的影響，對灰度變化，圖像形變以及遮擋等都有較好的適應能力。因此，其在圖像配準領域得到了廣泛應用。基于特征的圖像配準方法有兩個重要環節：特征提取和特征匹配。
待配準圖像 圖像預處理特征提取 特征集合 選擇匹配基元 參考圖像 搜索策略 選擇匹配基元 特征提取特征集合配準結果重采樣 模型參數求解 匹配結果 圖2-13 基于特征的圖像配準方法的基本步驟 基于特征點的配準方法的缺點：目前大多數的遙感圖像配準系統都采用基于特征點的配準方法，以交互或自動的方式選擇必要的控制點，但這些系統不能很好地適用于自動處理大量的數據，原因是特征點或控制點的選取是一項耗時、耗力的工作，在要求實時處理的應用中，這種方法是不現實的。同時自動配準要考慮是精度問題，因為在衛星遙感圖像中自動地確定有效的、精確的控制點有時是困難的，太少的點、不準確的點或者分布不均勻的點被選取都可能導致配準的誤差，而且這種情況是經常發生的。
基于特征的要求圖像比較清晰，能選出特征點，線，區域即：基于特征點的局部自動配準的一個前提是，能夠從圖像中準確提取點特征。圖像模糊，這必然使得點特征的提取比較困難，更加容易漏選特征點和產生偽特征點，從而導致配準精度不高。
1.基于小波變換的遙感圖像自動配準算法
其基本思想是：在對大尺度遙感圖像進行配準時，為了降低運算量，提高速度，利用小波變換的多分辨率特性，首先在低分辨率圖像上獲得一組配準參數，然后以此為初始值，再向高分辨率方向上逐層映射；算法在實現上，遵循一種由粗到精的搜索策略，即首先利用相似性度量獲得圖像間的一個粗略的變換參數估計，逐層迭代搜索，最終獲得精確的配準參數。
基于圖像灰度的全局配準，全局配準則是利用整幅圖像直接對映射函數進行搜索。
基于小波變換的配準原理：圖像配準過程中，如果對整幅圖像進行搜索，計算量大、耗時長。為了減少搜索空間，可以利用小波變換構造多尺度圖像金字塔，采取由粗到細的搜索策略，即只在最高層進行全搜索，逐層縮小搜索范圍，大大提高搜索效率。圖像經小波分解后分別得到低頻和高頻分量數據，低頻子圖像反映了原圖像的平滑特征，高頻系數分別反映了原圖像水平、垂直和對角方法的亮度突變特征。該突變特征可用于圖像配準的特征點(控制點)，而且小波分解后子圖尺寸減小2l(l表示分解層數)倍。因此為了減小計算量，需要找到小波分解后的子圖配準與原圖配準之間的關系。
基于小波變換的配準方案：基于小波變換的全局配準方案，其基本思想是：首先采用小波變換將原始圖像逐級分解得到一個分辨率從低到高、規模由小到大的層次式結構(也稱金字塔結構)；然后在分辨率低的圖像層，通過線性搜索或其他策略得到該分辨率下最優解的初步變換參數估計，并將此估計作為下一級圖像層處理的搜索中心，使得變換參數估計在較高分辨率下逐級得到校正和精化，隨著分辨率的提高，估計的精度隨之提高，同時搜索的范圍也逐級縮小，最終在最高分辨率的圖層上得到滿足精度要求的最優解。可見，在分辨率最低的圖像層，即使采用線性搜索策略，由于其數據量與原始圖像相比己經很小，計算量也會大大減小，而到了分辨率較高的圖層，由于搜索的范圍越來越小，那么雖然圖像規模變大，計算量也得到了有效的控制。該方案的基本流程如下：
(1)對參考圖像和待配準圖像均采用小波變換進行逐級分解，得到不同分辨率和大小的兩組金字塔圖像；
(2)給定變換參數的搜索范圍，在分辨率最低的圖層上進行全搜索：依次取出搜索空間中的變換參數，對待配準圖像對應的圖層進行幾何變換，采用基于灰度的配準方法(互相關法、最大互信息法等)，得到該分辨率下最優解的初步變換參數估計，并將此估計作為下一級圖像層處理的搜索中心；
(3)以上一層的搜索結果為搜索中心，在高一級分辨率下搜索變換參數，由粗到精逐步細化變換參數。最終在原始配準圖像上得到滿足精度要求的配準參數
該配準方案的特點可以歸納如下：
? 算法不需要人工干預，適合于大數據量的遙感圖像自動配準。? 與基于點特征的自動配準方案相比，在缺乏先驗知識的情況下，避免了點-點匹配的方法因缺乏充足和準確的控制點而導致較大的配準誤差。? 利用了多分辨率小波的優勢，采用由粗到精的搜索策略，減少了搜索空間，加速了處理過程，提高了圖像配準的速度。
2.高分辨率SAR影像同名點自動匹配技術 圖像自動配準大致包括以下3大步驟:(1)在主、輔影像中提取特征點,通過實施同名點搜索來獲取同名點;(2)利用同名點信息來解求主、輔影像之間的變換函數;(3)對輔影像進行幾何變換,并通過重采樣來獲得糾正后的配準影像。
在這3大步驟中,之所以同名點對的確定是自動配準流程中的關鍵環節,首先,因為它的配準精度將直接決定變換函數的解求及解求精度;其次,因為同名點搜索計算復雜度通常情況下較復雜,其在整個影像配準流程中占有較高的機時量。鑒于此,研究一種高精度、高效率的同名點搜索技術將顯得格外重要。本文提出的同名點自動匹配算法大致包括以下3大步驟:(1)創建金字塔影像,并通過在金字塔影像上進行回溯搜索來確定初始變換函數類型及相應 的變換參數;(2)通過分層回溯逐層加密控制點來解求最佳變換函數類型及相應變換參數;(3)在原始影像分辨率下修正同名點坐標,以獲取最終匹配同名點對。
3.圖像配準技術研究進展
將配準技術概括為8個方面,包括:配準對象、特征提取、特征匹配、變換模型、優化策略、坐標變換與插值、系統實現及算法評估,并考慮每項內容的技術特性進行細分,然后依據某一算法的創新點進行分類。
4.圖像配準方法及其在目標跟蹤中的應用
圖像配準方法可以分為基于灰度的配準和基于特征的配準。基于特征的圖像配準方法有兩個重要環節:特征提取和特征匹配。可以選取的特征包括點、線與區域。基于特征的圖像配準方法主要有兩方面優點:a.圖像的特征點比圖像的像素點要少很多,大大減少了匹配過程的計算量;b.特征點的提取過程可以減少噪聲的影響,對灰度變化、圖像形變以及遮擋等都有較好的適應能力。
基于點特征的圖像配準方法：特征點的提取——特征點匹配——誤匹配點剔除——配準參數計算
5.圖像配準技術研究
圖像之間的配準一般可分為以下5個步驟：
(l)從基準圖像和參考圖像中提取共有的控制結構，這種控制結構可以是物體的點、邊緣和邊界等；
(2)對每幅圖像中的控制結構(特征點)進行匹配;(3)選擇幾何變換模型，并利用匹配特征點對來估計變換參數;(4)對圖像實行坐標變換和灰度插值;(5)對配準的效果進行評估。
所有圖像配準方法都可以歸納為對三個元素選擇問題，即特征空間、相似性準則和搜索策。特征空間從圖像中提取用于配準的信息，搜策略從圖像轉換集中選擇用于匹配的變換方，相似性準則決定配準的相對價值，然后基于一結果繼續搜索，直到找到能使相似性度量有人滿意的結果的圖像變換方式。根據圖像配準這三個基元素選擇的區別，圖像配準方法通常分為三類：
(l)基于象素的配準方法，即根據待配準圖像的相關函數、Fourier變換和各階矩量之間的關系式來計算配準參數。
(2)基于特征的配準方法，即根據需要配準圖像重要相同特征之間的幾何關系確定配準參數。這類方法首先需要提取特征，如圖像的邊緣、角、點、線、曲率等具有不變性的特征。提取特征可在空間域內進行，也可在變換域內進行。在空間域內常使用的特征包括邊緣、區域線的端點、線交叉點、區域中心、曲率不連續點等。其中邊緣和區域邊界最常用，可以由邊緣檢測方法和區域分割方法得到;基于特征的配準方法是圖像配準中最常見的方法，對于不同特性的圖像，選擇圖像中容易提取，并能夠在一定程度上代表待配準圖像相似性的特征作為配準依據。基于特征的配準方法在圖像配準方法中具有最強的適應性。
(3)基于模型的配準方法，這種方法是根據圖像失真的數學模型來進行非線性校正式的配準。
前兩種方法是全局圖像配準技術，需要假設圖像中的對象僅是剛性地改變位置、姿態和刻度，改變的原因往往是由受試者運動引起的。第三類方法只適合圖像中對象之間局部的非線性的、非剛性的變形校正，這種失真通常由于成像系統空間編碼的非線性引起的。所以，它需要根據成像系統的非線性失真模型來實現配準。前兩類方法多用于圖像的初步配準，且能夠解析求解，后一類方法多用于圖像的精細配準，通常利用非線性規劃的方法數值求解。
3.26：
圖像的配準和融合方法較多,主要分為三類:基于像素的配準方法,基于特征的配準方法和基于模型的配準方法。基于像素的配準方法多用于圖像的初步配準,計算量小;基于特征的配準方法定位準確,計算量較大且要首先進行特征提取;基于模型的配準方法多用于圖像的精細配準,但只適合圖像中的對象之間的局部的非線性的非剛性的變形的校正。對于像素相關性大的圖像,可利用圖像間相同位置的特征點進行配準;對于像素相似性小的圖像,需要先對圖像進行特征提取,通過提取的特征點進行配準。
基于特征點的圖像配準技術主要有兩類方法: a)比較兩幅圖像的特征點及其周圍像素的灰度、曲率等情況來計算特征點之間的相似程度,建立特征點之間的一一對應關系[1, 2]。由于僅考慮單個特征點之間的相似程度,常存在特征點誤匹配的情況。b)改進的方法是建立特征點集之間的變換關系,主要使用Hausdorff距離來匹配兩個特征點集[3, 4]。這類方法可以容忍點與點之間匹配的不準確,但是要求預先確定圖像之間變換模型的參數搜索范圍,而且在圖像差異較大時計算量很大。
配準方法可分為以下幾種:(l)基于控制點的匹配方式。控制結構為圖像中的顯著點(稱為控制點)，控制點可以是用戶提供的，也可以由算法估計，然后對控制點進行匹配，估計幾何變換參數并進行配準。(2)基于矩(monent一based)的配準方式口控制結構是復雜的圖像矩，每幅圖像被標準化，即與一個矩被歸一化的參數位置進行匹配。(3)基于邊緣的配準方式。控制結構是圖像的邊緣.通過比較邊緣像素的密度或在符號層次上比較邊緣來實施邊緣匹配。幾何變換參數直接導出并對其中一幅圖像實施相應的變換.(4)基于相似性判據最優化的方式。選擇一個幾何變化并以各種參數值施于一幅圖像上。對于每一個值，評價由相似性判據提取的控制結構。該值表明了控制結構匹配的程度，因此可以從判據的最優值實現配準。圖像配準主要包括以下四個步驟:(l)從待配準的每幅圖像中提取控制結構;(2)在每幅圖像中對控制結構進行匹配;(3)從前兩步中選擇幾何變換并對其參數 進行估計;根據圖像配準的這三個基元素選擇的區別，圖像配準的方法通常可分為三類:(l)基于象素的配準方法，即根據待配準圖像的相關函數、Fourier變換和各階矩量之間的關系式來計算配準參數。(2)基于特征的配準方法，即根據需要配準圖像重要相同特征之間的幾何關系確定配準參數。這類方法首先需要提取特征，如圖像的邊緣、角、點、線、曲率等具有不變性的特征。提取特征可在空間域內進行，也可在變換域內進行。在空間域內常使用的特征包括邊緣、區域線的端點、線交叉點、區域中心、曲率不連續點等。其中邊緣和區域邊界最常用，可以由邊緣檢測方法和區域分割方法得到;基于特征的配準方法是圖像配準中最常見的方法，對于不同特性的圖像，選擇圖像中容易提取，并能夠在一定程度上代表待配準圖像相似性的特征作為配準依據。基于特征的配準方法在圖像配準方法中具有最強的適應性。(3)基于模型的配準方法，這種方法是根據圖像失真的數學模型來進行非線性校正式的配準。前兩種方法是全局圖像配準技術，需要假設圖像中的對象僅是剛性地改變位置、姿態和刻度，改變的原因往往是由受試者運動引起的。第三類方法只適合圖像中對象之間局部的非線性的、非剛性的變形校正，這種失真通常由于成像系統空間編碼的非線性引起的。所以，它需要根據成像系統的非線性失真模型來實現配準。前兩類方法多用于圖像的初步配準，且能夠解析求解，后一類方法多用于圖像的精細配準，通常利用非線性規劃的方法數值求解。
第二篇：圖像放大算法總結及MATLAB源程序
1，插值算法（3種）：
（1）最鄰近插值（近鄰取樣法）：
最鄰近插值的的思想很簡單，就是把這個非整數坐標作一個四舍五入，取最近的整數點坐標處的點的顏色。可見，最鄰近插值簡單且直觀，速度也最快，但得到的圖像質量不高。
最鄰近插值法的MATLAB源代碼為：
A = imread('F:lena.jpg');%讀取圖像信息 imshow(A);%顯示原圖 title('原圖128*128');
Row = size(A,1);Col = size(A,2);%圖像行數和列數 nn=8;%放大倍數
m = round(nn*Row);%求出變換后的坐標的最大值 n = round(nn*Col);
B = zeros(m,n,3);%定義變換后的圖像
for i = 1 : m
for j = 1 : n
x = round(i/nn);y = round(j/nn);%最小臨近法對圖像進行插值
if x==0 x = 1;end
if y==0 y = 1;end
if x>Row x = Row;end
if y>Col y = Col;end B(i,j,:)= A(x,y,:);
end end
B = uint8(B);%將矩陣轉換成8位無符號整數 figure;imshow(B);
title('最鄰近插值法放大8倍1024*1024');
運行程序后，原圖如圖1所示：
圖1
用最鄰近插值法放大4倍后的圖如圖2所示：
圖2
（2）雙線性內插值法：
在雙線性內插值法中，對于一個目的像素，設置坐標通過反向變換得到的浮點坐標為(i+u,j+v)，其中i、j均為非負整數，u、v為[0,1)區間的浮點數，則這個像素得值 f(i+u,j+v)可由原圖像中坐標為(i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所對應的周圍四個像素的值決定，即：
f(i+u,j+v)=(1-u)(1-v)f(i,j)+(1-u)vf(i,j+1)+ u(1-v)f(i+1,j)+ uvf(i+1,j+1)其中f(i,j)表示源圖像(i,j)處的的像素值，以此類推。
這就是雙線性內插值法。雙線性內插值法計算量大，但縮放后圖像質量高，不會出現像素值不連續的的情況。由于雙線性插值具有低通濾波器的性質，使高頻分量受損，所以可能會使圖像輪廓在一定程度上變得模糊。
在MATLAB中，可用其自帶的函數imresize()來實現雙線性內插值算法。
雙線性內插值算法的MATLAB源代碼為：
A=imread('F:lena.jpg');imshow(A);
title('原圖128*128');
C=imresize(A,8,'bilinear');%雙線性插值 figure;imshow(C);
title('雙線性內插值法放大8倍1024*1024');
程序運行后，原圖如圖3所示：
圖3
雙線性內插值法放大8倍后的圖如圖4所示：
圖4
（3）雙三次插值法：
雙三次插值法能夠在很大程度上克服以上兩種算法的不足，該算法計算精度高，但計算量大，它考慮一個浮點坐標(i+u,j+v)周圍的16個鄰點。
目的像素值f(i+u,j+v)可由如下插值公式得到：f(i+u,j+v)= [A] * [B] * [C] 其中[A]=[ S(u + 1)S(u + 0)S(u2)];[C]=[ S(v + 1)S(v + 0)S(v2)];而[B]是周圍16個鄰點組成的4*4的矩陣；S(x)是對 Sin(x*π)/x 的逼近。
在MATLAB中，可用其自帶的函數imresize()來實現雙三次插值算法。MATLAB源代碼為：
A=imread('F:lena.jpg');%讀取原圖像
D=imresize(A,8,'bicubic');%雙三次插值放大8倍 figure;
T
imshow(D);title('三次卷積法放大8倍1024*1024');
MATLAB自帶雙三次插值法運行結果如圖5所示：
圖5
也可以自己編寫雙三次插值算法MATLAB代碼如下：
clc,clear;
ff=imread('F:lena.jpg');%讀取圖像到ff
k=8;%設置放大倍數 [m,n,color]=size(ff);
f=zeros(m,n);%將彩色圖像ff轉換為黑白圖像f for i=1:m
for j=1:n
f(i,j)=ff(i,j);
end end
a=f(1,:);c=f(m,:);%將待插值圖像矩陣前后各擴展兩行兩列,共擴展四行四列 b=[f(1,1),f(1,1),f(:,1)',f(m,1),f(m,1)];d=[f(1,n),f(1,n),f(:,n)',f(m,n),f(m,n)];a1=[a;a;f;c;c];a1';
b1=[b;b;a1';d;d];f=b1';f1=double(f);
for i=1:k*m %利用雙三次插值公式對新圖象所有像素賦值 u=rem(i,k)/k;i1=floor(i/k)+2;A=[sw(1+u)sw(u)sw(1-u)sw(2-u)];
for j=1:k*n
v=rem(j,k)/k;j1=floor(j/k)+2;C=[sw(1+v);sw(v);sw(1-v);sw(2-v)];
B=[f1(i1-1,j1-1)f1(i1-1,j1)f1(i1-1,j1+1)f1(i1-1,j1+2)f1(i1,j1-1)f1(i1,j1)f1(i1,j1+1)f1(i1,j1+2)f1(i1,j1-1)f1(i1+1,j1)f1(i1+1,j1+1)f1(i1+1,j1+2)f1(i1+2,j1-1)f1(i1+2,j1)f1(i1+2,j1+1)f1(i1+2,j1+2)];g1(i,j)=(A*B*C);
end end
g=uint8(g1);%將矩陣轉換成8位無符號整數 imshow(g);
title('自編雙三次插值法放大8倍圖像');
其中子函數sw代碼如下： function A=sw(w1)w=abs(w1);if w<1&&w>=0 A=1-2*w^2+w^3;elseif w>=1&&w<2 A=4-8*w+5*w^2-w^3;else
A=0;end
與MATLAB自帶函數相比，以上手工編寫的MATLAB代碼只能完成黑白圖像輸出，且運行時間遠比MATLAB自帶函數的運行時間長。手工編寫雙三次插值算法MATLAB代碼的運行結果如圖6所示：
圖6
2，其他算法簡介：
傳統的圖像放大方法有重復放大線性放大和高次多項式插值放大。重復放大最簡單,但會產生明顯的方塊效應線性放大消除了方塊效應,但會造成圖像的模糊 高次多項式插值放大效果較好,但運算復雜。由于傳統方法的固有缺陷,誕生了新一代圖像放大方法,主要有小波放大、鄰域交換內插和分形放大等。
下面簡單介紹一下增強系數小波放大算法： 算法示意圖如圖7所示：
圖7 通過二維離散小波變換,經分析高通濾波器和分析低通濾波器,可將一幅分辨率為p的二維圖像分解為分辨率為p/2的離散逼近信號A1和水平、垂直、對角三個細節信號H1、V1、D1。這四個分量都只有原圖像大小的1/4。之后又可以對A1進行同樣的分解如圖7所示。這個過程可以一直重復下去。通過二維離散小波反變換,用相應的綜合高通濾波器和綜合低通濾波器可將各分量重構為原圖像。
對于一個圖像，低頻成分包含了基本特征，即原圖像的近似，高頻成分反應其細節。基于此，我們將原圖像作為低頻成分A1，其他3個細節部分置0，進行小波重構，便可得到放大4倍的圖像。但是由于能量守恒,放大后的圖像能量分散會顯得較暗。可以將原圖像灰度值矩陣乘2，再進行上述變換，便可解決這一問題。小波分解重構是一種全局運算，不會造成重復放大中的方塊效應，同時較好地保持圖像邊緣的清晰。
第三篇：算法總結
算法分析與設計總結報告
71110415 錢玉明
在計算機軟件專業中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數據結構這個公式。算法的學習對于培養一個人的邏輯思維能力是有極大幫助的，它可以培養我們養成思考分析問題，解決問題的能力。作為IT行業學生，學習算法無疑會增強自己的競爭力，修煉自己的“內功”。
下面我將談談我對這門課程的心得與體會。
一、數學是算法的基礎
經過這門課的學習，我深刻的領悟到數學是一切算法分析與設計的基礎。這門課的很多時間多花在了數學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數學息息相關。其中有幾個定理令我印象深刻。
①主定理
本門課中它主要應用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關結論進行分析處理。當f(n)量級高于nlogba時，我們可以設法降低子問題組合時的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴大問題的規模或者減小子問題的個數。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。
②隨機算法中的許多定理的運用
在這門課中，我學到了以前從未遇見過的隨機算法，它給予我很大的啟示。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風，它是建立在嚴格的定理的證明上。如素數判定定理是個很明顯的例子。它運用了包括費馬小定理在內的各種定理。將這些定理進行有效的組合利用，才得出行之有效的素數判定的定理。尤其是對尋找證據數算法的改進的依據，也是建立在3個定理上。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數學定理的運用上。
這些算法都給予了我很大啟發，要想學好算法，學好數學是必不可少的。沒有深厚的數學功力作為地基，即使再漂亮的算法框架，代碼實現也只能是根底淺的墻上蘆葦。
二、算法的核心是思想
我們學習這門課不是僅僅掌握那幾個經典算法例子，更重要的是為了學習蘊含在其中的思想方法。為什么呢？舉個例子。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發期為1個星期。現在用10只老鼠在一個星期內判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領域相關，我就立馬有了思路，運用二進制。因為計算機的最基本思想就是二進制。所以說，我們不僅要學習算法，更得學習思想方法。
①算法最基本的設計方法包括分治法，動態規劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做Strassen矩陣乘法等等。它的思想就是規模很大的問題分解為規模較小的獨立的子問題，關鍵是子問題要與原問題同類，可以采取平衡法來提高性能。
動態規劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可以利用前面解決過的問題的結果。如構造最優二叉查找樹，解決矩陣連乘時最小計算次數問題，尋找最長公共子序列等等。
貪心法就是局部最優法，先使局部最優，再依次構造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。
周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優先搜索(DFS)和廣度優先搜索(BFS)。
回溯法就是就是在滿足一定的條件后就往前走，當走到某步時，發現不滿足條件就退回一步重新選擇新的路線。典型的應用就是8皇后問題，平面點集的凸包問題和0-1背包問題。
分支定界法：它是解決整數規劃問題一種最常用的方法。典型應用就是解決整數規劃問題。
②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執行這步指令的消耗，再將每一步消耗全部累計。
這幾種方法都是平攤分析法，平攤分析的實質就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。
三、算法與應用緊密相關
我認為學習算法不能局限于書本上的理論運算，局限于如何提高性能以降低復雜度，我們要將它與實際生活聯系起來。其實算法問題的產生就來自于生活，設計出高效的算法就是為了更好的應用。如尋找最長公共子序列算法可以應用在生物信息學中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個字符串的相近性，這可應用在數據挖掘中。快速傅立葉變換（FFT）可應用在計算多項式相乘上來降低復雜度，脫線min算法就是利用了Union-Find這種結構。還有圖中相關算法，它對于解決網絡流量分配問題起了很大的幫助，等等。
這些應用給了我很大的啟發：因為單純講一個Union-Find算法，即使了解了它的實現原理，遇到具體的實際問題也不知去如何應用。這就要求我們要將自己學到的算法要和實際問題結合起來，不能停留在思想方法階段，要學以致用，做到具體問題具體分析。
四、對計算模型和NP問題的理解
由于對這部分內容不是很理解，所以就粗淺的談一下我的看法。
首先談到計算模型，就不得不提到圖靈計算，他將基本的計算抽象化，造出一個圖靈機，得出了計算的本質。并提出圖靈機可以計算的問題都是可以計算的，否則就是不可計算的。由此引申出一個著名論題：任何合理的計算模型都是相互等價的。它說明了可計算性本身不依賴于任何具體的模型而客觀存在。
NP問題比較復雜，我認為它是制約算法發展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個特殊的性質，如果存在一個NP-C問題找到一個多項式時間的解法，則所有的NP-C問題都能找到多項式時間解法。如哈密頓回路問題。NP-hard主要是解決最優化問題。它不一定是NP問題。這些問題在規模較小時可以找出精確解，但是規模大時，就因時間太復雜而找不到最優解。此時一般會采用近似算法的解法。頑型問題就是已經證明不可能有多項式時間的算法，如漢諾塔問題。
最后談談對這門課程的建議
①對于這門算法課，我認為應該加強對算法思想方法的學習。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發課件。讓我們先思考一會兒，或者給出個獎勵機制，誰能解決這個問題，平時成績加分。這在一定程度上會將強我們思考分析問題的能力。因為我感覺到，一個問題出來，未經過思考就已經知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點名回答問題可以一定程度上有效的防止不認真聽課的現象。
②作業安排的不是很恰當。本門課主要安排了三次作業，個人感覺只有第一次作業比較有意思。后面兩次作業只是實現一下偽代碼，沒有太多的技術含量。而且對于培養我們的解決問題的能力也沒有太多的幫助，因為這間接成為了程序設計題，不是算法設計題。
③本門課的時間安排的不太恰當，因為本學期的課程太多，壓力太大。沒有太多的時間去學習這門課程。因為我相信大家都對它感興趣，比較重視，想花功夫，但苦于沒時間。所以可不可以將課程提前一個學期，那時候離散數學也已經學過，且課程的壓力也不是很大。錯開時間的話，我覺得應該能夠更好提高大家算法分析設計的能力。
第四篇：算法總結
算法分塊總結
為備戰2005年11月4日成都一戰，特將已經做過的題目按算法分塊做一個全面詳細的總結，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設計中，時刻都要牢記要減少冗余，要以簡潔高效為追求目標。另外當遇到陌生的問題時，要想方設法進行模型簡化，轉化，轉化成我們熟悉的東西。
圖論模型的應用
分層圖思想的應用：
用此思想可以建立起更簡潔、嚴謹的數學模型，進而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質： 由于層是由復制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進行新層的存儲，甚至幾乎不需要花時間去處理。由于層之間的相似性，很多計算結果都是相同的。所以我們只需對這些計算進行一次，把結果存起來，而不需要反復計算。如此看來，雖然看起來圖變大了，但實際上問題的規模并沒有變大。層之間是拓撲有序的。這也就意味著在層之間可以很容易實現遞推等處理，為發現有效算法打下了良好的基礎。
這些特點說明這個分層圖思想還是很有潛力的，尤其是各層有很多公共計算結果這一點，有可能大大消除冗余計算，進而降低算法時間復雜度。二分圖最大及完備匹配的應用： ZOJ place the robots: 二分圖最優匹配的應用：
最大網絡流算法的應用：典型應用就求圖的最小割。最小費用最大流的應用：
容量有上下界的最大流的應用：
歐拉路以及歐拉回路的應用：主要利用求歐拉路的套圈算法。最小生成樹：
求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復雜度降為O(Vlog2V+E)，后者一般應用于稀疏圖，其時間復雜度為O(Elog2V)。最小K度限制生成樹：
抽象成數學模型就是：
設G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個頂點,k為給定的一個正整數。首先考慮邊界情況。先求出問題有解時k 的最小值：把v0點從圖中刪去后，圖中可能會出 現m 個連通分量，而這m 個連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當k 首先，將 v0和與之關聯的邊分別從圖中刪去，此時的圖可能不再連通，對各個連通分量，分別求最小生成樹。接著，對于每個連通分量V’，求一點v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時間復雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉化成以v0為根的有根樹。 假設已經得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關聯的邊后，必定形成一個環。若想得到一棵p+1 度限制生成樹，需刪去一條在環上的且與v0無關聯的邊。刪去的邊的權值越大，則所得到的生成樹的權值和就越小。動態規劃就有了用武之地。設Best(v)為路徑v0—v上與v0無關聯且權值最大的邊。定義father(v)為v的父結點，動態轉移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 狀態共|V|個，狀態轉移的時間復雜度O(1)，所以總的時間復雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時間復雜度為O(V)。1 先求出最小m度限制生成樹； 2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當dT(v0)=k時停止。 加邊和去邊過程，利用動態規劃優化特別值得注意。 次小生成樹： 加邊和去邊很值得注意。 每加入一條不在樹上的邊，總能形成一個環，只有刪去環上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權值越大，新得到的生成樹的權值和越小。具體做法： 首先做一步預處理，求出樹上每兩個結點之間的路徑上的權值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環上的權值最大的邊。如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。 最短路徑的應用： Dijkstra 算法應用： Folyed 算法應用： Bellman-Ford 算法的應用： 差分約束系統的應用： 搜索算法 搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數據有序化，要找一個較優的搜索出發點，凡是能用高效算法的地方盡量爭取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應用： 枚舉思想的應用： ZOJ 1252 island of logic A*算法的應用： IDA*算法的應用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，動態規劃）： ZOJ milk bottle data: 剪枝優化探索： 可行性剪枝，最優性剪枝，調整搜索順序是常用的優化手段。 動態規劃 動態規劃最重要的就是狀態的選取，以及狀態轉移方程，另外還要考慮高效的預處理（以便更好更快的實現狀態轉移）。最常用的思想就是用枚舉最后一次操作。 狀態壓縮DP，又叫帶集合的動態規劃：題目特點是有一維的維數特別小。類似TSP問題的DP： 狀態劃分比較困難的題目： 樹形DP： 四邊形不等式的應用探索：四邊形不等式通常應用是把O(n^3)復雜度O(n^2) 高檔數據結構的應用 并查集的應用： 巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應用： 總結用線段樹解題的方法 根據題目要求將一個區間建成線段樹，一般的題目都需要對坐標離散。建樹時，不要拘泥于線段樹這個名字而只將線段建樹，只要是表示區間，而且區間是由單位元素(可以是一個點、線段、或數組中一個值)組成的，都可以建線段樹；不要拘泥于一維，根據題目要求可以建立面積樹、體積樹等等 樹的每個節點根據題目所需，設置變量記錄要求的值 用樹形結構來維護這些變量：如果是求總數，則是左右兒子總數之和加上本節點的總數，如果要求最值，則是左右兒子的最大值再聯系本區間。利用每次插入、刪除時，都只對O(logL)個節點修改這個特點，在O(logL)的時間內維護修改后相關節點的變量。 在非規則刪除操作和大規模修改數據操作中，要靈活的運用子樹的收縮與葉子節點的釋放，避免重復操作。 Trie的應用：； Trie圖的應用探索： 后綴數組的應用研究： 在字符串處理當中，后綴樹和后綴數組都是非常有力的工具，其中后綴樹了解得比較多，關于后綴數組則很少見于國內的資料。其實后綴數組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現，能夠實現后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。 樹狀數組的應用探索：； 計算幾何 掌握基本算法的實現。凸包的應用：； 半平面交算法的應用：； 幾何+模擬類題目：幾何設計好算法，模擬控制好精度。掃描法：； 轉化法：ZOJ 1606 將求所圍的格子數，巧妙的轉化為求多邊形的面積。離散法思想的應用：； 經典算法：找平面上的最近點對。 貪心 矩形切割 二分思想應用 活用經典算法 利用歸并排序算法思想求數列的逆序對數： 利用快速排序算法思想，查詢N個數中的第K小數： 博弈問題 博弈類題目通常用三類解法：第一類推結論； 第二類遞推，找N位置，P位置； 第三類SG函數的應用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。 第一類：推結論。典型題目： 第二類：遞推。典型題目： 比如有向無環圖類型的博弈。在一個有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應該具有如下性質： 1． 所有的結束位置都是P位置。 2． 對于每一個N位置，至少存在一種移動可以將棋子移動到一個P位置。3． 對于每一個P位置，它的每一種移動都會將棋子移到一個N位置。 這樣，獲勝的策略就是每次都把棋子移動到一個P位置，因為在一個P位置，你的對手只能將棋子移動到一個N位置，然后你總有一種方法再把棋子移動到一個P位置。一直這樣移動，最后你一定會將棋子移動到一個結束位置（結束位置是P位置），這時你的對手將無法在移動棋子，你便贏得了勝利。 與此同時，得到了這些性質，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為： 1． 將所有的結束位置標為P位置。 2． 將所有能一步到達P位置的點標為N位置。 3． 找出所有只能到達N位置的點，將它們標為P位置。 4． 如果在第三步中沒有找到新的被標為P位置的點，則算法結束，否則轉到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數的應用。 關于SG函數的基本知識：對于一個有向圖(X, F)來說，SG函數g是一個在X上的函數，并且它返回一個非負整數值，具體定義為 g(x)?min{n?0,n?g(y)對于所有y?F(x)} 1． 對于所有的結束位置x，g(x)= 0。 2． 對于每一個g(x)≠ 0的位置x，在它可以一步到達的位置中至少存在一個位置y使得g(y)= 0。 3．對于每一個g(x)＝ 0的位置x，所有可以由它一步到達的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i個有向圖的SG函數值，i = 1,…,n，那么在由這n個有向圖組成的狀態的SG函數值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類：極大極小法。 典型題目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關系（最基本的就是求Fibonacci數列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目： 數學模型舉例 向量思想的應用： UVA 10089：注意降維和向量的規范化 ； 利用復數思想進行向量旋轉。 UVA 10253： 遞推 數代集合 數代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數代集合思想優化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個數不會超過100，因此可以考慮用一個數代替一個集合，首先把所有的運算結果都用預處理算出來，到計算的時候只要用O(1)的復雜度就可以完成一次運算。 組合數學 Polya定理則是解決同構染色計數問題的有力工具。 補集轉化思想 ZOJ 單色三角形： 字符串相關 擴展的KMP算法應用：；最長回文串； 最長公共子串； 最長公共前綴； 填充問題 高精度運算 三維空間問題專題 無論什么問題，一旦擴展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實現能力。 其它問題的心得 解決一些判斷同構問題的方法：同構的關鍵在于一一對應，而如果枚舉一一對應的關系，時間復雜度相當的高，利用最小表示，就能把一個事物的本質表示出來。求最小表示時，我們一定要仔細分析，將一切能區分兩個元素的條件都在最小表示中體現，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當的、高效的匹配算法（例如KMP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進行推廣 源程序代碼： } 一、自然數拆分（遞歸） } #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-完全的第五篇：算法總結材料
點擊咨詢 