算法設(shè)計(jì)與分析復(fù)習(xí)資料

1、算法：指解決問(wèn)題的一種方法或者一個(gè)過(guò)程，更嚴(yán)格的講，算法是由若干條指令組成的有窮序列。它具有輸入，輸出，確定性，可行性，有窮性5個(gè)性質(zhì)。遞歸算法：一個(gè)直接或者間接地調(diào)用自身的算法?？尚薪猓簼M足某線性規(guī)劃所有的約束條件（指全部前約束條件和后約束條件）的任意 一組決策變量的取值，都稱為該線性規(guī)劃的一個(gè)可行解。解空間：如果E 1,七2, 七s是一般齊次線性方程組的s個(gè)解,則它們的任一線性組合cl 士 1+c2 士 2+.+cs 士 s也是該齊次線性方程組的解向量.由此可知若齊次線性方程組有非零解，則其解有無(wú)窮多個(gè)，而齊次線性方程組所有解的集合構(gòu)成一個(gè)向量空間，這個(gè)向量空間就稱為解空間.解空間也就是一

2、個(gè)集合。目標(biāo)函數(shù)：（objective function） 是指所關(guān)心的目標(biāo) （某一變量）與相關(guān)的因素（某些變 量）的函數(shù)關(guān)系。簡(jiǎn)單的說(shuō)，就是你求解后所得出的那個(gè)函數(shù)。在求解前函數(shù)是未知 的，按照你的思路將已知條件利用起來(lái)，去求解未知量的函數(shù)關(guān)系式，即為目標(biāo)函數(shù)。最優(yōu)解：使某線性規(guī)劃的目標(biāo)函數(shù)達(dá)到最優(yōu)值（最大值或最小值）的任一可行解，都稱為 該線性規(guī)劃的一個(gè)最優(yōu)解。最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題，主要是指以下形式的問(wèn)題：給定一個(gè)函數(shù)，尋找一個(gè)元素使得對(duì)于所有A中的，（最小化）；或者（最大化）。這類定式有時(shí)還稱為“數(shù)學(xué)規(guī)劃”（譬如，線性規(guī)劃）。許多現(xiàn)實(shí)和理論問(wèn)題都可以建模成這樣的一般性框架。最優(yōu)化，是應(yīng)

3、用數(shù)學(xué)的一 個(gè)分支。子問(wèn)題：一個(gè)原問(wèn)題分解后得到的問(wèn)題，規(guī)模更小。分治法：求解一個(gè)復(fù)雜問(wèn)題可以將其分解成若干個(gè)子問(wèn)題，子問(wèn)題還可以進(jìn)一步分解成更小的問(wèn)題，直到分解所得的小問(wèn)題是一些基本問(wèn)題，并且其求解方法是已知的，可以直接求解為止，這便是分治法。分治法作為一種算法設(shè)計(jì)策略，要求分解所得的子問(wèn)題是同類問(wèn)題， 并要求原問(wèn)題的解能夠通過(guò)組合子問(wèn)題的解來(lái)獲取。貪心法：貪心法是一種極為直接的算法設(shè)計(jì)技術(shù)，可應(yīng)用于多種問(wèn)題的求解。貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從 整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。動(dòng)態(tài)規(guī)劃：在多階段決策問(wèn)

4、題中， 各個(gè)階段采取的策略，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移， 一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，固有動(dòng)態(tài)之說(shuō)，稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃方法。備忘錄算法：備忘錄方法是動(dòng)態(tài)規(guī)劃方法的變形。與動(dòng)態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動(dòng)態(tài)規(guī)劃算法則是自底向上的。回溯法：又稱試探法，該方法首先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順尋逐一枚舉和檢驗(yàn)。 回溯法（探索與回溯法）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索， 以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回

5、再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。貪心選擇性質(zhì)：事先可能給定一些以函數(shù)形式表示出來(lái)的判定標(biāo)準(zhǔn)，這種在貪心法的每一步上用做決策依據(jù)的選擇準(zhǔn)則被稱為最優(yōu)度量標(biāo)準(zhǔn)，額稱為貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：對(duì)于一個(gè)問(wèn)題，如果能從較小規(guī)模子問(wèn)題的最優(yōu)解求得較大規(guī)模同類子問(wèn) 題的最優(yōu)解，最終得到給定問(wèn)題的最優(yōu)解，這就是問(wèn)題最優(yōu)解的最優(yōu)子結(jié)構(gòu)特性。重疊子問(wèn)題：適合于動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是相互獨(dú)立的，他們可能共享更小的子問(wèn)題，被稱為重疊子問(wèn)題。分治法所能解決的問(wèn)題的特征：（基本要素）該問(wèn)題的規(guī)模縮小到一定程度就可以解決； 該

6、問(wèn)題可以分解成若干規(guī)模小的相同問(wèn)題， 即該 問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；禾I用該問(wèn)題分解出的子問(wèn)題的解能合并為該問(wèn)題的解；分解的各個(gè)子問(wèn)題的解是相互獨(dú)立的。如具備了前面兩條，而不具備第三條，可以考慮貪心算法和動(dòng)態(tài)規(guī)劃。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系程序 （Program） ，程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)（4） 。例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有

