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

第一章概述算法的概念：算法是指解決問題的一種方法或過程，是由假設(shè)干條指令組成的有窮序列。算法的特征：可終止性：算法必需在有限時間內(nèi)終止；正確性：算法必需正確描述問題的求解過程；可行性：算法必需是可實(shí)施的；0011算法與程序的關(guān)系：區(qū)分：程序可以不肯定滿足可終止性。但算法必需在有限時間內(nèi)完畢；程序可以沒有輸出,而算法則必需有輸出；算法是面對問題求解的過程描述，程序則是算法的實(shí)現(xiàn)。聯(lián)系：程序是算法用某種程序設(shè)計語言的具體實(shí)現(xiàn)；程序可以不滿足算法的有限性性質(zhì)。算法描述方式：自然語言，流程圖，偽代碼，高級語言。算法簡單性分析：算法簡單性的凹凸表達(dá)運(yùn)行該算法所需計算機(jī)資源〔時間，空間〕的多少。算法簡單性度量：期望反映算法本身性能，與環(huán)境無關(guān)?！病Ｒ话闶轻槍栴}選擇根本運(yùn)算和根本存儲單位根本運(yùn)算與根本存儲單位的開銷作為標(biāo)準(zhǔn)。算法簡單性C問題規(guī)模N、算法輸入I和算法本身A。即C=F(N,I,A)。其次章遞歸與分治分治法的根本思想：求解問題算法的簡單性一般都與問題規(guī)模相關(guān)，問題規(guī)模越小越簡潔處理。分治法的根本思想是，將一個難以直接解決的大問題，分解為規(guī)模較小的一樣子問題，直至這些子問題簡潔直接求解，并且可以利用這些子問題的解求出原問題的解。各個擊破，分而治之。是分治法中最常用的技術(shù)。使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到肯定的程度就可以簡潔地解決；該問題可以分解為假設(shè)干個規(guī)模較小的一樣問題，即該問題具有最優(yōu)子構(gòu)造性質(zhì)；利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題?！沧鳎貜?fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好〕遞歸的概念：直接或間接地調(diào)用自身的算法稱為遞歸算法，用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。題縮小到很簡潔直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。有限次計算后得出結(jié)果。第三章動態(tài)規(guī)劃動態(tài)規(guī)劃的根本思想：挨次求解各子問題。最終一個階段或子問題的解就是初始問題的解。分治法求解時，子問題數(shù)目太多，從而導(dǎo)致解決原問題需要消耗指數(shù)級時間。與分治法不同的是，動態(tài)規(guī)劃中分解得到的子問題往往不是相互獨(dú)立的。。動態(tài)規(guī)劃的適用條件：動態(tài)規(guī)劃法解所能解決的問題一般具有以下兩個根本因素：一、最優(yōu)子構(gòu)造性質(zhì)當(dāng)問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子構(gòu)造性質(zhì)。二、重疊子問題性質(zhì)屢次。這種性質(zhì)稱為子問題的重疊性質(zhì)。其它同分治法。動態(tài)規(guī)劃問題的特征：求解的問題是組合優(yōu)化問題；求解過程需要多步推斷，從小到大依次求解；子問題目標(biāo)函數(shù)最優(yōu)解之間存在依靠關(guān)系；動態(tài)規(guī)劃算法設(shè)計的根本步驟和要素：根本步驟：找出最優(yōu)解的性質(zhì)，并刻畫其構(gòu)造特征〔考察是否適合承受動態(tài)規(guī)劃法〕遞歸地定義最優(yōu)值。(建立遞歸式或動態(tài)規(guī)劃方程)以自底向上的方式〔或以自頂向下的備忘錄方法〕計算出最優(yōu)值。依據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。要素：最優(yōu)子構(gòu)造重疊子問題備忘錄〔表格〕應(yīng)用實(shí)例分析：1、矩陣連乘問題：分析最優(yōu)解構(gòu)造：計算A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。題的最優(yōu)子構(gòu)造性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。建立遞歸關(guān)系；〔遞歸求解最優(yōu)值簡單度較高的緣由是)；計算最優(yōu)值—迭代查表求解計算最優(yōu)值—備忘錄求解構(gòu)造最優(yōu)解第四章貪心法貪心算法的根本思想：方法。優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法不能對全部問題都得到整體最優(yōu)解，但對很多問題它能產(chǎn)生整體最優(yōu)解。設(shè)計中的優(yōu)化原則本質(zhì)上是全都的。動態(tài)規(guī)劃算法在某一步打算優(yōu)化函數(shù)的最大或最小值時而是依據(jù)當(dāng)時狀況實(shí)行“只顧眼前”的貪心策略打算取舍。貪心算法的設(shè)計要素：可以用貪心算法求解的問題一般具有2個重要的性質(zhì)：1、最優(yōu)子構(gòu)造性質(zhì)：題的最優(yōu)子構(gòu)造性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征2、貪心選擇性質(zhì)：貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇選擇來到達(dá)。這是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)分。動態(tài)規(guī)劃算法通常以自底向上的方式求解各子問題為規(guī)模更小的子問題。選擇最終導(dǎo)致問題的整體最優(yōu)解。應(yīng)用實(shí)例：1、活動安排問題：第五章回溯法回溯法的根本思想：回溯法的使用條件：回溯法適用于搜尋問題和優(yōu)化問題。回溯法的設(shè)計要素：針對問題定義解空間：問題解向量解向量重量取值集合構(gòu)造解空間樹兩類典型的解空間樹：子集樹：當(dāng)所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。子集樹通常有2n個葉結(jié)點(diǎn)n樹稱為排列樹。排列樹通常有n!個葉結(jié)點(diǎn)。推斷問題是否滿足多米諾性質(zhì)。搜尋解空間樹，確定剪枝函數(shù)。確定存儲搜尋路徑的數(shù)據(jù)構(gòu)造。第六章分支限界法分支限界法的根本思想：分支界限法類似與回溯法，也是在問題解空間中搜尋問題解的一種算法。分支界限法與回溯法思想比照：支限界法的求解目標(biāo)則是找出滿足約束條件的一個解種意義下的最優(yōu)解。廣度優(yōu)先或以最小消耗優(yōu)先的方式搜尋解空間樹。兒子結(jié)點(diǎn)被