1、期末復(fù)習(xí)期末復(fù)習(xí) 題型題型 選擇題（選擇題（10分）分） 填空題（填空題（10分）分） 算法應(yīng)用題（算法填空，簡(jiǎn)單問題回答）算法應(yīng)用題（算法填空，簡(jiǎn)單問題回答） （3-4個(gè)題，個(gè)題，35-40分）分） 算法設(shè)計(jì)（按照已知條件設(shè)計(jì)算法或?yàn)樗闼惴ㄔO(shè)計(jì)（按照已知條件設(shè)計(jì)算法或?yàn)樗?法補(bǔ)充完整）（法補(bǔ)充完整）（3個(gè)題，個(gè)題，45-50分）分） 第第1章章 算法的性質(zhì)及其與程序的區(qū)別算法的性質(zhì)及其與程序的區(qū)別 算法復(fù)雜性分析算法復(fù)雜性分析 漸進(jìn)意義下的四種記號(hào)漸進(jìn)意義下的四種記號(hào) 簡(jiǎn)單的程序段的復(fù)雜度分析簡(jiǎn)單的程序段的復(fù)雜度分析 算法的五個(gè)重要特征 輸入輸入 有有零個(gè)或多個(gè)零個(gè)或多個(gè)由外部提供的量作為算

2、法的輸入由外部提供的量作為算法的輸入 輸出輸出 算法產(chǎn)生算法產(chǎn)生至少一個(gè)量至少一個(gè)量作為輸出作為輸出. 確定性確定性 組成算法的每條指令是清晰的組成算法的每條指令是清晰的,無歧義的無歧義的. 有限性有限性 在執(zhí)行了有窮步驟后運(yùn)算終止在執(zhí)行了有窮步驟后運(yùn)算終止 可行性可行性 運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成。運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成。 漸進(jìn)意義下的記號(hào)：O, f(N)和和g(N)是定義在正整數(shù)上的正函數(shù)是定義在正整數(shù)上的正函數(shù) 定義定義1.1 1.1 如果存在兩個(gè)正常數(shù)如果存在兩個(gè)正常數(shù)c和和N0,對(duì)于所有的對(duì)于所有的NN0， 有有f(N) Cg(N)，則記作：，則記

