《算法課程總結(jié)》PPT課件

1、算法分析與設(shè)計(jì)課程總結(jié)算法分析與設(shè)計(jì)課程總結(jié)課程主講 計(jì)算機(jī)科學(xué)學(xué)院 王小明 博士/教授/博士生導(dǎo)師 :算法分析與設(shè)計(jì)課程總結(jié)算法分析與設(shè)計(jì)課程總結(jié)第一部分第一部分 課程回想課程回想第二部分第二部分 算法比較算法比較第一部分：課程回想第一部分：課程回想算法課程總結(jié)最優(yōu)子構(gòu)造課程思想導(dǎo)圖課程思想導(dǎo)圖定義：用變量的舊值不斷遞推出新值的處理問題的方法。定義：用變量的舊值不斷遞推出新值的處理問題的方法。通常用于數(shù)值計(jì)算。通常用于數(shù)值計(jì)算。實(shí)現(xiàn)：遞推法利用問題本身所具有的一種遞推關(guān)系求問實(shí)現(xiàn)：遞推法利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法題解的一種方法倒推法倒推法是

2、對(duì)某些特殊問題所采用的違反通倒推法倒推法是對(duì)某些特殊問題所采用的違反通常習(xí)慣的，從后向前推解問題的方法，如猴子偷桃問題常習(xí)慣的，從后向前推解問題的方法，如猴子偷桃問題課程回想迭代法迭代法(iteration):(iteration):定義：把問題的一切情況或一切過程交給計(jì)算機(jī)去一定義：把問題的一切情況或一切過程交給計(jì)算機(jī)去一一嘗試，從中找出問題的解。如獄吏問題。一嘗試，從中找出問題的解。如獄吏問題。如枚舉法如枚舉法(enumerate)(enumerate)運(yùn)用：順序查找，選擇排序，冒泡排序，插入排序都是采運(yùn)用：順序查找，選擇排序，冒泡排序，插入排序都是采用的蠻力法用的蠻力法課程回想蠻力法：蠻

3、力法：運(yùn)用：折半查找，快速排序，二叉樹遍歷，等等。運(yùn)用：折半查找，快速排序，二叉樹遍歷，等等。定義定義: :把一個(gè)難于直接處理的大問題分解為假設(shè)干個(gè)把一個(gè)難于直接處理的大問題分解為假設(shè)干個(gè)“類似的小問題，類似的小問題，再解一切小問題，然后把小問題的解再解一切小問題，然后把小問題的解“合并，從而得到大問題的解。合并，從而得到大問題的解。課程回想分治法分治法: :思想：把問題分解為大小相當(dāng)或相等的獨(dú)立子問題，然后處理思想：把問題分解為大小相當(dāng)或相等的獨(dú)立子問題，然后處理子問題，最后把子問題的解合并，得到原問題的解。子問題，最后把子問題的解合并，得到原問題的解。實(shí)現(xiàn)：實(shí)現(xiàn)： 二分法：每次把問題一分為

4、二。如二分法求金塊分配問題二分法：每次把問題一分為二。如二分法求金塊分配問題減治法：只需處理子問題的一部分，合并這部分子問題的解即可減治法：只需處理子問題的一部分，合并這部分子問題的解即可得到原問題的解。得到原問題的解。* *遞歸方法是詳細(xì)實(shí)現(xiàn)分治算法的一種技術(shù)。遞歸方法是詳細(xì)實(shí)現(xiàn)分治算法的一種技術(shù)。* *分治法是遞歸設(shè)計(jì)方法的一種詳細(xì)戰(zhàn)略。分治法是遞歸設(shè)計(jì)方法的一種詳細(xì)戰(zhàn)略。定義：貪婪算法總是作出在當(dāng)前看來(lái)最好的選擇。即貪婪算法并定義：貪婪算法總是作出在當(dāng)前看來(lái)最好的選擇。即貪婪算法并不從整體最優(yōu)思索，它所作出的選擇只是在某種意義上的部分最不從整體最優(yōu)思索，它所作出的選擇只是在某種意義上的部

5、分最優(yōu)選擇。如背包問題、工資發(fā)放問題優(yōu)選擇。如背包問題、工資發(fā)放問題運(yùn)用：活動(dòng)安排問題、最優(yōu)裝載、哈夫曼編碼、單源最短途徑、最小生成運(yùn)用：活動(dòng)安排問題、最優(yōu)裝載、哈夫曼編碼、單源最短途徑、最小生成樹、多機(jī)調(diào)度問題樹、多機(jī)調(diào)度問題* *對(duì)于一個(gè)詳細(xì)問題，要確定它能否具有貪婪選擇性質(zhì)，必需證明每一步所對(duì)于一個(gè)詳細(xì)問題，要確定它能否具有貪婪選擇性質(zhì)，必需證明每一步所作的貪婪選擇最終導(dǎo)致問題的整體最優(yōu)解。作的貪婪選擇最終導(dǎo)致問題的整體最優(yōu)解。哪些問題適宜用哪些問題適宜用“貪婪法獲得的最優(yōu)解？貪婪法獲得的最優(yōu)解？滿足：貪婪選擇性質(zhì)、最優(yōu)子構(gòu)造性質(zhì)的問題適宜用滿足：貪婪選擇性質(zhì)、最優(yōu)子構(gòu)造性質(zhì)的問題適宜用