7、窮序列，滿足性質(zhì)：（1） 輸入：有外部提供的量作為算法的輸入。（2） 輸出：算法產(chǎn)生至少一個(gè)量作為輸出。（3） 確定性：組成算法的每條指令是清晰，無(wú)歧義的。（4） 有窮性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。（ 5）可行性：算法中每條指令的執(zhí)行指令都有明確的定義，是可行的，可在有限的時(shí)間內(nèi)做完掌握算法的計(jì)算復(fù)雜性：算法的復(fù)雜度是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量被稱為時(shí)間復(fù)雜度，需要的空間資源的量被稱為空間復(fù)雜度。N問(wèn)題的規(guī)模I算法的輸入A算法本身，C表示復(fù)雜度， C=F（N,I,A）,算法復(fù)雜性= 算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T（n,I）

8、；算法的空間復(fù)雜性S（n,I） 。算法三態(tài)性：最好性態(tài) TMIN（N）,最壞性態(tài) TMAX（N）,平均性態(tài) TAVG（N）。算法時(shí)間復(fù)雜度，漸進(jìn)復(fù)雜度略。計(jì)算見(jiàn)書6,7,8.遞歸技術(shù)：常把問(wèn)題分為N 個(gè)子問(wèn)題，子問(wèn)題又繼續(xù)細(xì)分，知道規(guī)模足夠小，直接解決，然后逐層返回。遞歸技術(shù)的基本思想：人們?cè)诮鉀Q一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程度，一般總是將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是在解決了最后那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的基本思想。怎么解決遞歸：采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧

9、；用遞推法來(lái)實(shí)現(xiàn)遞歸函數(shù)；通過(guò)變換。（遞推法，生成函數(shù)法，特征方程法，數(shù)學(xué)歸納法，不規(guī)則法）優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)。缺點(diǎn)：運(yùn)行效率低，占用存儲(chǔ)空間大，計(jì)算時(shí)間多。分治法的算法框架（ 1 ）將一個(gè)難以直接解決的原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，這些子問(wèn)題相互獨(dú)立（ 2） 遞歸地解這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解，此外為了得到原始問(wèn)題的解，必須找到一種途徑能夠?qū)⒏鱾€(gè)子問(wèn)題的解組合成原始問(wèn)題和一個(gè)完整的答案貪心法的步驟（ 1 ）從問(wèn)題的某一初始解出發(fā)（ 2） 當(dāng)能夠向給定目標(biāo)前進(jìn)一步則求出可行解的一個(gè)解元素（ 3）由所有解元素組合成問(wèn)題的可行解（ 2） 貪心法的

10、基本思想從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的求的更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。貪心法的基本要素1. 最優(yōu)度量標(biāo)準(zhǔn)：指可以根據(jù)該度量標(biāo)準(zhǔn)，實(shí)行多步地決策進(jìn)行求解，雖然在該量度意義下所做的這些選擇都是局部最優(yōu)的，但最終得到的解卻不一定是全局最優(yōu)的。2. 最優(yōu)子結(jié)構(gòu)：指局部最優(yōu)解能夠決定全局最優(yōu)解。動(dòng)態(tài)規(guī)劃的步驟（ 1 ）找出最優(yōu)解的性質(zhì)并刻畫最優(yōu)解的結(jié)構(gòu)特性（2）遞歸定義最優(yōu)解值（3）以自底向上方式計(jì)算最優(yōu)解值（4）根據(jù)計(jì)算得到的信息構(gòu)造一個(gè)最優(yōu)解（ 2） 動(dòng)態(tài)規(guī)劃的基本思想1 將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求

11、解2 經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的，它們可能共享更小的子問(wèn)題，被成為重疊子問(wèn) 題3 如果能夠保存已經(jīng)解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大 量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。為了達(dá)到這個(gè)目的，實(shí)施自底向上計(jì)算。動(dòng)態(tài)規(guī)劃的基本要素1 最優(yōu)子結(jié)構(gòu)特性。對(duì)于一個(gè)問(wèn)題，如果能從較小規(guī)模子問(wèn)題的最優(yōu)解求得較大規(guī)模同類子問(wèn)題的最優(yōu)解，最終得到給定問(wèn)題的最優(yōu)解，這就是問(wèn)題最優(yōu)解的最優(yōu)子結(jié)構(gòu)特性。較小子問(wèn)題的最優(yōu)解與較大子問(wèn)題的最優(yōu)解之間存在數(shù)值關(guān)系，這就是最優(yōu)子結(jié)構(gòu)。2 . 子問(wèn)題重疊性質(zhì)。在用遞歸算法自頂向下求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。用這一性質(zhì)，對(duì)每一個(gè)自問(wèn)題只解一次，而后就其解保存在一個(gè)表格中，當(dāng)再次需要解次子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。貪心法與動(dòng)態(tài)規(guī)劃的比較貪心法就是通過(guò)對(duì)每一個(gè)子問(wèn)題采取最優(yōu)決策，最后達(dá)到全局最優(yōu)的一種策略。動(dòng)態(tài)規(guī)劃也是一種求解最優(yōu)化問(wèn)題的算法設(shè)計(jì)策略，它先求解若干子問(wèn)題，再根據(jù)子問(wèn)題的解來(lái)做出決策， 共同點(diǎn)是兩者所解決的問(wèn)題都有很強(qiáng)的步驟性，都要經(jīng)過(guò)各步?jīng)Q策最終得到最優(yōu)解。區(qū)別在于貪心法要求針對(duì)問(wèn)題設(shè)計(jì)最優(yōu)度量標(biāo)準(zhǔn)，動(dòng)態(tài)規(guī)劃