3、作：f(N)= O(g(N)。 N0 f(N) g(N) 當(dāng)說一個(gè)算法具有當(dāng)說一個(gè)算法具有O(g(n)的計(jì)算時(shí)間時(shí)，指的的計(jì)算時(shí)間時(shí)，指的 就是如果此算法用就是如果此算法用n值不變的同一類數(shù)據(jù)在某臺(tái)值不變的同一類數(shù)據(jù)在某臺(tái) 機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于g(n)的一個(gè)的一個(gè) 常數(shù)倍。常數(shù)倍。 g(n)是計(jì)算時(shí)間是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)，的一個(gè)上界函數(shù)，f(n)的數(shù)的數(shù) 量級(jí)就是量級(jí)就是g(n) 符號(hào)符號(hào)的定義的定義 定義定義1.2 如果存在兩個(gè)正常數(shù)如果存在兩個(gè)正常數(shù)C和自然數(shù)和自然數(shù)N0， 使得當(dāng)使得當(dāng)N N0時(shí)有時(shí)有f(N)Cg(N)，則稱函數(shù)，則

4、稱函數(shù)f(N) 當(dāng)當(dāng)N充分大時(shí)下有界；且充分大時(shí)下有界；且g(N)是它的一個(gè)下界，是它的一個(gè)下界， 記為記為f(N)=(g(N)。這時(shí)我們說。這時(shí)我們說f(N)的階不低的階不低 于于g(N)的階。的階。 ，o 的定義 定義定義f(N)= (g(N)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)f(N)=O(g(N)且且 f(N)=(g(N)。這時(shí)，我們說。這時(shí)，我們說f(N)與與g(N)同階同階 o 如果對(duì)于任意給定的如果對(duì)于任意給定的0，都存在正整數(shù)，都存在正整數(shù)N0， 使得當(dāng)使得當(dāng)N N0時(shí)有時(shí)有f(N)/g(N)，則稱函數(shù)，則稱函數(shù) f(N)當(dāng)當(dāng)N充分大時(shí)的階比充分大時(shí)的階比g(N)低，記為低，記為 f(N)=o(g

5、(N) 例如：例如：4NlogN+7=o(3N2+4NlogN+7) 1.2 算法分析初 步 多項(xiàng)式時(shí)間算法多項(xiàng)式時(shí)間算法 (polynomial time algorithm):可用多項(xiàng)式可用多項(xiàng)式 來對(duì)其計(jì)算時(shí)間限界的來對(duì)其計(jì)算時(shí)間限界的 算法算法 O(1)O(logn)O(n)O (nlogn)O(n2)O(n3) 指數(shù)時(shí)間算法指數(shù)時(shí)間算法 (exponential time algorithm):計(jì)算時(shí)間用計(jì)算時(shí)間用 指數(shù)函數(shù)限界的算法指數(shù)函數(shù)限界的算法 O(2n)O(n!)O(nn) 作業(yè)作業(yè)1-7 第第2章章 遞歸遞歸 分治法基本思想分治法基本思想 二分搜索算法二分搜索算法 Str

6、assen矩陣乘法矩陣乘法 合并排序和快速排序合并排序和快速排序 遞歸復(fù)雜度分析 漢諾塔移動(dòng)次數(shù) M(1)=1 M(n)=2M(n-1)+1 = 22M(n-2)+1+1 = 22M(n-2)+2+1 = 23M(n-3)+22+2+1 = =2iM(n-i)+2i-1+2i-2+2+1 =2iM(n-i)+2i - 1 令令i= n -1 則則M(n)= 2n-1 + 2n-1-1=2n-1 2.1 遞歸遞歸 分治法的基本思想分治法的基本思想 分而治之方法與軟件設(shè)計(jì)的模塊化方法非常分而治之方法與軟件設(shè)計(jì)的模塊化方法非常 相似。為了解決一個(gè)大的問題，可以：相似。為了解決一個(gè)大的問題，可以： 1

7、) 把它分成兩個(gè)或多個(gè)更小的問題；把它分成兩個(gè)或多個(gè)更小的問題； 2) 分別解決每個(gè)小問題；分別解決每個(gè)小問題； 3) 把各小問題的解答組合起來，即可得到原把各小問題的解答組合起來，即可得到原 問題的解答。小問題通常與原問題相似，問題的解答。小問題通常與原問題相似， 可以遞歸地使用分而治之策略來解決?？梢赃f歸地使用分而治之策略來解決。 例例2-6 在在9,12,15,27,39中分別查找中分別查找27，12，14 9 12 15 27 39 0 1 2 3 4 left right mid mid = (left+right)/2 =(0+4)/2=2 mid =(3+4)/2=3 9 12

8、15 27 39 left right mid 查找查找27成功返成功返 回回3， leftright mid 9 12 15 27 39 leftright template BinarySearch( , ) /在在a0=a1=amiddle) left= ; else right= ; return 1; /未找到未找到x 當(dāng)當(dāng)n1時(shí)，時(shí)，Tw(n)= Tw(n/2)+1, T(1) = 1 Tw(n) = Tw(n/2) + 1 = Tw(n/4) +1 +1 =Tw(1)+1+.+1=1+k=1+logn 二分搜索的時(shí)間復(fù)雜度 最壞情況下的成功檢索計(jì)算時(shí)間最壞情況下的成功檢索計(jì)算時(shí)間

9、(logn) 最壞情況下的不成功檢索計(jì)算時(shí)間最壞情況下的不成功檢索計(jì)算時(shí)間(logn) 最好情況下的成功檢索計(jì)算時(shí)間最好情況下的成功檢索計(jì)算時(shí)間(1) 最好情況下的不成功檢索計(jì)算時(shí)間最好情況下的不成功檢索計(jì)算時(shí)間(logn) 每種不成功的檢索時(shí)間都為每種不成功的檢索時(shí)間都為(logn) 2.2二分搜索技術(shù)二分搜索技術(shù) 作業(yè)： 1. P34，2-2 中第二個(gè)和第中第二個(gè)和第 五個(gè)算法的正確性，錯(cuò)誤五個(gè)算法的正確性，錯(cuò)誤 的說明原因或者給出反例的說明原因或者給出反例 2. P35, 2-3 2-3： 二分搜索中當(dāng)程序停止時(shí)，左右指針或者指 向同一個(gè)元素，此時(shí)該元素等于待查找元 素 或者left=r

10、ight+1，此時(shí)right指向的為比待找 元素小的元素，left為比待找元素大的元素 歸并排序主程序偽代碼歸并排序主程序偽代碼 template void MergeSort(Type a , int left, int right) / Aleft:right是一個(gè)全程數(shù)組，含有是一個(gè)全程數(shù)組，含有 right-left+1個(gè)待排個(gè)待排 序的元素。序的元素。 if ( ) /至少有至少有2個(gè)元素個(gè)元素 int mid = (left+right)/2; /求當(dāng)前數(shù)組的分割點(diǎn)求當(dāng)前數(shù)組的分割點(diǎn) MergeSort(a，left, mid); MergeSort(a，mid+1, right)

11、; Merge(a，b，left, mid ,right); copy（a，b，left，right）；）； left right 遞歸調(diào)用，分別對(duì)分遞歸調(diào)用，分別對(duì)分 解出來的兩個(gè)子問題解出來的兩個(gè)子問題 排序排序 合并兩個(gè)排好序的子合并兩個(gè)排好序的子 問題，放入另一個(gè)數(shù)問題，放入另一個(gè)數(shù) 組組b中中 2.4合并排序合并排序 考慮數(shù)組a的兩段為1, 7, 8, 9和2, 3, 4, 5 1,7,8,92,3,4,5 1,7,8,92,3,4,5 1 1,2 1,7,8,92,3,4,5 1,2,3 1,7,8,92,3,4,5 1,2,3,4 1,7,8,92,3,4,5 1,2,3,4,5

12、 數(shù)組數(shù)組a的兩部分的兩部分 數(shù)組數(shù)組b 1,2,3,4,5,7 1,2,3,4,5,7,8 1,2,3,4,5, 7,8,9 在移動(dòng)掃描指針的同時(shí)，在移動(dòng)掃描指針的同時(shí)， 要判斷其是否已經(jīng)到達(dá)數(shù)要判斷其是否已經(jīng)到達(dá)數(shù) 組的尾部，如到達(dá)，則停組的尾部，如到達(dá)，則停 止掃描，把未參加排序的止掃描，把未參加排序的 數(shù)全部放入備用數(shù)組中數(shù)全部放入備用數(shù)組中 2.4合并排序合并排序 合并函數(shù) template void Merge( Type a , Type b , int l, int m, int r) /合并合并al:m和和am+1:r到到bl:r int i=l; j=m+1, k=l; w

13、hile( ( ) q=r; q+ ) b k+ =a q ; else for( int q=I; q=m; q+) b k+ =a q ; 把把a(bǔ)l:m和和 am+1:r中的數(shù)中的數(shù) 據(jù)進(jìn)行比較，按順據(jù)進(jìn)行比較，按順 序放入序放入b中中 如果前一段數(shù)據(jù)如果前一段數(shù)據(jù) 小于后一段的多，小于后一段的多， 則先排完，把后則先排完，把后 段剩余數(shù)賦給段剩余數(shù)賦給 bn,否則將前段否則將前段 數(shù)據(jù)賦給數(shù)據(jù)賦給bn 前半段指針前半段指針 后半段指針后半段指針 數(shù)組數(shù)組b的下標(biāo)指針的下標(biāo)指針 i=m j=r 2.4合并排序合并排序 作業(yè) 分析分析merge函數(shù)最好與最壞的鍵值比較次函數(shù)最好與最壞的鍵值比

14、較次 數(shù)。數(shù)。 最好比較最好比較1次次 最差比較最差比較m+n-1，m和和n分別為兩段數(shù)組的長度分別為兩段數(shù)組的長度 快速排序 Template void QuickSort(Type a , int p,int r) if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1);/對(duì)左半段排序 QuickSort(a,q+1,r);/對(duì)右半段排序 a的起始位的起始位 置置 A的終止位置的終止位置 Partition函數(shù)負(fù)責(zé)將函數(shù)負(fù)責(zé)將 a進(jìn)行一次分割，返進(jìn)行一次分割，返 回分割元素的位置回分割元素的位置 快速排序問題快速排序問題 劃分程序 templat

