第3章_動(dòng)態(tài)規(guī)劃2016all

1、1動(dòng)態(tài)規(guī)劃算法的基本要素動(dòng)態(tài)規(guī)劃算法的基本要素舉例舉例1 1 矩陣連乘問(wèn)題矩陣連乘問(wèn)題舉例舉例2 2 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分舉例舉例3 3 最長(zhǎng)公共子序列最長(zhǎng)公共子序列舉例舉例4 4 多段圖的最短路徑問(wèn)題多段圖的最短路徑問(wèn)題舉例舉例5 0-15 0-1背包問(wèn)題背包問(wèn)題舉例舉例6 6 資源分配問(wèn)題資源分配問(wèn)題多階段決策問(wèn)題多階段決策問(wèn)題多階段決策過(guò)程：多階段決策過(guò)程：?jiǎn)栴}的活動(dòng)過(guò)程分為若干相互聯(lián)問(wèn)題的活動(dòng)過(guò)程分為若干相互聯(lián)系的階段，任一階段系的階段，任一階段i以后的行為僅依賴(lài)于以后的行為僅依賴(lài)于i階段階段的過(guò)程狀態(tài)，而與的過(guò)程狀態(tài)，而與i階段之前的過(guò)程如何達(dá)到這種階段之前的過(guò)程

2、如何達(dá)到這種狀態(tài)的方式無(wú)關(guān)。在每一個(gè)階段都要做出決策，狀態(tài)的方式無(wú)關(guān)。在每一個(gè)階段都要做出決策，這一系列的決策稱(chēng)為多階段決策過(guò)程這一系列的決策稱(chēng)為多階段決策過(guò)程(multistep decision process) 。 最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題：?jiǎn)栴}的每一階段可能有多種可供選擇問(wèn)題的每一階段可能有多種可供選擇的決策，必須從中選擇一種決策。各階段的決策的決策，必須從中選擇一種決策。各階段的決策構(gòu)成一個(gè)決策序列。決策序列不同，所導(dǎo)致的問(wèn)構(gòu)成一個(gè)決策序列。決策序列不同，所導(dǎo)致的問(wèn)題的結(jié)果可能不同。題的結(jié)果可能不同。 多階段決策的最優(yōu)化問(wèn)題多階段決策的最優(yōu)化問(wèn)題：求能夠獲得問(wèn)題最優(yōu)解：求能夠獲得問(wèn)題最

3、優(yōu)解的決策序列的決策序列最優(yōu)決策序列。最優(yōu)決策序列。22022-3-1731）枚舉法）枚舉法 窮舉窮舉可能的決策序列，從中選取可以獲得最優(yōu)解的決策序列可能的決策序列，從中選取可以獲得最優(yōu)解的決策序列2）動(dòng)態(tài)規(guī)劃）動(dòng)態(tài)規(guī)劃 20世紀(jì)世紀(jì)50年代初美國(guó)數(shù)學(xué)家年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理最優(yōu)化原理(principle of optimality)，把，把多階段多階段過(guò)程轉(zhuǎn)化為一系列過(guò)程轉(zhuǎn)化為一系列單階段單階段問(wèn)題，創(chuàng)立了解決這問(wèn)題，創(chuàng)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法類(lèi)過(guò)程優(yōu)化問(wèn)題的

4、新方法動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃(dynamic programming)是是運(yùn)籌學(xué)運(yùn)籌學(xué)的一個(gè)分支，是求解的一個(gè)分支，是求解決策過(guò)程決策過(guò)程(decision process)最優(yōu)化的數(shù)學(xué)方法。最優(yōu)化的數(shù)學(xué)方法。 應(yīng)用領(lǐng)域：動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技應(yīng)用領(lǐng)域：動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題，用動(dòng)態(tài)規(guī)劃方法比用其它資源分配、設(shè)備更新、排序、裝載等問(wèn)題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。方法

5、求解更為方便。多階段決策過(guò)程的求解策略多階段決策過(guò)程的求解策略2022-3-174多階段決策問(wèn)題多階段決策問(wèn)題n多階段決策過(guò)程多階段決策過(guò)程 多階段決策過(guò)程是活動(dòng)過(guò)程可按時(shí)間或空間順序分解成若干相互獨(dú)立、相互聯(lián)系的階段，在每個(gè)階段的狀態(tài)下做出決策，整個(gè)過(guò)程的決策構(gòu)成一個(gè)決策序列，則稱(chēng)多階段決策過(guò)程為序貫決策過(guò)程。稱(chēng)問(wèn)題為多階段決策問(wèn)題。狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5決策2決策3決策4決策1q 多階段決策問(wèn)題的特點(diǎn)多階段決策問(wèn)題的特點(diǎn) 過(guò)程可分為若干個(gè)相互聯(lián)系的階段；每一階段都對(duì)應(yīng)著一組可供選擇的決策；每一決策的選定即依賴(lài)于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。2022-3-175第第1階段階段

6、第第2階段階段第第3階段階段第第4階段階段狀狀態(tài)態(tài)1狀狀態(tài)態(tài)2狀狀態(tài)態(tài)4狀狀態(tài)態(tài)5狀狀態(tài)態(tài)3決決策策1決決策策2決決策策4決決策策3q 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 把多階段過(guò)程的問(wèn)題轉(zhuǎn)化為一系列單階段的問(wèn)題，逐個(gè)階段求解的最優(yōu)化數(shù)學(xué)方法。6 動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想基本思想是將是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。待求解問(wèn)題分解成若干個(gè)子問(wèn)題。n nn/4n/4n/4n/4n/4n/4n/4n/4區(qū)別區(qū)別：經(jīng)分解得到的子問(wèn)題往往不是互相：經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立獨(dú)立的。的。問(wèn)題問(wèn)題：用分治法求解，有些子問(wèn)題被重復(fù)計(jì)算多次。：用分治法求解，有些子問(wèn)題被重復(fù)計(jì)算

