算法分析與設計知識點總結(jié)

1、第一章概述算法的概念：算法是指解決問題的一種方法或過程，是由若干條指令組成的有窮序列。算法的特征：可終止性：算法必須在有限時間內(nèi)終止；正確性：算法必須正確描述問題的求解過程；可行性：算法必須是可實施的；算法可以有0個或0個以上的輸入；算法必須有1個或1個以上的輸出。算法與程序的關(guān)系：區(qū)別：程序可以不一定滿足可終止性。但算法必須在有限時間內(nèi)結(jié)束；程序可以沒有輸出，而算法則必須有輸出；算法是面向問題求解的過程描述，程序則是算法的實現(xiàn)。聯(lián)系：程序是算法用某種程序設計語言的具體實現(xiàn)；程序可以不滿足算法的有限性性質(zhì)。算法描述方式：自然語言，流程圖，偽代碼，高級語言。算法復雜性分析：算法復雜性的高低體現(xiàn)運

2、行該算法所需計算機資源（時間，空間）的多少。算法復雜性度量：期望反映算法本身性能，與環(huán)境無關(guān)。理論上不能用算法在機器上真正的運行開銷作為標準（硬件性能、代碼質(zhì)量影響）一般是針對問題選擇基本運算和基本存儲單位，用算法針對基本運算與基本存儲單位的開銷作為標準。算法復雜性C依賴于問題規(guī)模N算法輸入I和算法本身Ao即C=F（N,I,A）。第二章遞歸與分治分治法的基本思想：求解問題算法的復雜性一般都與問題規(guī)模相關(guān)，問題規(guī)模越小越容易處理。分治法的基本思想是，將一個難以直接解決的大問題，分解為規(guī)模較小的相同子問題，直至這些子問題容易直接求解，并且可以利用這些子問題的解求出原問題的解。各個擊破，分而治之。分

3、治法產(chǎn)生的子問題一般是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。遞歸是分治法中最常用的技術(shù)。使子問題規(guī)模大致相等的做法是出自一種平衡（balancing）子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。（這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此

4、時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。）遞歸的概念:直接或間接地調(diào)用自身的算法稱為遞歸算法，用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產(chǎn)生。邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。第三章動態(tài)規(guī)劃動態(tài)規(guī)劃的基本思想：動態(tài)規(guī)劃算法與分治法類似，其思想把求解的問題分成許多階段或多個子問題，然后按順序求解各子問題。最后一個階段或子問題的解就是初始問題的解。分治法求解時，子問題數(shù)目太多，從而導致解決原問題需要耗費指數(shù)級時間。

5、與分治法不同的是，動態(tài)規(guī)劃中分解得到的子問題往往不是互相獨立的。但不同子問題的數(shù)目常常只有多項式級。用分治法求解時，有些子問題被重復計算了許多次。動態(tài)規(guī)劃的適用條件：動態(tài)規(guī)劃法解所能解決的問題一般具有以下兩個基本因素：一、最優(yōu)子結(jié)構(gòu)性質(zhì)當問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。二、重疊子問題性質(zhì)遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。其它同分治法。動態(tài)規(guī)劃問題的特征：求解的問題是組合優(yōu)化問題；求解過程需要多步判斷，從小到大依次求解；子問題目標函數(shù)最優(yōu)解之間存在依賴關(guān)系；動態(tài)規(guī)劃算法設計的基本步驟和要素

6、：基本步驟：(1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。(考察是否適合采用動態(tài)規(guī)劃法。)(2)遞歸地定義最優(yōu)值。(建立遞歸式或動態(tài)規(guī)劃方程)(3)以自底向上的方式(或以自頂向下的備忘錄方法)計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。要素：最優(yōu)子結(jié)構(gòu)重疊子問題備忘錄(表格)應用實例分析：1、矩陣連乘問題：(1)分析最優(yōu)解結(jié)構(gòu)：計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈Ai:k和Ak+1:j的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。(2)建立遞歸關(guān)系；(3)計算最優(yōu)值一遞歸求

7、解(遞歸求解最優(yōu)值復雜度較高的原因是：子問題重復度高);計算最優(yōu)值一迭代查表求解計算最優(yōu)值一備忘錄求解(4)構(gòu)造最優(yōu)解第四章貪心法貪心算法的基本思想：當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時，可用動態(tài)規(guī)劃方法求解，但有時會有更簡單有效的方法。顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。貪心算法中，較大子問題的解恰好包含了較小子問題的解作為子集，這與動態(tài)規(guī)劃算法設計中的優(yōu)化

8、原則本質(zhì)上是一致的。動態(tài)規(guī)劃算法在某一步?jīng)Q定優(yōu)化函數(shù)的最大或最小值時，需要考慮到它的所有子問題的優(yōu)化函數(shù)值，然后從中選出最優(yōu)的結(jié)果；貪心算法的每步判斷時，不考慮子問題的計算結(jié)果，而是根據(jù)當時情況采取“只顧眼前”的貪心策略決定取舍。貪心算法的設計要素：可以用貪心算法求解的問題一般具有2個重要的性質(zhì)：1、最優(yōu)子結(jié)構(gòu)性質(zhì)：當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征2、貪心選擇性質(zhì)：貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)

9、規(guī)劃算法通常以自底向上的方式求解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。應用實例：1、活動安排問題：第五章回溯法回溯法的基本思想：回溯法的使用條件：回溯法適用于搜索問題和優(yōu)化問題?；厮莘ǖ脑O計要素：針對問題定義解空間：問題解向量解向量分量取值集合構(gòu)造解空間樹兩類典型的解空間樹：n個元素白集合S中找出滿足某種性質(zhì)的子集時，2n個葉結(jié)點n個元素滿足某種性質(zhì)的排列時，相應的解空間子集樹：當所給的問題是從相應的

10、解空間樹稱為子集樹。子集樹通常有排列樹：當所給的問題是確定樹稱為排列樹。排列樹通常有n!個葉結(jié)點。判斷問題是否滿足多米諾性質(zhì)。搜索解空間樹，確定剪枝函數(shù)。確定存儲搜索路徑的數(shù)據(jù)結(jié)構(gòu)。第六章分支限界法分支限界法的基本思想：分支界限法類似與回溯法，也是在問題解空間中搜索問題解的一種算法。分支界限法與回溯法思想對比：求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為