15、e int Partition(Type a ,int p,int r) int i = , j = ; Type x = ; while( true ) while( a +i x ); if( ) break; Swap( a i , a j ); a p = ; a j = ; return j; 快速排序問題快速排序問題 p r+1 a p i = j a j x 左側(cè)掃描指針起左側(cè)掃描指針起 始始 右側(cè)掃描指針起右側(cè)掃描指針起 始始 中軸元素中軸元素 移動(dòng)左側(cè)掃描指移動(dòng)左側(cè)掃描指 針針 移動(dòng)右側(cè)掃描指針移動(dòng)右側(cè)掃描指針 算法分析算法分析 最壞情況：劃分的兩個(gè)區(qū)域分別包含最壞情況：劃分

16、的兩個(gè)區(qū)域分別包含n1 個(gè)元素和個(gè)元素和1個(gè)元素，如果每一步都出現(xiàn)這種個(gè)元素，如果每一步都出現(xiàn)這種 情況，其復(fù)雜性情況，其復(fù)雜性T(n) O(1) n1 T(n)= T(n-1)+O(n) n1 解得：解得：T(n)=O(n2) 快速排序問題快速排序問題 最好情況最好情況 每次劃分所取的基準(zhǔn)都恰好為中值，即每每次劃分所取的基準(zhǔn)都恰好為中值，即每 次劃分都產(chǎn)生兩個(gè)大小為次劃分都產(chǎn)生兩個(gè)大小為n/2的區(qū)域，的區(qū)域， O(1) n1 T(n)= 2T(n/2)+O(n) n1 T(n)=O(nlogn) 快速排序問題快速排序問題 2-19 將算法Partition中的不等號(hào)反向 第第3章章 動(dòng)態(tài)規(guī)劃

17、思想，基本要素動(dòng)態(tài)規(guī)劃思想，基本要素 矩陣連乘算法及最優(yōu)解構(gòu)造矩陣連乘算法及最優(yōu)解構(gòu)造 0-1背包問題最優(yōu)值及最優(yōu)解背包問題最優(yōu)值及最優(yōu)解 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹 （通過具體實(shí)例弄清每個(gè)算法的流程及算法（通過具體實(shí)例弄清每個(gè)算法的流程及算法 的具體實(shí)現(xiàn)）的具體實(shí)現(xiàn)） 動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法 將待求解的問題分解成若干個(gè)子問題，將待求解的問題分解成若干個(gè)子問題， 先求解子問題，并存儲(chǔ)子問題的解先求解子問題，并存儲(chǔ)子問題的解 而而避免計(jì)算重復(fù)的子問題避免計(jì)算重復(fù)的子問題，再由子，再由子 問題的解得到原問題的解。問題的解得到原問題的解。 算法思想算法思想 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基

18、本要素 1 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 2 重疊子問題性質(zhì)重疊子問題性質(zhì) 1. 最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu) 當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解 時(shí)，稱該問題具有時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 分析最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，一般假設(shè)由問題分析最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，一般假設(shè)由問題 的最優(yōu)解導(dǎo)出的子問題不是最優(yōu)的，然后的最優(yōu)解導(dǎo)出的子問題不是最優(yōu)的，然后 再設(shè)法說明在這個(gè)假設(shè)下可以構(gòu)造出一個(gè)再設(shè)法說明在這個(gè)假設(shè)下可以構(gòu)造出一個(gè) 比原問題更優(yōu)解更好的解，從而導(dǎo)出矛盾。比原問題更優(yōu)解更好的解，從而導(dǎo)出矛盾。 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素 2.重疊子問

19、題重疊子問題 在用遞歸算法自頂向下解此問題時(shí)，每次在用遞歸算法自頂向下解此問題時(shí)，每次 產(chǎn)生的子問題并不總是新問題，有些子問產(chǎn)生的子問題并不總是新問題，有些子問 題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè) 問題只解一次，而后將其解保存在一個(gè)表問題只解一次，而后將其解保存在一個(gè)表 格中，當(dāng)再次需要解此問題時(shí)，用常數(shù)時(shí)格中，當(dāng)再次需要解此問題時(shí)，用常數(shù)時(shí) 間查看一下結(jié)果。因此，用動(dòng)態(tài)規(guī)劃算法間查看一下結(jié)果。因此，用動(dòng)態(tài)規(guī)劃算法 通常只需要多項(xiàng)式時(shí)間。通常只需要多項(xiàng)式時(shí)間。 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素 都是分解成子問題，由子問題的解得到原都是分解成子問

20、題，由子問題的解得到原 問題的解。問題的解。 分治中子問題相互獨(dú)立，而動(dòng)態(tài)規(guī)劃中子分治中子問題相互獨(dú)立，而動(dòng)態(tài)規(guī)劃中子 問題互相有聯(lián)系，且存在重復(fù)計(jì)算，即存問題互相有聯(lián)系，且存在重復(fù)計(jì)算，即存 在在。 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)步驟動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)步驟 （1）找出最優(yōu)解的性質(zhì)，刻畫其結(jié)構(gòu)特征）找出最優(yōu)解的性質(zhì)，刻畫其結(jié)構(gòu)特征 （2）遞歸地定義最優(yōu)值）遞歸地定義最優(yōu)值 （3）以自底向上的方式計(jì)算出最優(yōu)值）以自底向上的方式計(jì)算出最優(yōu)值 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一 個(gè)最優(yōu)解個(gè)最優(yōu)解 矩陣連乘問題矩陣連乘問題 給定給定n個(gè)矩陣個(gè)矩陣A1, A2, , An，其中