6、“貪婪法求最優(yōu)解貪婪法求最優(yōu)解1.1.貪婪選擇性質(zhì)所求問題的整體最優(yōu)解可以經(jīng)過一系列部分最優(yōu)解的選擇，貪婪選擇性質(zhì)所求問題的整體最優(yōu)解可以經(jīng)過一系列部分最優(yōu)解的選擇，即即“貪婪選擇來(lái)得到。貪婪選擇來(lái)得到。2.2.最優(yōu)子構(gòu)造性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其一切子問題的最優(yōu)解時(shí)，稱最優(yōu)子構(gòu)造性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其一切子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子構(gòu)造性質(zhì)。此問題具有最優(yōu)子構(gòu)造性質(zhì)。課程回想貪婪法：貪婪法：定義：我們把這種經(jīng)過多階段決策以最優(yōu)化處理問題的定義：我們把這種經(jīng)過多階段決策以最優(yōu)化處理問題的過程稱為動(dòng)態(tài)規(guī)劃。過程稱為動(dòng)態(tài)規(guī)劃。 問題特征：適宜用動(dòng)態(tài)規(guī)劃算法處理的問題及決策應(yīng)該具問題

7、特征：適宜用動(dòng)態(tài)規(guī)劃算法處理的問題及決策應(yīng)該具有三個(gè)性質(zhì)：最優(yōu)化原理、無(wú)后向性、子問題重疊有三個(gè)性質(zhì)：最優(yōu)化原理、無(wú)后向性、子問題重疊( (子問子問題之間是不獨(dú)立的題之間是不獨(dú)立的) )性質(zhì)。性質(zhì)。根本思想：把求解的問題分成許多階段或多個(gè)子問題，根本思想：把求解的問題分成許多階段或多個(gè)子問題，然后按順序求解各子問題。最后一個(gè)子問題的解就是然后按順序求解各子問題。最后一個(gè)子問題的解就是初始問題的解。初始問題的解。實(shí)例：實(shí)例：0-10-1背包問題、最短途徑問題、數(shù)塔問題、背包問題、最短途徑問題、數(shù)塔問題、n n矩陣連乘問題矩陣連乘問題運(yùn)用：資源分配問題、運(yùn)用：資源分配問題、n n矩陣連乘問題矩陣連

8、乘問題課程回想動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃：定義：實(shí)踐是一個(gè)類似枚舉的搜索嘗試方法，它的主題定義：實(shí)踐是一個(gè)類似枚舉的搜索嘗試方法，它的主題思想是在搜索嘗試中找問題的解，當(dāng)不滿足求解條件就思想是在搜索嘗試中找問題的解，當(dāng)不滿足求解條件就“回溯回溯( (前往前往) )，嘗試別的途徑?；厮菟惴ㄊ菄L試搜索算，嘗試別的途徑?；厮菟惴ㄊ菄L試搜索算法中最為根本的一種算法法中最為根本的一種算法, ,其采用了一種其采用了一種“走不通就掉頭走不通就掉頭的思想，作為其控制構(gòu)造。如八皇后問題的思想，作為其控制構(gòu)造。如八皇后問題課程回想 回溯(Backtravking)算法：定義：一種在問題解空間上進(jìn)展嘗試搜索算法。所謂定義：

9、一種在問題解空間上進(jìn)展嘗試搜索算法。所謂“分分支是采用廣度優(yōu)先的戰(zhàn)略，依次生成結(jié)點(diǎn)支是采用廣度優(yōu)先的戰(zhàn)略，依次生成結(jié)點(diǎn)( (擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)) )的一切分支，也就是一切的兒子結(jié)點(diǎn)。和回溯法一樣，的一切分支，也就是一切的兒子結(jié)點(diǎn)。和回溯法一樣，在生成的節(jié)點(diǎn)中，丟棄那些不滿足約束條件或者說(shuō)不在生成的節(jié)點(diǎn)中，丟棄那些不滿足約束條件或者說(shuō)不能夠?qū)С鲎顑?yōu)解的結(jié)點(diǎn)，其他節(jié)點(diǎn)參與活節(jié)點(diǎn)表。然能夠?qū)С鲎顑?yōu)解的結(jié)點(diǎn)，其他節(jié)點(diǎn)參與活節(jié)點(diǎn)表。然后按一定規(guī)那么后按一定規(guī)那么( (如后進(jìn)先出、先進(jìn)先出、優(yōu)先隊(duì)列如后進(jìn)先出、先進(jìn)先出、優(yōu)先隊(duì)列) )從從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)活節(jié)點(diǎn)。如裝載問題。表中選擇一個(gè)節(jié)點(diǎn)作為下一

