算法分析與設(shè)計(jì)知識(shí)點(diǎn)總結(jié)

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

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

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

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

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

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

7、結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。問(wèn)（ 2）建立遞歸關(guān)系；（ 3）計(jì)算最優(yōu)值遞歸求解 （遞歸求解最優(yōu)值復(fù)雜度較高的原因是： 子問(wèn)題重復(fù)度高 )；計(jì)算最優(yōu)值迭代查表求解計(jì)算最優(yōu)值備忘錄求解（ 4）構(gòu)造最優(yōu)解第四章貪心法貪心算法的基本思想：當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，可用動(dòng)態(tài)規(guī)劃方法求解，但有時(shí)會(huì)有更簡(jiǎn)單有效的方法。顧名思義， 貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。在一些情況下， 即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最

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

9、是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式求解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行， 以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。應(yīng)用實(shí)例：1、活動(dòng)安排問(wèn)題：第五章回溯法回溯法的基本思想：回溯法的使用條件：回溯法適用于搜索問(wèn)題和優(yōu)化問(wèn)題?；厮莘ǖ脑O(shè)計(jì)要素：針對(duì)問(wèn)題定義解空間：?jiǎn)栴}解向量解向量分量取值集合構(gòu)造解空間樹(shù)兩類典型的解空間樹(shù)：子集樹(shù)：當(dāng)所

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