7、多次。7 保存已解決的子問(wèn)題的答案，在需要時(shí)找出已保存已解決的子問(wèn)題的答案，在需要時(shí)找出已求得的答案，以避免大量的重復(fù)計(jì)算，從而得求得的答案，以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。這就是到多項(xiàng)式時(shí)間算法。這就是動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法。算法。 在算法中用表格來(lái)保存已經(jīng)求解的子問(wèn)題的解，在算法中用表格來(lái)保存已經(jīng)求解的子問(wèn)題的解，無(wú)論它是否會(huì)被用到。當(dāng)以后遇到該子問(wèn)題時(shí)無(wú)論它是否會(huì)被用到。當(dāng)以后遇到該子問(wèn)題時(shí)即可查表取出其解，避免了重復(fù)計(jì)算。即可查表取出其解，避免了重復(fù)計(jì)算。解決方法解決方法算法設(shè)計(jì)與分析8動(dòng)態(tài)規(guī)劃的基本要素動(dòng)態(tài)規(guī)劃的基本要素n最優(yōu)子結(jié)構(gòu)：?jiǎn)栴}的最優(yōu)解是由其子問(wèn)題的最優(yōu)解所構(gòu)成

8、的。n重疊子問(wèn)題：子問(wèn)題之間并非相互獨(dú)立的，而是彼此有重疊的。最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠以自底向上的方式遞歸地從子結(jié)構(gòu)的最優(yōu)解構(gòu)造出問(wèn)題的最優(yōu)解。因?yàn)樽訂?wèn)題重疊，所以存在著重復(fù)計(jì)算。這樣就可以用填表保存子問(wèn)題解的方法來(lái)提高效率。9n找出最優(yōu)解的性質(zhì)，并描述其結(jié)構(gòu)特征。找出最優(yōu)解的性質(zhì)，并描述其結(jié)構(gòu)特征。n遞歸地定義最優(yōu)值。遞歸地定義最優(yōu)值。n以自底向上的方式計(jì)算出最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。n根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。n步驟步驟13是動(dòng)態(tài)規(guī)劃算法的基本步驟。若需要最優(yōu)是動(dòng)態(tài)規(guī)劃算法的基本步驟。若需要最優(yōu)解，則必須執(zhí)行第解，則必須執(zhí)行

9、第4步，步，為此還需要在第為此還需要在第3步中記錄步中記錄構(gòu)造最優(yōu)解所必需的信息。構(gòu)造最優(yōu)解所必需的信息。動(dòng)態(tài)規(guī)劃算法的基本步驟動(dòng)態(tài)規(guī)劃算法的基本步驟算法設(shè)計(jì)與分析10動(dòng)態(tài)規(guī)劃的備忘錄方法動(dòng)態(tài)規(guī)劃的備忘錄方法n動(dòng)態(tài)規(guī)劃中采用自底向上的方式。但是在遞歸動(dòng)態(tài)規(guī)劃中采用自底向上的方式。但是在遞歸定義中往往是自上而下的描述。備忘錄方法就定義中往往是自上而下的描述。備忘錄方法就采用與遞歸定義一致的自上而下的方式。采用與遞歸定義一致的自上而下的方式。n備忘錄方法同樣用表格來(lái)保存已解子問(wèn)題的信備忘錄方法同樣用表格來(lái)保存已解子問(wèn)題的信息。每個(gè)子問(wèn)題初始化時(shí)都標(biāo)記為尚未求解。息。每個(gè)子問(wèn)題初始化時(shí)都標(biāo)記為尚未求

10、解。在遞歸求解過(guò)程中，對(duì)每個(gè)待解子問(wèn)題，先查在遞歸求解過(guò)程中，對(duì)每個(gè)待解子問(wèn)題，先查看它是否已求解。若未求解，則計(jì)算其解并填看它是否已求解。若未求解，則計(jì)算其解并填表保存。若已求解，則查表取出相應(yīng)的結(jié)果。表保存。若已求解，則查表取出相應(yīng)的結(jié)果。n備忘錄方法同樣避免了子問(wèn)題的重復(fù)計(jì)算，因備忘錄方法同樣避免了子問(wèn)題的重復(fù)計(jì)算，因而和動(dòng)態(tài)規(guī)劃算法具有同樣效率。而和動(dòng)態(tài)規(guī)劃算法具有同樣效率。11動(dòng)態(tài)規(guī)劃算法舉例動(dòng)態(tài)規(guī)劃算法舉例1 1：矩陣連乘問(wèn)題：矩陣連乘問(wèn)題1050 A4010 B3040 C530 D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB給定給定n n個(gè)矩陣個(gè)矩陣AA1 1,

11、A,A2 2,.,A,.,An n ，其中，其中A Ai i與與A Ai+1i+1是可乘的。是可乘的。由于乘法滿(mǎn)足結(jié)合律，故計(jì)算矩陣的連乘可以有不同由于乘法滿(mǎn)足結(jié)合律，故計(jì)算矩陣的連乘可以有不同的計(jì)算次序。其計(jì)算次序可以用加括號(hào)的方式確定。的計(jì)算次序。其計(jì)算次序可以用加括號(hào)的方式確定。假設(shè)有假設(shè)有4 4個(gè)矩陣：個(gè)矩陣：A,B,C,DA,B,C,D乘法：乘法：1600016000乘法：乘法：1050010500乘法：乘法：3600036000乘法：乘法：8750087500乘法：乘法：3450034500算法設(shè)計(jì)與分析12不同計(jì)算順序的差別不同計(jì)算順序的差別n設(shè)矩陣設(shè)矩陣A1, A2和和A3分別

12、為分別為10100, 1005和和550的矩陣，現(xiàn)要計(jì)算的矩陣，現(xiàn)要計(jì)算A1A2A3 。n若按若按(A1A2)A3)來(lái)計(jì)算，則需要的數(shù)乘次數(shù)為來(lái)計(jì)算，則需要的數(shù)乘次數(shù)為101005 + 10550 = 7500n若按若按(A1(A2 A3)來(lái)計(jì)算，則需要的數(shù)乘次數(shù)為來(lái)計(jì)算，則需要的數(shù)乘次數(shù)為100 5 50+ 1010050 = 75000n后一種計(jì)算順序的計(jì)算量竟是前者的后一種計(jì)算順序的計(jì)算量竟是前者的10倍！倍！n所以，求多個(gè)矩陣的連乘積時(shí)，計(jì)算的結(jié)合所以，求多個(gè)矩陣的連乘積時(shí)，計(jì)算的結(jié)合順序是十分重要的。順序是十分重要的。13給定給定n n個(gè)矩陣個(gè)矩陣A A1 1,A,A2 2, ,A,

13、An n，其中，其中A Ai i與與A Ai+1i+1是可乘的，是可乘的，i=1i=1, ,2 ,2 , ,n-1n-1。如何確定計(jì)算矩。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積所需要的陣連乘積所需要的乘法次數(shù)最少乘法次數(shù)最少。14列舉出所有可能的計(jì)算次序，并計(jì)算出每一列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序所需要的乘法次數(shù)，從中找出一種計(jì)算次序所需要的乘法次數(shù)，從中找出一種乘法次數(shù)最少的計(jì)算次序。種乘法次數(shù)最少的計(jì)算次序。 時(shí)間復(fù)雜度分析：對(duì)于時(shí)間復(fù)雜度分析：對(duì)于n n個(gè)矩陣的連乘，設(shè)其不同的個(gè)矩陣的連乘，設(shè)其不同的計(jì)算次序?yàn)?/p>