21、，其中Ai 是是 一個(gè)一個(gè)ri-1ri 矩陣矩陣( 1in)，即，即AiAi+1是是 可乘的，求出可乘的，求出n個(gè)矩陣相乘的最優(yōu)計(jì)算個(gè)矩陣相乘的最優(yōu)計(jì)算 次序，使得計(jì)算量最小。次序，使得計(jì)算量最小。 問題提出問題提出 設(shè)三個(gè)矩陣設(shè)三個(gè)矩陣A1, A2, A3大小分別為大小分別為10100， 1005，550，考慮，考慮(A1( A2 A3), (A1A2) A3的的 結(jié)果與相乘的次數(shù)。結(jié)果與相乘的次數(shù)。 最優(yōu)子結(jié)構(gòu)特征最優(yōu)子結(jié)構(gòu)特征 計(jì)算計(jì)算A1:n的一個(gè)最優(yōu)次序所包含的計(jì)算的一個(gè)最優(yōu)次序所包含的計(jì)算 矩陣子鏈矩陣子鏈A1:k和和Ak+1:n的次序也是最優(yōu)的次序也是最優(yōu) 的的 矩陣連乘積計(jì)算次

22、序問題的最優(yōu)解包含著矩陣連乘積計(jì)算次序問題的最優(yōu)解包含著 其子問題的最優(yōu)解，也就是最優(yōu)子結(jié)構(gòu)性其子問題的最優(yōu)解，也就是最優(yōu)子結(jié)構(gòu)性 質(zhì)。質(zhì)。 矩陣連乘問題矩陣連乘問題 考慮考慮A1:k 和和Ak+1:n相乘所需的相乘所需的 計(jì)算量，計(jì)算量，A i: k 和和A k+1:j 相乘呢相乘呢 A1:k 的結(jié)果為的結(jié)果為r0*rk的的 矩陣，矩陣，Ak+1:n的結(jié)果的結(jié)果 為為rk*rn的矩陣，則它們的矩陣，則它們 相乘的計(jì)算量為相乘的計(jì)算量為p0*pk*pn 2.建立遞歸關(guān)系建立遞歸關(guān)系 設(shè)計(jì)算設(shè)計(jì)算A i: j 所需的最少次數(shù)為所需的最少次數(shù)為mij,原問題的最優(yōu)原問題的最優(yōu) 解為解為m1n。 當(dāng)

23、當(dāng) i = j 時(shí)，時(shí)，A i : j = Ai ,m i i = 0,i=1,2,n。 當(dāng)當(dāng) i j 時(shí)時(shí)m i j =m i k + m k+1 j + pi-1pkpj k i, i+1, , j-1 jipppjkmkim ji jim jki jki 1min 0 1 矩陣連乘問題矩陣連乘問題 采用遞歸方法計(jì)算采用遞歸方法計(jì)算 int RecurMatrixChain( int i, int, j, int p) if ( ) return 0; int u=RecurMatrixChain(i, i)+RecurMatrixChain(i+1,j,p) +pi-1*pi*pj; s

24、ij=i; for(int k=i+1; kj; k+) int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j,p) +pi-1*pi*pj; if (tu) u=t; sij=k; return u; 參加運(yùn)算矩陣鏈起始位置參加運(yùn)算矩陣鏈起始位置 矩陣鏈終止位置矩陣鏈終止位置 i=j 取第一個(gè)斷開位取第一個(gè)斷開位 置時(shí)計(jì)算量置時(shí)計(jì)算量 記記 錄錄 當(dāng)當(dāng) 前前 斷斷 開開 位位 置置 循環(huán)取循環(huán)取k的可取的可取 斷開位置斷開位置 矩陣連乘問題矩陣連乘問題 遞歸樹遞歸樹 14 112412341344 22 342344 11 22 33 4411

25、23 1233 3344223322 33 11 22 矩陣連乘問題矩陣連乘問題 24 22 3412 3344 11 14 13 23 矩陣連乘問題矩陣連乘問題 3.計(jì)算最優(yōu)值計(jì)算最優(yōu)值 3.計(jì)算最優(yōu)值計(jì)算最優(yōu)值 置所有只有一個(gè)矩陣的矩陣鏈計(jì)算量為置所有只有一個(gè)矩陣的矩陣鏈計(jì)算量為0，即，即 mii=0， i=1,2,n。 通過上一步的結(jié)果可以得到所有矩陣鏈長度為通過上一步的結(jié)果可以得到所有矩陣鏈長度為2的的 子問題的最優(yōu)計(jì)算量。子問題的最優(yōu)計(jì)算量。 通過上兩步的結(jié)果可以得到所有矩陣鏈長度為通過上兩步的結(jié)果可以得到所有矩陣鏈長度為3的的 子問題的最優(yōu)計(jì)算量子問題的最優(yōu)計(jì)算量 矩陣連乘問題矩陣

26、連乘問題 計(jì)算計(jì)算m i j 時(shí)，只用到已計(jì)算出的時(shí)，只用到已計(jì)算出的m i k 和和 m k+1 j A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025 例例32 設(shè)要計(jì)算矩陣連乘積設(shè)要計(jì)算矩陣連乘積A1A2A3A4A5A6 , 其中各矩陣的維數(shù)分別為其中各矩陣的維數(shù)分別為 1 2 3 4 5 6 1. 2. 3. 4. 5. 6. 0 0 0 0 0 0 15750 2625 750 1000 5000 m11 + m23+p0p1p3=7875 m13=min m12 + m33 + p0p2p3=15750 93751187515125 4375

27、712510500 25005375 3500 7875 i j 3.計(jì)算最優(yōu)值計(jì)算最優(yōu)值 void MatrixChain(int p, int n, int * *m, int * *s) for (int i=1; i=n; i+) mii= ;/單個(gè)矩陣的計(jì)算量單個(gè)矩陣的計(jì)算量 for (int r=2; r=n; r+)/r為每次循環(huán)矩陣鏈的長度為每次循環(huán)矩陣鏈的長度 for (int i=1; i= ; i+) int j=i+r-1; mij= mi+1j+pi-1*pi*pj; sij=i; for (int k=i+1; kj; k+) int t= mik+ mk+1j+

28、; if (t mij) mij=t; sij=k; 矩陣連乘問題矩陣連乘問題 0 n r + 1 取第一個(gè)可取第一個(gè)可 取位置，即取位置，即 斷開位置為斷開位置為i 循環(huán)取循環(huán)取k 的可取的可取 位置位置 pi-1*pk*pj 算法復(fù)雜度算法復(fù)雜度 算法算法MatrixChain 的主要計(jì)算量取決于程的主要計(jì)算量取決于程 序中對(duì)序中對(duì)r, i 和和k 的三重循環(huán)，的三重循環(huán)， 循環(huán)體內(nèi)的計(jì)算量為循環(huán)體內(nèi)的計(jì)算量為O(1)，三重循環(huán)的總，三重循環(huán)的總 次數(shù)是次數(shù)是O(n3)，所以，算法的計(jì)算時(shí)間上界，所以，算法的計(jì)算時(shí)間上界 為為O(n3)。 4. 構(gòu)造最優(yōu)解構(gòu)造最優(yōu)解 上述算法只是明確給出了

29、矩陣最優(yōu)連乘次上述算法只是明確給出了矩陣最優(yōu)連乘次 序所用的數(shù)乘次數(shù)序所用的數(shù)乘次數(shù)m1n，并未明確給出，并未明確給出 最優(yōu)連乘次序，即完全加括號(hào)方法。但是最優(yōu)連乘次序，即完全加括號(hào)方法。但是 以以sij為元素的為元素的2 維數(shù)組卻給出了足夠的維數(shù)組卻給出了足夠的 信息。事實(shí)上，信息。事實(shí)上，sij=k說明，計(jì)算連乘積說明，計(jì)算連乘積 Ai:j的最佳方式應(yīng)該在矩陣的最佳方式應(yīng)該在矩陣Ak 和和Ak+1 之之 間斷開，即最優(yōu)加括號(hào)方式為間斷開，即最優(yōu)加括號(hào)方式為 (Ai:k)(Ak+1:j)。 1 2 3 4 5 6 10 1 1 3 3 3 2 0 2 3 3 3 3 0 3 3 3 4 0