10、個(gè)活節(jié)點(diǎn)。如裝載問題。實(shí)現(xiàn)：分支搜索、分支限界搜索、優(yōu)先隊(duì)列分支限界搜索實(shí)現(xiàn)：分支搜索、分支限界搜索、優(yōu)先隊(duì)列分支限界搜索課程回想分支搜索法：分支搜索法：概率算法：是指選擇下一步執(zhí)行步驟時(shí)，用隨機(jī)概率方法概率算法：是指選擇下一步執(zhí)行步驟時(shí)，用隨機(jī)概率方法進(jìn)展選擇，而不是用邏輯上確定的方法進(jìn)展選擇進(jìn)展選擇，而不是用邏輯上確定的方法進(jìn)展選擇. .概率算法特點(diǎn)：隨機(jī)決策、不可再現(xiàn)性在同一實(shí)例上執(zhí)行概率算法特點(diǎn)：隨機(jī)決策、不可再現(xiàn)性在同一實(shí)例上執(zhí)行兩次其結(jié)果能夠不同兩次其結(jié)果能夠不同; ;在同一實(shí)在同一實(shí) 例上執(zhí)行兩次的時(shí)間亦能夠例上執(zhí)行兩次的時(shí)間亦能夠不太一樣。、分析困難要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的

11、不太一樣。、分析困難要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)。知識(shí)。課程回想概率算法及智能優(yōu)化算法：概率算法及智能優(yōu)化算法：智能優(yōu)化算法：模擬自然過程智能優(yōu)化算法：模擬自然過程“優(yōu)勝略劣汰的算法普通稱之優(yōu)勝略劣汰的算法普通稱之為智能算法。例如，根據(jù)動(dòng)植物繁衍過程原理、物理或化學(xué)為智能算法。例如，根據(jù)動(dòng)植物繁衍過程原理、物理或化學(xué)景象原理等設(shè)計(jì)的處理困難計(jì)算問題的算法，都可以稱為智景象原理等設(shè)計(jì)的處理困難計(jì)算問題的算法，都可以稱為智能優(yōu)化算法。如蟻群算法、模擬退火算法、遺傳算法等。能優(yōu)化算法。如蟻群算法、模擬退火算法、遺傳算法等。蟻群算法：模擬自然界螞蟻尋食過程的一種分布式、啟發(fā)式群體智能算法。蟻群算法

12、：模擬自然界螞蟻尋食過程的一種分布式、啟發(fā)式群體智能算法。螞蟻一開場(chǎng)選擇尋食途徑的概率是一樣的，但經(jīng)過一段時(shí)間后更優(yōu)途徑上螞蟻一開場(chǎng)選擇尋食途徑的概率是一樣的，但經(jīng)過一段時(shí)間后更優(yōu)途徑上的信息素算子增多，螞蟻選擇更優(yōu)途徑的概率隨之增大。的信息素算子增多，螞蟻選擇更優(yōu)途徑的概率隨之增大。*迭代思想在實(shí)現(xiàn)蟻群算法時(shí)有很好的運(yùn)用。迭代思想在實(shí)現(xiàn)蟻群算法時(shí)有很好的運(yùn)用。要點(diǎn)：信息素控制計(jì)算函數(shù)設(shè)計(jì)、隨機(jī)選擇概率函數(shù)設(shè)計(jì)、閱歷參數(shù)選取要點(diǎn)：信息素控制計(jì)算函數(shù)設(shè)計(jì)、隨機(jī)選擇概率函數(shù)設(shè)計(jì)、閱歷參數(shù)選取主要運(yùn)用領(lǐng)域：組合優(yōu)化如主要運(yùn)用領(lǐng)域：組合優(yōu)化如TSP問題等、機(jī)器學(xué)習(xí)如神經(jīng)網(wǎng)絡(luò)的優(yōu)化問題等、機(jī)器學(xué)習(xí)如神經(jīng)