14、計(jì)算次序?yàn)镻(n)P(n)。由于每種加括號(hào)方式都可以分解為。由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A(A1 1.A.Ak k)(A)(Ak+1k+1A An n) )可以可以得到關(guān)于得到關(guān)于P(n)P(n)的遞推式如下：的遞推式如下：結(jié)論：結(jié)論：P(n)P(n)隨隨n n的增長(zhǎng)呈指數(shù)增長(zhǎng)，不是高效算法。的增長(zhǎng)呈指數(shù)增長(zhǎng)，不是高效算法。( )( )()nknP nP k P nkn11111 115消除重復(fù)的計(jì)算消除重復(fù)的計(jì)算n要消除重復(fù)計(jì)算，可在在計(jì)算過(guò)程中保存已解要消除重復(fù)計(jì)算，可在在計(jì)算過(guò)程中保存已解決的子問(wèn)題的答案。這樣，每個(gè)子問(wèn)題只計(jì)算決的子問(wèn)

15、題的答案。這樣，每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免重復(fù)計(jì)算。避免重復(fù)計(jì)算。n計(jì)算方式可依據(jù)遞歸式自底向上地進(jìn)行。計(jì)算方式可依據(jù)遞歸式自底向上地進(jìn)行。n注意到在此問(wèn)題中，注意到在此問(wèn)題中，不同的有序?qū)Σ煌挠行驅(qū)?(i, j)就對(duì)應(yīng)就對(duì)應(yīng)不同的子問(wèn)題，因此不同的子問(wèn)題，因此不同的子問(wèn)題個(gè)數(shù)個(gè)數(shù)最不同的子問(wèn)題個(gè)數(shù)個(gè)數(shù)最多只有多只有Cn2+ n = (n2)個(gè)。個(gè)。n這樣便可以得到多項(xiàng)式時(shí)間的算法。這樣便可以得到多項(xiàng)式時(shí)間的算法。16自底向上的計(jì)算自底向上的計(jì)算n例如對(duì)于例如對(duì)于A1A2A3A4，依據(jù)遞歸式以自底向上的依據(jù)遞歸式以自底

16、向上的方式計(jì)算出各個(gè)子問(wèn)題，其過(guò)程如下：方式計(jì)算出各個(gè)子問(wèn)題，其過(guò)程如下：m11m22m33m44m12m23m34m13m24m24其中mii = 0mii+1 = pi1pipi+1mij = minikj mik+mk+1j+pi1pkpj例如： m13 = min m11+m23+p0p1p3m12+m33+p0p2p317將矩陣連乘積將矩陣連乘積A Ai iA Ai+1i+1.A.Aj j 簡(jiǎn)記為簡(jiǎn)記為Ai:jAi:j，ijij?？疾煊?jì)算考察計(jì)算Ai:jAi:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣A Ak k和和A Ak+1k+1之間將矩陣鏈斷開(kāi)，