30、4 5 5 0 5 6 0 考慮計(jì)算考慮計(jì)算A16時(shí)的順序時(shí)的順序 S16 (A1A3) (A4A6) S13 A1(A2A3) S46 (A4A5) A6 S11=0 S23=0 A1(A2)(A3) S22= S33= 0 S66=0 S45=0 (A4)(A5) A6 S44= S55= 0 根據(jù)最優(yōu)值算法構(gòu)造最優(yōu)解根據(jù)最優(yōu)值算法構(gòu)造最優(yōu)解 Void Traceback(int i, int j, int * * s) if (i=j) return; Traceback(i, sij, s); Traceback(sij+1, j, s); cout “Multiply A” i “,

31、” sij; cout “and A” (sij +1) “,” j; endl; 調(diào)用調(diào)用Traceback(1, n, s)即可得到即可得到A1:n 作業(yè)作業(yè) 1 當(dāng)當(dāng)A1 A2 A3 A4 A5 分別為分別為2025， 2510， 105，515，1520的矩陣時(shí)，填寫相的矩陣時(shí)，填寫相 應(yīng)的應(yīng)的mij和和sij，并給出最優(yōu)計(jì)算次序。，并給出最優(yōu)計(jì)算次序。 備忘錄方法備忘錄方法 用一個(gè)表格來保存已解決的子問題的答案，用的用一個(gè)表格來保存已解決的子問題的答案，用的 時(shí)候查表即可。時(shí)候查表即可。 采用的遞歸方式是采用的遞歸方式是自頂向下自頂向下，動(dòng)態(tài)規(guī)劃是，動(dòng)態(tài)規(guī)劃是自低向自低向 上上 控制

32、結(jié)構(gòu)與直接遞歸相同，區(qū)別在于備忘錄方式控制結(jié)構(gòu)與直接遞歸相同，區(qū)別在于備忘錄方式 為每個(gè)解過的子問題建立備忘錄。為每個(gè)解過的子問題建立備忘錄。 初始化為每個(gè)子問題的記錄存入一個(gè)特殊的值，初始化為每個(gè)子問題的記錄存入一個(gè)特殊的值， 表示并未求解。在求解過程中，查看相應(yīng)記錄如表示并未求解。在求解過程中，查看相應(yīng)記錄如 果是特殊值，表示未求解，否則只要取出該子問果是特殊值，表示未求解，否則只要取出該子問 題的解答即可。題的解答即可。 動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素 備忘錄方法解矩陣乘備忘錄方法解矩陣乘 int MemoizedMatrixChain(int n,int *m,int *

33、s) for(int i=1;i=n;i+) for(int j=i;j0) return mij; if(i=j) return 0; int u=LookupChain(i,i)+LookupChain(i+1,j) +pi-1*pk*pj; sij=i; for(int k=i+1;kj;k+) int t=LookupChain(i,k) +LookupChain(k+1,j) +pi-1*pk*pj; if(t0，其價(jià)值為，其價(jià)值為vi0，背包的容量為，背包的容量為c。問。問 應(yīng)如何選擇裝入背包中的物品，使得裝入應(yīng)如何選擇裝入背包中的物品，使得裝入 背 包 中 物 品 的 總 價(jià) 值

34、 最 大 ？背 包 中 物 品 的 總 價(jià) 值 最 大 ？ 要求一組數(shù)要求一組數(shù)i (i = 0 = 0 或或，i = 0= 0表示表示物體物體不放入背包，不放入背包，i 1表示把表示把物體物體放入背包），放入背包）， 使得使得 vixi 最大，即將盡量多的價(jià)值裝入背包。最大，即將盡量多的價(jià)值裝入背包。 1 i n 1. 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 證明證明0/1 背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 即若背包容量為即若背包容量為c時(shí)，時(shí)，(y1, y2, yn )為待選物品為為待選物品為1到到n時(shí)時(shí) knap(1, n, c)的最優(yōu)解，則的最優(yōu)解，則(y2, yn )將是物

35、品將是物品1作出作出 選 擇 后 的 子 問 題選 擇 后 的 子 問 題 的 最 優(yōu) 解的 最 優(yōu) 解 當(dāng)?shù)谝粋€(gè)物品做出決策后，有兩種狀態(tài)當(dāng)?shù)谝粋€(gè)物品做出決策后，有兩種狀態(tài) y1=0，則背包容量沒有影響，則背包容量沒有影響，(y2, yn )是是 的最優(yōu)解的最優(yōu)解 y1=1，則背包減少，則背包減少w1，價(jià)值增長，價(jià)值增長v1，(y2, yn )是是 的最優(yōu)解的最優(yōu)解 x1 vixi knap(2, n, c- w1*y1) knap(2, n,c) knap(2, n,c w1) 2.遞歸關(guān)系 設(shè)背包問題的子問題的最優(yōu)值為設(shè)背包問題的子問題的最優(yōu)值為m( i, j ),即即m( i, j)是