13、網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)等設(shè)計(jì)等遺傳算法：在每一代中，根據(jù)個(gè)體順應(yīng)度大小選挑個(gè)體，并借助于自然遺傳遺傳算法：在每一代中，根據(jù)個(gè)體順應(yīng)度大小選挑個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)展選擇、交叉、變異，產(chǎn)生新的種群。最后末代中的最優(yōu)個(gè)學(xué)的遺傳算子進(jìn)展選擇、交叉、變異，產(chǎn)生新的種群。最后末代中的最優(yōu)個(gè)體經(jīng)過解碼可以作為問題的近似最優(yōu)解。體經(jīng)過解碼可以作為問題的近似最優(yōu)解。*遺傳算法是基于迭代的一種優(yōu)化工具。遺傳算法是基于迭代的一種優(yōu)化工具。要點(diǎn)：?jiǎn)栴}元素的編碼，選擇、交叉和變異要點(diǎn)：?jiǎn)栴}元素的編碼，選擇、交叉和變異主要運(yùn)用領(lǐng)域：特別適宜組合優(yōu)化問題，在機(jī)器學(xué)習(xí)、自動(dòng)控制等領(lǐng)域同樣主要運(yùn)用領(lǐng)域：特別適宜組合優(yōu)化

14、問題，在機(jī)器學(xué)習(xí)、自動(dòng)控制等領(lǐng)域同樣運(yùn)用廣泛。運(yùn)用廣泛。課程回想智能優(yōu)化算法舉例：智能優(yōu)化算法舉例：第二部分：算法比較第二部分：算法比較算法課程總結(jié)算法比較中心思想：一切算法戰(zhàn)略的中心思想就是用算法的根本中心思想：一切算法戰(zhàn)略的中心思想就是用算法的根本工具工具循環(huán)機(jī)制和遞歸機(jī)制循環(huán)機(jī)制和遞歸機(jī)制來(lái)實(shí)現(xiàn)算法。來(lái)實(shí)現(xiàn)算法。根本戰(zhàn)略：普通而言除蠻力法，算法實(shí)現(xiàn)就是根本戰(zhàn)略：普通而言除蠻力法，算法實(shí)現(xiàn)就是“化化大為小，化繁為簡(jiǎn)的過程。大為小，化繁為簡(jiǎn)的過程。算法戰(zhàn)略和算法的區(qū)別與聯(lián)絡(luò)：算法戰(zhàn)略和算法的區(qū)別與聯(lián)絡(luò)：它們是算法設(shè)計(jì)中的兩個(gè)方面，算法戰(zhàn)略是面向問題的它們是算法設(shè)計(jì)中的兩個(gè)方面，算法戰(zhàn)略是面向

15、問題的,算法是面向?qū)崿F(xiàn)的。算法是面向?qū)崿F(xiàn)的。二者又是不可分的二者又是不可分的, 經(jīng)過算法戰(zhàn)略可以找出處理問題的經(jīng)過算法戰(zhàn)略可以找出處理問題的算法，經(jīng)過處理的算法亦可反映其處理戰(zhàn)略。算法，經(jīng)過處理的算法亦可反映其處理戰(zhàn)略。綜述：綜述：算法策略算法策略迭代法迭代法蠻力法蠻力法分治法分治法基本思想用變量的舊值不斷遞推出新值的解決問題的方法把問題的所有情況或所有過程交給計(jì)算機(jī)去一一嘗試分解解決合并算法（實(shí)現(xiàn)）遞推法倒推法枚舉法二分法減治法適合解決的問題適用解決計(jì)算問題問題可能的解是有限的、固定的、不會(huì)產(chǎn)生組合爆炸、容易枚舉的。多用于決策類問題。問題的解可以通過將問題分解成相互獨(dú)立的、”相似”的子問題來(lái)

16、得到。算法比較迭代法、蠻力法、分治法比較迭代法、蠻力法、分治法比較算法策略算法策略貪心法貪心法動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法思想做從當(dāng)前來(lái)看最好的選擇整體規(guī)劃動(dòng)態(tài)解決，做整體最優(yōu)選擇最優(yōu)子結(jié)構(gòu)性質(zhì)滿足。滿足。貪心選擇性質(zhì)滿足。后向性無(wú)后向性適用問題滿足最優(yōu)子結(jié)構(gòu)、貪心選擇性質(zhì)的問題。如多機(jī)調(diào)度問題等滿足最優(yōu)子結(jié)構(gòu)、無(wú)后向性、子問題重疊性質(zhì)的問題。如資源分配問題算法比較動(dòng)態(tài)規(guī)劃法與貪婪法比較動(dòng)態(tài)規(guī)劃法與貪婪法比較算法策略算法策略分治法分治法動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法思想分解解決合并得出問題結(jié)果整體規(guī)劃動(dòng)態(tài)解決，做整體最優(yōu)選擇子問題重疊子問題相互獨(dú)立，不包含公共子問題將問題歸納為更小的、 相似的子問題子，子問題不獨(dú)立、有重疊適用問題問題可分解且子問題相互獨(dú)立，如折半查找，快速排序等滿足最優(yōu)子結(jié)構(gòu)、無(wú)后向性、子問題重疊性質(zhì)的問題。如資源分配問題算法比較動(dòng)態(tài)規(guī)劃法與分治法比較動(dòng)態(tài)規(guī)劃法與分治法比較算法算法