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

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