36、背是背 包容量為包容量為j，可選擇物品為，可選擇物品為i，i1，, n時(shí)的最優(yōu)值。時(shí)的最優(yōu)值。 當(dāng)選擇第當(dāng)選擇第i個(gè)物品時(shí)，個(gè)物品時(shí)， 。 如果不選擇第如果不選擇第i個(gè)物品，則個(gè)物品，則 。 由問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，我們可以建立計(jì)算由問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，我們可以建立計(jì)算m( i, j)的遞歸式如的遞歸式如 下：下： i iii wjjim wjvwjimjim jim 0), 1( ), 1(), 1(max ),( n nn wj wjv jnm 00 ),( m( i, j) = m(i + 1, j - wi) + vi m( i, j) = m(i + 1, j) 例例: 四個(gè)物品，

37、背包容積為四個(gè)物品，背包容積為5，w4=2, 1, 3, 2，v4=12, 10, 20, 15，求最大價(jià)值，求最大價(jià)值m1c及選取的物品編號(hào)及選取的物品編號(hào) 4 3 2 1 432105 0 0 0 0 0 10 15 15 15 1515 15 2020 35 353025 37 i j n nn wj wjv jnm 00 ),( i iii wjjim wjvwjimjim jim 0), 1( ), 1(), 1(max ),( x4 X3 X2 X1 1 m15m25 所以物品所以物品1被選被選 c w1= 3,查看查看 m23m33 1 j w2= 2,查看查看 m32=m42

38、0 查看查看m420 1 3.算法描述 template void Knapsack(Type v, int w, int c, int n, Type *m) int jMax = min( wn - 1, c ); for( int j = 0; j = jMax; j + )/出口出口 m n j = ; for( int j = wn; j 1; i - ) jMax = min( w i - 1, c ); for(int j = 0; j = jMax; j +) m i j = ; for(int j = w i ; j = w1 ) m1c=max(m1c,m2c-w1+v1)

39、; 0 vn m i+1 j m 2 c 初始化初始化mnj 只剩下第一個(gè)物品只剩下第一個(gè)物品 時(shí)，如果剩余背包時(shí)，如果剩余背包 容積大于容積大于w1時(shí)，時(shí)， 要進(jìn)行選擇要進(jìn)行選擇 m15 m25 4 3 2 1 432105 0 0 0 0 0 10 10 15 15 1515 15 2020 35 353025 37 i j 構(gòu)造最優(yōu)解 x1=1 c= 5- w1=3 m23 m33x2=1 c= 3- w2=2 m32 = m42x3=0 c= 2 m42 0 x4=1 構(gòu)造最優(yōu)解 Template Void Traceback(Type *m,int w,int c,int n,int

40、 x) for(int i=1;i2n時(shí)，算法需要時(shí)，算法需要(n2n) n=3, (w1, w2, w3)=(2, 3, 4), v1, v2, v3=(1, 2, 5), c=5 3-4 錢幣問題 3.5 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹 Optimal Binary Search Trees 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹 利用動(dòng)態(tài)規(guī)劃構(gòu)造對(duì)標(biāo)識(shí)符集合利用動(dòng)態(tài)規(guī)劃構(gòu)造對(duì)標(biāo)識(shí)符集合 a1, a2, , an的的最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹算法算法包包 括括成功檢索成功檢索和和不成功檢索不成功檢索）。）。 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹 3、最優(yōu)二叉搜索樹問題、最優(yōu)二叉搜索樹問題 對(duì)于有序集對(duì)于有序

41、集S及其存取概率分布及其存取概率分布 （a0, b1, a1, , bn, an），在所有表示有序集），在所有表示有序集 S的二叉搜索樹中找出一棵具有最小平均路的二叉搜索樹中找出一棵具有最小平均路 長的二叉搜索樹。長的二叉搜索樹。 結(jié)點(diǎn)在二叉搜索樹中的層次越深，需要比結(jié)點(diǎn)在二叉搜索樹中的層次越深，需要比 較的次數(shù)就越多，因此要構(gòu)造一棵最小二較的次數(shù)就越多，因此要構(gòu)造一棵最小二 叉樹，一般盡量把搜索概率較高的結(jié)點(diǎn)放叉樹，一般盡量把搜索概率較高的結(jié)點(diǎn)放 在較高的層次。在較高的層次。 最優(yōu)二叉搜索樹問題最優(yōu)二叉搜索樹問題 4、最優(yōu)子結(jié)構(gòu)性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì) 假設(shè)選擇假設(shè)選擇 k為樹根，則為樹根，則

42、1, 2, , k-1 和和a0, a1, , ak-1 都將位于左子樹都將位于左子樹 L 上，其余上，其余 結(jié)點(diǎn)結(jié)點(diǎn) (k+1, , n 和和 ak, ak+1, , an)位于位于 右子樹右子樹 R 上。上。 k L R 1, 2, , k-1 a0, a1, , ak-1 k+1, , n ak, ak+1, , an 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 4、最優(yōu)子結(jié)構(gòu)性質(zhì)、最優(yōu)子結(jié)構(gòu)性質(zhì) 二叉搜索樹二叉搜索樹T 的一棵含有頂點(diǎn)的一棵含有頂點(diǎn)xi , , xj和葉頂點(diǎn)和葉頂點(diǎn) (xi-1 , xi ) , , ( xj , xj+1)的子樹可以看作是有序集的子樹可以看作是有序集 xi , ,

43、xj 關(guān)于全集為關(guān)于全集為 xi-1 , xj 1 的一棵二叉搜索樹（ 的一棵二叉搜索樹（T 自身可自身可 以看作是有序集以看作是有序集) 。根據(jù)。根據(jù)S 的存取分布概率，在子樹的頂?shù)拇嫒》植几怕剩谧訕涞捻?點(diǎn)處被搜索到的概率是點(diǎn)處被搜索到的概率是 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) jipwpww )(pww)(pwpw r,jmli,mij r,jmm,mli,mijij 11 11 11 左子樹左子樹 的搜索的搜索 概率概率 右子樹右子樹 的搜索的搜索 概率概率 設(shè)設(shè)Tij是有序集是有序集xi , , xj關(guān)于存儲(chǔ)概率分布為關(guān)于存儲(chǔ)概率分布為ai-1, bi, , bj, aj 的一棵最優(yōu)二

44、叉搜索樹的一棵最優(yōu)二叉搜索樹 Pij ：平均路長平均路長 xm ：Tij的根頂點(diǎn)存儲(chǔ)的元素的根頂點(diǎn)存儲(chǔ)的元素 pl和和pr: 左子樹左子樹Tl和右子樹和右子樹Tr的平均路長的平均路長 xi , , xj的存儲(chǔ)概率分布為的存儲(chǔ)概率分布為ai-1, bi, , bj, aj ，其，其 中，中，ah，bk分別是下面的條件概率：分別是下面的條件概率： 構(gòu)造最優(yōu)二叉搜索樹時(shí)，可以選構(gòu)造最優(yōu)二叉搜索樹時(shí)，可以選 擇先構(gòu)造其左右子樹，使其左右擇先構(gòu)造其左右子樹，使其左右 子樹最優(yōu)，然后構(gòu)造整棵樹子樹最優(yōu)，然后構(gòu)造整棵樹 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 5、遞歸計(jì)算最優(yōu)值 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹Tij的平

45、均路長為的平均路長為pij，則所求的，則所求的 最優(yōu)值為最優(yōu)值為p1,n。由二叉樹的花費(fèi)公式。由二叉樹的花費(fèi)公式 根據(jù)最優(yōu)二叉搜索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可根據(jù)最優(yōu)二叉搜索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可 建立計(jì)算建立計(jì)算pij的遞歸式如下的遞歸式如下 初始時(shí)初始時(shí) jipwpww )(pww)(pwpw ,jk,jki,ki,kij ,jk,jkk,ki,ki,kijij 1111 1111 11 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值 記記wi,j pi,j為為m( i, j ) 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值 例 給出標(biāo)識(shí)符集給出標(biāo)識(shí)符集1, 2, 3do, if, stop存取存取 概率概率 若若P1=0.

46、5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 構(gòu)造一棵最優(yōu)二叉搜索樹構(gòu)造一棵最優(yōu)二叉搜索樹 遞歸計(jì)算最優(yōu)值遞歸計(jì)算最優(yōu)值 P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 1 q0q1 T11 w11=0.75 m11=0.75 2 q1q2 T22 w22=0.25 m22=0.25 3 q2q3 T33 w33=0.15 m33=0.15 1 2 q0 q1q2 1 2 q0 q1 q2 T12 w12=0.9 m12=0.9+ m11+m32 =1.65 w1

47、2=0.9 m12=0.9+ m10+m22 =1.15 q0 T10 w10=0.15 m10=0 q1 T21 w21=0.1 m21=0 q2 T32 w32=0.05 m32=0 q3 T43 w43=0.05 m43=0 P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 1 q0q1 T11 w11=0.75 m11=0.75 2 q1q2 T22 w22=0.25 m22=0.25 3 q2q3 T33 w33=0.15 m33=0.15 1 2 q0 q1q2 1 2 q0 q1 q2 T12 w12=0.9 m

48、12=0.9+ m11+m32 =1.65 w12=0.9 m12=0.9+ m10+m22 =1.15 2 3 q1 q2q3 2 3 q1 q2 q3 T23 w23=0. 5 m23=0.5m23=0.6 P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 1 q0q1 T11 w11=0.75 m11=0.75 2 q1q2 T22 w22=0.25 m22=0.25 3 q2q3 T33 w33=0.15 m33=0.15 1 2 q0 q1q2 1 2 q0 q1 q2 T12 w12=0.9 m12=0.9+ m1

49、1+m32 =1.65 w12=0.9 m12=0.9+ m10+m22 =1.15 2 3 q1 q2q3 2 3 q1 q2 q3 T23 w23=0. 5 m23=0.5m23=0.6 P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 T12 m12=1.15 1 2 q0 q1q2 2 3 q1 q2q3 T23 m23=0.5 2 3 q2q3 1 q0 q1 T13 W13=1 m13=1.5 2 3 q2q3 1 q0q1 m13=1.9 2 3 q2 q3 1 q0 q1 m13=2.15 P1=0.5, P2

50、=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 T12 m12=1.15 1 2 q0 q1q2 2 3 q1 q2q3 T23 m23=0.5 2 3 q2q3 1 q0 q1 T13 W13=1 m13=1.5 2 3 q2q3 1 q0q1 m13=1.9 2 3 q2 q3 1 q0 q1 m13=2.15 P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05 0123 1 2 3 0 0 0 0 4 0 1 2 3 1 2 3 4 W(i, j) 0 1 2 3 1 2

51、3 4 0 0 0 0 0.15 0.1 0.05 0.05 0.75 0.75 1 0.25 0.15 0.25 0.15 2 3 0.9 1.15 1 0.35 10. 5 2 1.5 1 m(i, j) s(i, j) void OptimalBinarySearchTree( int a, int b,int n, int *m, int *s, int *w) for( int i=0; i=n; i+) wi+1i=ai; mi+1i=0; for(int r=0; rn; r+) for(int i =1; i= n - r; i+) int j= j + r; wij=wij-

52、1+aj+bj; mij=mi+1j; sij = i; for(int k = i+1; k=j; k+) int t=mik-1+mk+1j; if (tmij) mij=t; sij=k; mij+=wij; 初始化初始化 對(duì)角線賦值對(duì)角線賦值 i為起始元素下標(biāo)為起始元素下標(biāo) j為終止元素下標(biāo)為終止元素下標(biāo) 加第加第j個(gè)結(jié)點(diǎn)后，個(gè)結(jié)點(diǎn)后， 權(quán)值權(quán)值w改變改變 如第如第i個(gè)結(jié)點(diǎn)作根的個(gè)結(jié)點(diǎn)作根的 值值 取第取第k個(gè)結(jié)點(diǎn)作根個(gè)結(jié)點(diǎn)作根 練習(xí)練習(xí) 設(shè)設(shè)n=4，且，且 (1, 2, 3, 4) = (do, if, read, while)。 又設(shè)又設(shè)b(1 : 4)=(3, 3, 1, 1)和

53、和a(0 : 4)=(2,3,1,1,1) (這些這些b,a都乘了都乘了16。) 寫出數(shù)組寫出數(shù)組wij,mij,sij及最后的最優(yōu)及最后的最優(yōu) 二叉搜索樹二叉搜索樹 作業(yè) P84 3-15 第第4章章 貪心算法的基本要素，思想，與動(dòng)態(tài)規(guī)劃貪心算法的基本要素，思想，與動(dòng)態(tài)規(guī)劃 的區(qū)別聯(lián)系的區(qū)別聯(lián)系 活動(dòng)安排問題活動(dòng)安排問題 最優(yōu)裝載最優(yōu)裝載 單源最短路徑單源最短路徑 多機(jī)調(diào)度問題多機(jī)調(diào)度問題 什么是貪心方法什么是貪心方法 如果硬幣面值為如果硬幣面值為1角角1分分、7分分、5分分、和、和1分分。 要找給顧客要找給顧客2角角6分分錢，錢， 按貪心方法找出的硬幣個(gè)數(shù)是：按貪心方法找出的硬幣個(gè)數(shù)是：2

54、個(gè)個(gè)1角角1分分 和四個(gè)和四個(gè)1分，共分，共6枚，枚， 這比這比1個(gè)個(gè)1角角1分和分和3個(gè)個(gè)5分多了分多了2枚；因此，枚；因此， 從從局部的最優(yōu)選擇局部的最優(yōu)選擇得到的解得到的解并不總是問題并不總是問題 的最優(yōu)解的最優(yōu)解。 貪心算法貪心算法總是作出在當(dāng)前看來最好的選擇?？偸亲鞒鲈诋?dāng)前看來最好的選擇。 也就是說貪心算法也就是說貪心算法并不從整體最優(yōu)并不從整體最優(yōu)考慮，它所考慮，它所 作出的選擇只是在某種意義上的作出的選擇只是在某種意義上的局部最優(yōu)選擇局部最優(yōu)選擇。 當(dāng)然，當(dāng)然，希望希望貪心算法得到的最終結(jié)果也是整體貪心算法得到的最終結(jié)果也是整體 最優(yōu)的。最優(yōu)的。 雖然貪心算法不能對(duì)所有問題都得到