17、之間將矩陣鏈斷開(kāi)，ikjikj，則其相應(yīng)完全，則其相應(yīng)完全加括號(hào)方式為：加括號(hào)方式為： ( ( A Ai iA Ai+1i+1.A.Ak k）( (A Ak+1k+1A Ak+2k+2.A.Aj j ) )計(jì)算量計(jì)算量：Ai:kAi:k的計(jì)算量加上的計(jì)算量加上Ak+1:jAk+1:j的計(jì)算量，再加上的計(jì)算量，再加上Ai:kAi:k和和Ak+1:jAk+1:j相乘的計(jì)算量。相乘的計(jì)算量。 18n關(guān)鍵特征關(guān)鍵特征：計(jì)算：計(jì)算A1:nA1:n的最優(yōu)次序所包含的計(jì)的最優(yōu)次序所包含的計(jì)算矩陣子鏈算矩陣子鏈 A1:kA1:k和和Ak+1:nAk+1:n的次序也是最的次序也是最優(yōu)的。優(yōu)的。n矩陣連乘計(jì)算次序

18、問(wèn)題的最優(yōu)解包含著其子問(wèn)矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求最優(yōu)解的算法求最優(yōu)解的顯著特征。顯著特征。19 假設(shè)計(jì)算假設(shè)計(jì)算Ai:jAi:j（1ijn1ijn）所需要的最少乘法次數(shù)）所需要的最少乘法次數(shù)為為mi,jmi,j，則原問(wèn)題的最優(yōu)值為，則原問(wèn)題的最優(yōu)值為m1,nm1,n。 當(dāng)當(dāng)i=ji=j時(shí)，時(shí)，Ai:j=AAi:j=Ai i，因此，因此mi,i=0mi,i=0，i=1,2,i=1,2,n,n 當(dāng)當(dāng)ijij時(shí)，時(shí)，mij

19、=mik+mk+1j+mij=mik+mk+1j+p pi-1i-1p pk kp pj j ki,i+1,.,j-1ki,i+1,.,j-1 可以遞歸地定義可以遞歸地定義mi,jmi,j為：為：jipppjkmkimjijimjki, 1,min0,1jki20n對(duì)于對(duì)于1ijn1ijn不同的有序?qū)Σ煌挠行驅(qū)?i,j)(i,j)對(duì)應(yīng)不對(duì)應(yīng)不同的子問(wèn)題，因此不同子問(wèn)題的個(gè)數(shù)最多同的子問(wèn)題，因此不同子問(wèn)題的個(gè)數(shù)最多只有：只有： 可以看出，在遞歸計(jì)算時(shí)，有許多子問(wèn)題可以看出，在遞歸計(jì)算時(shí)，有許多子問(wèn)題被重復(fù)計(jì)算。被重復(fù)計(jì)算。)(22nnn21int recurMatrixChain(int p

20、, int i, int j) if (i=j) return 0; int u =; for (int k=i; kj; k+) int t= recurMatrixChain(p,i,k) + recurMatrixChain(p,k+1,j)+pi-1*pk*pj; if (tu) u=t; sij=k; return u;22n出現(xiàn)重復(fù)計(jì)算是該問(wèn)題用動(dòng)態(tài)規(guī)劃算法求解的出現(xiàn)重復(fù)計(jì)算是該問(wèn)題用動(dòng)態(tài)規(guī)劃算法求解的又一個(gè)顯著特征。又一個(gè)顯著特征。n用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保的方式進(jìn)行計(jì)算。在計(jì)

21、算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，在后面需要時(shí)只要簡(jiǎn)單查找一下，從而可次，在后面需要時(shí)只要簡(jiǎn)單查找一下，從而可以避免大量地重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間以避免大量地重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。的算法。23假設(shè)假設(shè)Ai的維數(shù)為的維數(shù)為pi-1pi，則輸入序列為則輸入序列為 p0, p1, p2, . ,pn pn+1 記錄每個(gè)矩陣的維數(shù)記錄每個(gè)矩陣的維數(shù);mi,j記錄記錄AiAi+1.Aj相乘的代價(jià)（乘法次數(shù)）相乘的代價(jià)（乘法次數(shù)）;si,j記錄取得最優(yōu)代價(jià)所斷開(kāi)的點(diǎn)記錄取得最優(yōu)代價(jià)所斷開(kāi)的點(diǎn)k 。24具有自底向上的計(jì)算特征：具

22、有自底向上的計(jì)算特征：如果計(jì)算如果計(jì)算mi,jmi,j，僅需要計(jì)算，僅需要計(jì)算 小于小于j-i+1j-i+1個(gè)的矩陣乘積。個(gè)的矩陣乘積。即計(jì)算長(zhǎng)度為即計(jì)算長(zhǎng)度為L(zhǎng) L的矩陣相乘代價(jià)僅依賴(lài)于小的矩陣相乘代價(jià)僅依賴(lài)于小于于L L長(zhǎng)度的矩陣相乘代價(jià)。長(zhǎng)度的矩陣相乘代價(jià)。算法思路：按照長(zhǎng)度遞增算法思路：按照長(zhǎng)度遞增(1,2, . n) (1,2, . n) 計(jì)計(jì)算算mi,jmi,j代價(jià)代價(jià)。25算法算法matrixChainmatrixChain，首先計(jì)算出，首先計(jì)算出mi,i=0,i=1,2,nmi,i=0,i=1,2,n。然后，根據(jù)遞歸式，。然后，根據(jù)遞歸式，按矩陣鏈長(zhǎng)遞增的方式依次計(jì)算：按矩陣鏈

23、長(zhǎng)遞增的方式依次計(jì)算：mimi，i+1,i=1,2,n-1,(i+1,i=1,2,n-1,(矩陣鏈長(zhǎng)度為矩陣鏈長(zhǎng)度為2 2）；）；mimi，i+2,i=1,2,n-2, (i+2,i=1,2,n-2, (矩陣鏈矩陣鏈長(zhǎng)度為長(zhǎng)度為3 3）；在計(jì)算在計(jì)算mimi，jj時(shí)，只用到已計(jì)算的時(shí)，只用到已計(jì)算的mimi，kk和和mk+1mk+1，j.j.261234567812345671234561234512341231211 2 3 4 5 6 7 812345678m長(zhǎng)度（個(gè)數(shù)）長(zhǎng)度（個(gè)數(shù)）m3,6 :m3,3+m4,6m3,4+m5,6m3,5+m6,6r27void matrixChain(i

24、nt p , int mNUM+1, int sNUM+1,int n) / n是當(dāng)前矩陣個(gè)數(shù)，是當(dāng)前矩陣個(gè)數(shù)，NUM是最大矩陣個(gè)數(shù)是最大矩陣個(gè)數(shù) 處理矩陣長(zhǎng)度為處理矩陣長(zhǎng)度為1的代價(jià)（的代價(jià)（mi,i = 0）；）； for (int r = 2; r = n; r+) /長(zhǎng)度從長(zhǎng)度從2n for (int i = 1; i mij, k-sij; ( ikj) 28void matrixChain(int p, int mNUM+1, int sNUM+1) / p數(shù)組包含數(shù)組包含n+1元素元素 for (int i = 1; i = n; i+) mii = 0; /將長(zhǎng)度為將長(zhǎng)度為1的

25、代價(jià)賦為的代價(jià)賦為0 for (int r = 2; r = n; r+) / 長(zhǎng)度從長(zhǎng)度從2n for (int i = 1; i = n - r+1; i+) / 從第從第1行開(kāi)始行開(kāi)始n-r+1行為止行為止 int j=i+r-1; mij = mii + mi+1j+ pi-1*pi*pj; / k=i, mii=0可以省略可以省略 sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 算法描述了矩陣填充的過(guò)程：r為當(dāng)前斜線起始列號(hào)（長(zhǎng)度）i控

26、制當(dāng)前斜線元素行號(hào)J控制當(dāng)前斜線元素列號(hào)29A1A2A3A4A5A630353515155510102020251137520103504375554271252053510002625543213000201535250005322min52541531521pppmmpppmmpppmmm算法復(fù)雜度分析算法復(fù)雜度分析：算法：算法matrixChainmatrixChain的主要計(jì)算量取決于算法中對(duì)的主要計(jì)算量取決于算法中對(duì)r r，i i和和k k的三重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為的三重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)O(1)，三重循環(huán)的總次數(shù)為，三重循環(huán)的總次數(shù)為O(nO(n3 3) )。因此

27、算法計(jì)算時(shí)間上界為。因此算法計(jì)算時(shí)間上界為O(nO(n3 3) )。算法占用的空間為。算法占用的空間為O(nO(n2 2) )。p0p1p2p3p4p5p63035155102025舉例：給定一個(gè)舉例：給定一個(gè)6 6個(gè)矩陣的矩陣鏈：個(gè)矩陣的矩陣鏈：30繼續(xù)分析繼續(xù)分析Void MatrixChain(int p, int n, int *m, int *s) for (int i = 1; i = n; i+) mii = 0; /將對(duì)角線元素賦值為零，即單個(gè)矩陣計(jì)算量為0 for (int r = 2; r = n; r+) for (int i = 1; i = n r +1; i+) i

28、nt j = i + r 1;(5) mij = mi+1j + pi1*pi*pj; /計(jì)算Ai, j = Ai: i Ai+1: j sij = i; /記下斷點(diǎn)i(7) for (int k = i + 1; k j; k+) int t = mik + mk+1j + pi1*pk*pj; /對(duì)ikj, 逐個(gè)計(jì)算Ai, j = Ai: k Ak+1: j if (t mij) mij = t; sij = k; /記下較小的mij及相應(yīng)的斷點(diǎn)k 第(5)步與第(7)步能否合在一起?能。此處分開(kāi)是為了給mij賦初值。算法設(shè)計(jì)與分析31 設(shè)要計(jì)算矩陣連乘積A1A2A3A4A5A6，其維數(shù)分

29、別為3535, 3515, 155, 510, 1020, 2025, 即p0=35, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。 MatrixChain用矩陣mij, sij存放子問(wèn)題Ai: j的最小計(jì)算量以及相應(yīng)的斷點(diǎn)。123456 1 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain將如下面紅色箭頭所示的過(guò)程逐個(gè)計(jì)算子問(wèn)題Ai: j：執(zhí)行for (int i = 1; i = n; i+) mii = 0后將對(duì)角線元素全部置零，即子問(wèn)題Aii = 0。000000當(dāng)r=2，執(zhí)行第(5)句完成了相鄰矩陣Aii+1=

30、pi1*pi*pj 的計(jì)算，并在sij中添入了相應(yīng)的斷點(diǎn)。其中的第(7)句因?yàn)閖 = i+1(k=i+1)而被跳過(guò)去了，實(shí)際并沒(méi)有執(zhí)行。1575026257501000500012345當(dāng)r=3，i=1時(shí)，執(zhí)行第(5)句計(jì)算A1:12:3， m13 = m23 + p0*p1*p3 = 2625 +30*35*5 = 787578751執(zhí)行第(7)句計(jì)算A1:23:3， t = m12 + m33 + p0*p2*p3 = 15750+0+35*15*5 = 183757875，所以m13不變，斷點(diǎn)仍為1。當(dāng)r=3，i=2時(shí)，執(zhí)行第(5)句計(jì)算A2:23:4，m24 = m34 + p1*p2

31、*p4 = 750 +35*15*10 = 600060002執(zhí)行第(7)句計(jì)算A2:34:4， t = m23+m44+ p1*p3*p4 = 2625+0+35*5*10 = 43756000，所以m24改為4375，斷點(diǎn)改為3。43753當(dāng)r=3，i=3時(shí)，執(zhí)行第(5)句計(jì)算A3:34:5，m35 = m45 + p2*p3*p5 = 1000 +15*5*20 = 250025003執(zhí)行第(7)句計(jì)算A3:45:5， t = m34+m55+ p2*p4*p5 = 750+0+15*10*20 = 37502500，所以m35仍為2500，斷點(diǎn)仍為3。當(dāng)r=3，i=4時(shí)，執(zhí)行第(5)句

32、計(jì)算A4:45:6，m46 = m56 + p3*p4*p6 = 5000 +5*10*25 = 625062504執(zhí)行第(7)句計(jì)算A4:56:6， t = m45+m66+ p3*p5*p6 = 1000+0+5*20*25 = 35006250，所以m46改為3500，斷點(diǎn)改為5。35005類(lèi)似的，當(dāng)r=4、5、6時(shí)，可以計(jì)算出相應(yīng)的mij及其相應(yīng)的斷點(diǎn)sij，如下圖中所示：937537125353753118753105003151253由由m16=15125可知這可知這6個(gè)矩陣連乘積的最小運(yùn)算次數(shù)為個(gè)矩陣連乘積的最小運(yùn)算次數(shù)為15125。由。由s16 = 3可知可知A1: 6的最優(yōu)計(jì)

33、算次序?yàn)榈淖顑?yōu)計(jì)算次序?yàn)锳1: 3 A4: 6；由；由s13=1可知可知A1: 3的最優(yōu)計(jì)算次序?yàn)榈淖顑?yōu)計(jì)算次序?yàn)锳1: 1 A2: 3；由；由s46=5可知可知A4: 6的最優(yōu)計(jì)算次序?yàn)榈淖顑?yōu)計(jì)算次序?yàn)锳4: 5 A6: 6；因此最優(yōu)計(jì)算次序?yàn)椋?；因此最?yōu)計(jì)算次序?yàn)椋?A1(A2A3)(A4A5)A6)。32打印矩陣的運(yùn)算次序打印矩陣的運(yùn)算次序void printOptimalParens(int sNUM+1, int i, int j) if (i = j) coutA i ; else cout(; printOptimalParens(s,i,sij); printOptimalPa

34、rens(s,sij+1,j); cout)”; 輸出結(jié)果：輸出結(jié)果：(A1(A2A3)(A4A5)A6)(A1(A2A3)(A4A5)A6)2022-3-1733舉例：給定一個(gè)舉例：給定一個(gè)6 6個(gè)矩陣的矩陣鏈：個(gè)矩陣的矩陣鏈：q 舉例舉例 計(jì)算5 個(gè)矩陣乘積最少數(shù)乘次數(shù)。設(shè)：M1：510M2：104M3：46M4：610M5：102C6,6C1,6C1,5C1,4C1,3C1,2C1,1C2,6C2,5C2,4C2,3C2,2C3,6C3,5C3,4C3,3C4,6C4,5C4,4C5,6C5,5d=0d=2d=1d=3d=4d=5(M1 ( M2 ( M3 ( M4 M5 )例如：例如：

35、n=6的計(jì)算形式348 2620 4320 3200 20 248 3640 3240 30 168 4240 40 120 50 0 34矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。在利用遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是在利用遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱(chēng)為子問(wèn)新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱(chēng)為子問(wèn)題的重疊性質(zhì)。題的重疊性質(zhì)。35n用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即用多邊形頂點(diǎn)的逆時(shí)針序列表示

36、凸多邊形，即P=vP=v0 0,v,v1 1, ,v,vn-1n-1 表示具有表示具有n n條邊的凸多邊形。條邊的凸多邊形。n若若v vi i與與v vj j是多邊形上不相鄰的是多邊形上不相鄰的2 2個(gè)頂點(diǎn)，則線段個(gè)頂點(diǎn)，則線段v vi iv vj j稱(chēng)為稱(chēng)為多邊形的一條多邊形的一條弦弦。弦將多邊形分割成。弦將多邊形分割成2 2個(gè)多邊形個(gè)多邊形vvi i,v,vi+1i+1, ,v,vj j 和和vvj j,v,vj+1j+1, ,v vi i 。36n多邊形的三角剖分就是將多邊形分割成互不相交的三多邊形的三角剖分就是將多邊形分割成互不相交的三角形的弦的集合角形的弦的集合T T。n在凸多邊形在

37、凸多邊形P P的三角剖分的三角剖分T T中中, ,各弦互不相交各弦互不相交, ,且集合且集合T T已達(dá)到最大。已達(dá)到最大。n在有在有n n個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有n-3n-3條弦條弦和和n-2n-2個(gè)三角形。個(gè)三角形。 37n給定凸多邊形給定凸多邊形P P，以及定義在由多邊形的邊和弦組成，以及定義在由多邊形的邊和弦組成的三角形上的的三角形上的權(quán)函數(shù)權(quán)函數(shù)w w。要求確定該凸多邊形的三角剖。要求確定該凸多邊形的三角剖分，使得三角剖分中各個(gè)三角形的分，使得三角剖分中各個(gè)三角形的權(quán)值之和最小權(quán)值之和最小。 38n一個(gè)帶括號(hào)的表達(dá)式可以用一棵二叉樹(shù)表示其一個(gè)

38、帶括號(hào)的表達(dá)式可以用一棵二叉樹(shù)表示其計(jì)算順序，稱(chēng)為表達(dá)式的語(yǔ)法樹(shù)。計(jì)算順序，稱(chēng)為表達(dá)式的語(yǔ)法樹(shù)。例如，例如，(A(A1 1(A(A2 2A A3 3)(A)(A4 4(A(A5 5A A6 6)對(duì)應(yīng)的語(yǔ)法樹(shù)是對(duì)應(yīng)的語(yǔ)法樹(shù)是語(yǔ)法樹(shù)語(yǔ)法樹(shù)39n凸多邊形凸多邊形vv0 0,v,v1 1, ,v vn-1n-1 的三角剖分也可以用語(yǔ)法樹(shù)表示。的三角剖分也可以用語(yǔ)法樹(shù)表示。除（除（v0,v6v0,v6）外，其余）外，其余邊邊構(gòu)成構(gòu)成葉子葉子結(jié)點(diǎn)，結(jié)點(diǎn)，弦弦構(gòu)成構(gòu)成內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)。40n矩陣連乘積中的每個(gè)矩陣矩陣連乘積中的每個(gè)矩陣A Ai i對(duì)應(yīng)凸對(duì)應(yīng)凸(n+1)(n+1)邊形中的一條邊形中的一條邊邊v

39、 vi-1i-1v vi i。三角剖分中的一條弦。三角剖分中的一條弦v vi iv vj j，ijij，對(duì)應(yīng)矩陣連，對(duì)應(yīng)矩陣連乘積乘積Ai+1:jAi+1:j。41凸多邊形最優(yōu)三角凸多邊形最優(yōu)三角 給定凸邊形給定凸邊形p=vp=v0 0,v,v1 1,.v,.vn-1n-1 ，以及定義，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)函數(shù)w w，要求確定該凸多邊形的三角，要求確定該凸多邊形的三角42凸多邊形的最優(yōu)三角剖分凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。證明（反證法）：證明（反證法）：如果凸如果凸(n+1)(n+1)邊形邊形P

40、=vP=v0 0,v,v1 1, ,v,vn n 的的最最優(yōu)三角剖分優(yōu)三角剖分T T包含三角形包含三角形v v0 0v vk kv vn n，1kn-11kn-1，則，則T T的權(quán)為的權(quán)為3 3個(gè)部分權(quán)的和：個(gè)部分權(quán)的和：v v0 0v vk kv vn n +v+v0 0,v,v1 1, ,v,vk k+v+vk k,v,vk+1k+1, ,v,vn n 可以斷言，由可以斷言，由T T確定的兩個(gè)子多邊形的三角剖分也是最優(yōu)確定的兩個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲械?。因?yàn)槿粲衯v0 0,v,v1 1, ,v,vk k 或或vvk k,v,vk+1k+1, ,v,vn n 的更小權(quán)的的更小

41、權(quán)的三角剖分將導(dǎo)致三角剖分將導(dǎo)致T T不是最優(yōu)三角剖分的矛盾。不是最優(yōu)三角剖分的矛盾。 43n定義定義tijtij，1ijn1ijn為凸子多邊形為凸子多邊形vvi-1i-1,v,vi i, ,v,vj j 的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。假設(shè)將退化的多邊形數(shù)值，即其最優(yōu)值。假設(shè)將退化的多邊形vvi-1i-1,v,vi i 的權(quán)值定義為的權(quán)值定義為0 0。最終需要計(jì)算的凸。最終需要計(jì)算的凸(n+1)(n+1)邊形邊形P P的最優(yōu)權(quán)值為的最優(yōu)權(quán)值為t1nt1n。44n利用最優(yōu)子結(jié)構(gòu)性質(zhì)利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算遞歸地計(jì)算tijtij 。當(dāng)當(dāng)j-ij-i1 1

42、時(shí)，凸子多邊時(shí)，凸子多邊形至少有形至少有3 3個(gè)頂點(diǎn)。個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，由最優(yōu)子結(jié)構(gòu)性質(zhì)，tijtij的值應(yīng)為的值應(yīng)為tiktik的值加上的值加上tk+1jtk+1j的值，再加上三角形的值，再加上三角形v vi-1i-1v vk kv vj j的權(quán)值，其中的權(quán)值，其中ikj-1ikj-1。需要在。需要在j-ij-i個(gè)個(gè)位置中選出使位置中選出使tijtij達(dá)到最小的達(dá)到最小的k k。45tijtij可遞歸地定義為：可遞歸地定義為：jijivvvwjktkitjitjkijki)(1min01（3）計(jì)算最優(yōu)值）計(jì)算最優(yōu)值n創(chuàng)建數(shù)組創(chuàng)建數(shù)組sij，用于存放與，用于存放與vi-1和和vj一起構(gòu)

43、成三角形的第一起構(gòu)成三角形的第3個(gè)頂點(diǎn)位置。個(gè)頂點(diǎn)位置。n與矩陣連乘相仿，最優(yōu)值可以通過(guò)與矩陣連乘相仿，最優(yōu)值可以通過(guò)數(shù)組數(shù)組s得到。得到。4647void minWeightTriangulation(int n, int tNUM, int sNUM) / tij存放存放vi-1 vj之間凸多邊形最優(yōu)剖分權(quán)值之間凸多邊形最優(yōu)剖分權(quán)值 / sij 存放最優(yōu)剖分令一個(gè)頂點(diǎn)的位置存放最優(yōu)剖分令一個(gè)頂點(diǎn)的位置 初始化初始化t=0； for (int r = 2; r = n; r+) / 計(jì)算計(jì)算r凸邊形的最優(yōu)剖分凸邊形的最優(yōu)剖分 2. n for (int i = 1; i j之間邊數(shù)為之間邊數(shù)

44、為r的最優(yōu)剖分權(quán)值及位置的最優(yōu)剖分權(quán)值及位置k / 并分別將結(jié)果存放在并分別將結(jié)果存放在tij和和sij中中 48void minWeightTriangulation(int n, int tNUM, int sNUM) for (int i = 1; i = n; i+) tii = 0; / 初始化初始化t for (int r = 2; r = n; r+) / 計(jì)算計(jì)算r凸邊形的最優(yōu)剖分凸邊形的最優(yōu)剖分 for (int i = 1; i j之間的最優(yōu)值及位置之間的最優(yōu)值及位置k tij = ti+1j+ w(i-1, i, j); sij = i; for (int k = i+1

45、; k i+r-1; k+) int u= tik + tk+1j + w(i-1, k, j); if (u tij) tij = u; sij = k; 消耗空間：消耗空間：O(n2)消耗時(shí)間：消耗時(shí)間：O(n3)49在生物工程應(yīng)用中，我們經(jīng)常要比較兩個(gè)在生物工程應(yīng)用中，我們經(jīng)常要比較兩個(gè)DNADNA序列的相序列的相似性，在軟件工程領(lǐng)域也經(jīng)常比較兩個(gè)軟件版本，以似性，在軟件工程領(lǐng)域也經(jīng)常比較兩個(gè)軟件版本，以便確定版本的變化，所有這些相似性比較問(wèn)題，都涉便確定版本的變化，所有這些相似性比較問(wèn)題，都涉及最長(zhǎng)公共子序列問(wèn)題。及最長(zhǎng)公共子序列問(wèn)題。若給定序列若給定序列X=xX=x1 1,x,x2

46、2, ,x,xm m ，則另一序列，則另一序列Z=zZ=z1 1,z,z2 2, ,z,zk k 是是X X的子序列是指存在一個(gè)的子序列是指存在一個(gè)嚴(yán)格遞增的嚴(yán)格遞增的下標(biāo)序列下標(biāo)序列ii1 1,i,i2 2, ,i,ik k 使得對(duì)于所有使得對(duì)于所有j=1,2,j=1,2,k,k有：有：z zj j=x=xi ij j。 例如，例如，Z=BZ=B，C C，D D，BB 是是X=AX=A，B B，C C，B B，D D，A A，B B 的子序列，的子序列， 相應(yīng)的遞增下標(biāo)序列為相應(yīng)的遞增下標(biāo)序列為22，3 3，5 5，77。50給定給定2 2個(gè)序列個(gè)序列X X和和Y Y，當(dāng)另一序列，當(dāng)另一序列

47、Z Z既是既是X X的子序列的子序列又是又是Y Y的子序列時(shí)，稱(chēng)的子序列時(shí)，稱(chēng)Z Z是是X X和和Y Y的的公共子序列公共子序列。最長(zhǎng)公共子序列問(wèn)題最長(zhǎng)公共子序列問(wèn)題：給定：給定2 2個(gè)序列個(gè)序列 X=xX=x1 1,x,x2 2, ,x,xm m 和和 Y=yY=y1 1,y,y2 2, ,y,yn n ， 找出找出X X和和Y Y的最長(zhǎng)公共子序列。的最長(zhǎng)公共子序列。51假設(shè)序列假設(shè)序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n 的最長(zhǎng)公共的最長(zhǎng)公共子序列為子序列為Z=zZ=z1 1,z,z2 2, ,z,zk k ，則，則(1

48、)(1)若若x xm m=y=yn n，則，則z zk k=x=xm m=y=yn n，且，且Z Zk-1k-1是是X Xm-1m-1和和Y Yn-1n-1的最長(zhǎng)公共子的最長(zhǎng)公共子序列。序列。(2)(2)若若x xm myyn n且且z zk kxxm m，則，則Z Z是是X Xm-1m-1和和Y Y的最長(zhǎng)公共子序列。的最長(zhǎng)公共子序列。(3)(3)若若x xm myyn n且且z zk kyyn n，則，則Z Z是是X X和和y yn-1n-1的最長(zhǎng)公共子序列。的最長(zhǎng)公共子序列。2 2個(gè)序列的最長(zhǎng)公共子序列包含了這個(gè)序列的最長(zhǎng)公共子序列包含了這2 2個(gè)序列的前綴的個(gè)序列的前綴的最長(zhǎng)公共子序列。

49、因此，最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)優(yōu)子結(jié)構(gòu)性質(zhì)。 52證明證明 (1) 若若xm= yn，則，則zk = xm = yn， 且且Zk-1是是Xm-1和和Yn-1的最長(zhǎng)公共子序列。的最長(zhǎng)公共子序列。 反證法：反證法： 假設(shè)假設(shè)zkxm,則則 z1, z2, ., zk, xm是是X和和Y的長(zhǎng)度的長(zhǎng)度為為k+1的公共子序列。與假設(shè)的公共子序列。與假設(shè)Z是是X和和Y的最的最長(zhǎng)公共子序列矛盾。長(zhǎng)公共子序列矛盾。 （2）（）（3）類(lèi)似。）類(lèi)似。n由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知可知: :要找出要找出X=xX

50、=x1 1,x,x2 2,x,x3 3,x,xm m 和和Y=yY=y1 1,y,y2 2,y,y3 3,y,yn n 的最長(zhǎng)公共子序列，可按的最長(zhǎng)公共子序列，可按以下方式遞歸計(jì)算：以下方式遞歸計(jì)算：n當(dāng)當(dāng)x xm m=y=yn n時(shí)時(shí)，找出，找出x xm-1m-1和和y yn-1n-1的最長(zhǎng)公共子序列的最長(zhǎng)公共子序列，然后在其尾部加上，然后在其尾部加上x(chóng) xm m( (或者或者y yn n) )即可得即可得X X和和Y Y的的最長(zhǎng)公共子序列。最長(zhǎng)公共子序列。n當(dāng)當(dāng)x xm m y yn n時(shí)時(shí)，必須解兩個(gè)子問(wèn)題：即找出，必須解兩個(gè)子問(wèn)題：即找出x xm-1m-1和和y y的一個(gè)最長(zhǎng)公共子序列

51、及的一個(gè)最長(zhǎng)公共子序列及x x和和y yn-1n-1的一個(gè)最長(zhǎng)的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為x x和和y y的最長(zhǎng)公共子序列。的最長(zhǎng)公共子序列。5354由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用優(yōu)值的遞歸關(guān)系。用cijcij記錄序列記錄序列X Xi和和Y Yj的最長(zhǎng)公共的最長(zhǎng)公共子序列的長(zhǎng)度。其中，子序列的長(zhǎng)度。其中， X Xi i=x=x1 1,x,x2 2, ,x,xi i ；Y Yj j=y=y1 1,y,y2 2, ,y,yj j 。當(dāng)。當(dāng)i=0i=0或或

52、j=0j=0時(shí)，時(shí)，X Xi i和和Y Yj j的最長(zhǎng)公共子的最長(zhǎng)公共子序列是空序列。故此時(shí)序列是空序列。故此時(shí)cij=0cij=0。其他情況下，由最。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110c0.m0.n55由于在所考慮的子問(wèn)題中，總共有由于在所考慮的子問(wèn)題中，總共有(mn)(mn)個(gè)不個(gè)不同的子問(wèn)題，采用遞歸算法會(huì)隨著序列長(zhǎng)度的同的子問(wèn)題，采用遞歸算法會(huì)隨著序列長(zhǎng)度的增長(zhǎng)，時(shí)間復(fù)雜性成指數(shù)遞增，而采用動(dòng)態(tài)規(guī)增長(zhǎng)，時(shí)間復(fù)雜性成指數(shù)遞增，而采用動(dòng)態(tài)規(guī)劃算法自

53、底向上計(jì)算最優(yōu)值可提高算法的效率。劃算法自底向上計(jì)算最優(yōu)值可提高算法的效率。 bij記錄計(jì)算子序列的方式。記錄計(jì)算子序列的方式。cij記錄記錄Xi和和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。的最長(zhǎng)公共子序列的長(zhǎng)度。56int lcsLength(char x , char y , int bNUM,int m,int n ) int* c = 創(chuàng)建C數(shù)組; 初始化ci0，c0i 為0; for (int i = 1; i = m; i+) for (int j = 1; j =cij-1) / 第2,3種情況 cij=ci-1j; bij=2; else cij=cij-1; bij=3; return

54、cmn; 時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(mn)O(mn)57int lcsLength(char x, char y, int bNUM,int m,int n) int cm+1n+1; for (int i = 0; i=m; i+) ci0=0; for (int i = 0; i=n; i+ ) c0i=0; for (int i = 1; i = m; i+) for (int j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn; 時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(mn)O(mn)58構(gòu)造最長(zhǎng)公共子序列構(gòu)造最長(zhǎng)公共

55、子序列(打印最長(zhǎng)公共子序列）打印最長(zhǎng)公共子序列）void lcs(int i,int j, char x, int bNUM) if (i =0 | j=0) return; if (bij= 1) lcs(i-1, j-1, x, b); coutxi- 1; else if (bij = 2) lcs(i-1, j, x, b); else lcs(i, j-1, x, b); 每次運(yùn)行都使每次運(yùn)行都使i 或或 j 減減1，所以時(shí)間復(fù)雜度為，所以時(shí)間復(fù)雜度為O(m+n)。59 #include int main() char* x = ABCBDAB; char* y =BDCABA; i

56、nt xlen = strlen(x); int ylen = strlen(y); int bNUM1 + 1NUM2 + 1; int len = lcsLength(x, y, b, xlen,ylen); lcs(xlen,ylen, x, b); return 0;運(yùn)行結(jié)果：運(yùn)行結(jié)果：BCBA60運(yùn)行結(jié)果：運(yùn)行結(jié)果：BCBA61運(yùn)行結(jié)果：運(yùn)行結(jié)果：BCBA6200000000000yj:xmy1y2ynx1x2xii012nm120firstsecond填表的順序：沿著箭頭先填充最上面一行，填表的順序：沿著箭頭先填充最上面一行，然后填充接下來(lái)的行然后填充接下來(lái)的行6300000000

57、000yj:DACFABxiji012nm120矩陣 cStepi, j:l它告訴我們要獲得最優(yōu)結(jié)果應(yīng)該如何選擇l如果 xi = yjcStepi, j = “ ”（1）l如果 nZi - 1, j nZi, j-1cStepi, j = “” （2）否則cStepi, j = “” （3）33CDci,j-1ci-1,jnLCS(sX, sY, nA, nB)1 for i 1 to nA do nZi, 0 02 for j 0 to nB do nZ0, j 03 for i 1 to nA do4 for j 1 to nB do5 if xi = yj6 then nZi, j ci

58、 - 1, j - 1 + 17 cStep i, j “ ”8 else if nZi - 1, j nZi, j - 19 then nZi, j nZi - 1, j10 cStep i, j “”11 else nZi, j nZi, j - 112 cStep i, j “”13 return nZ and cStep64運(yùn)行時(shí)間: (nA*nB) 舉例X = (B, D, C, A, B, A)Y = (A, B, C, B, D, A,B)650126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222

59、 1122 331 222331232 3 4 1223 44如果 xi = yj cStepi, j = “ ”如果 nZi - 1, jnZi, j-1cStepi, j = “ ”否則cStepi, j = “ ”找出最長(zhǎng)共同子序列sLCS(cStep, sX, i, j)1 if i = 0 or j = 02 then return3 if cStepi, j = 4 then sLCS(cStep, X, i - 1, j - 1)+ xi5 elseif cStepi, j = 6 then sLCS(cStep, X, i - 1, j)7 else sLCS(cStep, X

60、, i, j - 1)6667多段圖定義：多段圖定義：給定有向連通帶權(quán)圖給定有向連通帶權(quán)圖G=(V,E,W)G=(V,E,W)，如果將頂，如果將頂點(diǎn)集合點(diǎn)集合 V V 劃分成劃分成 k k 個(gè)互不相交的子集個(gè)互不相交的子集V Vi i，1 1iik k，k k2,2,使得使得E E中的任何一條邊中的任何一條邊(u,v)(u,v)，必有，必有u uV Vi i,v,v V Vi+mi+m，m m 1 1，則稱(chēng)，則稱(chēng)這樣的圖為這樣的圖為多段圖多段圖。68多段圖令令|V|V1 1| =|V| =|Vk k|=1,|=1,稱(chēng)稱(chēng)s s V V1 1為為源點(diǎn)源點(diǎn)，t tV Vk k為為匯點(diǎn)匯點(diǎn)。st69首