55、整體最優(yōu)雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu) 解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單 源最短路徑問題，最小生成樹問題等。源最短路徑問題，最小生成樹問題等。 在一些情況下，即使貪心算法不能得到整體最在一些情況下，即使貪心算法不能得到整體最 優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。 貪心算法通過一系列的選擇來得到一個(gè)問貪心算法通過一系列的選擇來得到一個(gè)問 題的解。它所做的每一個(gè)選擇都是當(dāng)前狀題的解。它所做的每一個(gè)選擇都是當(dāng)前狀 態(tài)下某種意義的最好選擇，即貪心選擇。態(tài)下某種意義的最好選擇，即貪心選擇。 希望通過每次所做

56、的選擇導(dǎo)致最終結(jié)果是希望通過每次所做的選擇導(dǎo)致最終結(jié)果是 問題的一個(gè)最優(yōu)解。問題的一個(gè)最優(yōu)解。 希望從希望從局部的最優(yōu)選擇局部的最優(yōu)選擇得到得到整體最優(yōu)解整體最優(yōu)解。 貪心算法的基本要素貪心算法的基本要素 貪心算法的基本要素貪心算法的基本要素 貪心算法的基本要素貪心算法的基本要素 可用貪心算法求解的問題的基本要素可用貪心算法求解的問題的基本要素 用貪心算法求解的問題，具有兩個(gè)重要的性質(zhì)：用貪心算法求解的問題，具有兩個(gè)重要的性質(zhì)： 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 貪心選擇性質(zhì)貪心選擇性質(zhì)。 貪心算法的基本要素貪心算法的基本要素 1. 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 整體

57、最優(yōu)解整體最優(yōu)解包含它的包含它的子問題的最優(yōu)解子問題的最優(yōu)解。 具有具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)是一個(gè)問題可用動(dòng)態(tài)規(guī)劃是一個(gè)問題可用動(dòng)態(tài)規(guī)劃 算法或貪心算法求解的一個(gè)關(guān)鍵特征。算法或貪心算法求解的一個(gè)關(guān)鍵特征。 貪心算法的基本要素貪心算法的基本要素 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 例：例： 活動(dòng)安排問題中最優(yōu)子結(jié)構(gòu)性質(zhì)表現(xiàn)為：活動(dòng)安排問題中最優(yōu)子結(jié)構(gòu)性質(zhì)表現(xiàn)為： 若若A是對(duì)于是對(duì)于E的活動(dòng)安排問題包含活動(dòng)的活動(dòng)安排問題包含活動(dòng)1的的 一個(gè)最優(yōu)解，則相容活動(dòng)集合一個(gè)最優(yōu)解，則相容活動(dòng)集合A= A 1 是對(duì)于是對(duì)于E =iE: sif1的活動(dòng)安排問題的的活動(dòng)安排問題的 一個(gè)最優(yōu)解一個(gè)最優(yōu)解 2.

58、貪心選擇性質(zhì)貪心選擇性質(zhì) 貪心選擇性質(zhì)貪心選擇性質(zhì): 所求問題的整體最優(yōu)解可以通過一系列局所求問題的整體最優(yōu)解可以通過一系列局 部最優(yōu)的選擇來完成即貪心選擇來達(dá)到。部最優(yōu)的選擇來完成即貪心選擇來達(dá)到。 這是貪心算法可行的要素。也是貪心算法這是貪心算法可行的要素。也是貪心算法 與與動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。的主要區(qū)別。 如找顧客錢幣問題和圖的染色問題不具有如找顧客錢幣問題和圖的染色問題不具有 貪心選擇性質(zhì)貪心選擇性質(zhì)。 貪心算法的基本要素貪心算法的基本要素 3.貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 相同點(diǎn)：都具有最優(yōu)子結(jié)構(gòu)性質(zhì)相同點(diǎn)：都具有最優(yōu)子結(jié)構(gòu)性質(zhì) 區(qū)別：動(dòng)態(tài)

59、規(guī)劃算法每步所作的選擇往往區(qū)別：動(dòng)態(tài)規(guī)劃算法每步所作的選擇往往 依賴于相關(guān)子問題的解。只有解出相關(guān)子依賴于相關(guān)子問題的解。只有解出相關(guān)子 問題才能作出選擇。問題才能作出選擇。 貪心算法僅在當(dāng)前狀態(tài)下作出最好選擇，貪心算法僅在當(dāng)前狀態(tài)下作出最好選擇， 即局部最優(yōu)選擇，但不依賴于子問題的解即局部最優(yōu)選擇，但不依賴于子問題的解 貪心：自頂向下貪心：自頂向下 動(dòng)態(tài)規(guī)劃：自低向上動(dòng)態(tài)規(guī)劃：自低向上 貪心算法的基本要素貪心算法的基本要素 貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 對(duì)于一個(gè)具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用對(duì)于一個(gè)具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用 貪心算法還是動(dòng)態(tài)規(guī)劃算法？貪心算法還是

60、動(dòng)態(tài)規(guī)劃算法？ 是不是能用動(dòng)態(tài)規(guī)劃算法求解的問題也能是不是能用動(dòng)態(tài)規(guī)劃算法求解的問題也能 用貪心算法來求解？用貪心算法來求解？ 活動(dòng)安排問題活動(dòng)安排問題 已知已知n個(gè)活動(dòng)個(gè)活動(dòng) E = 1, 2, , n 要求使用同要求使用同 一資源，第一資源，第k個(gè)活動(dòng)要求的開始和結(jié)束時(shí)間個(gè)活動(dòng)要求的開始和結(jié)束時(shí)間 為為sk , fk , 其中其中sk fk , k = 1, 2, , n ?；顒?dòng)?；顒?dòng)k 與活動(dòng)與活動(dòng)j稱為相容的如果稱為相容的如果sk fj 或者或者sj fk。 活動(dòng)安排問題就是要在所給的活動(dòng)集合中活動(dòng)安排問題就是要在所給的活動(dòng)集合中 選出最大的相容活動(dòng)子集。選出最大的相容活動(dòng)子集。 問題