1、 12022年4月8日8時08分計算機常用算法簡介計算機常用算法簡介(1) 2011年年4月月主要內容主要內容算法概述算法概述分治與遞歸分治與遞歸動態規劃動態規劃貪心算法貪心算法回溯法回溯法分限界法分限界法 22022年4月8日8時08分1、算法、算法(Algorithm)一、算法概述一、算法概述2、程序、程序(probram)解決問題的方法（現實世界解決問題的方法（現實世界數字世界）。數字世界）。 算法的具體實現（具體的代碼序列）算法的具體實現（具體的代碼序列） 3、算法與程序的主要區別、算法與程序的主要區別算法的主要特征：算法的主要特征： 1）有輸入：有零個或多個數據輸入。）有輸入：有零個

2、或多個數據輸入。 2）有輸出：至少有一個數據輸出。）有輸出：至少有一個數據輸出。 3）確定性：組成算法的每個操作是無二義的。）確定性：組成算法的每個操作是無二義的。 4）有限性：每個操作的次數和時間是有限的。）有限性：每個操作的次數和時間是有限的。 程序可能不滿足第程序可能不滿足第4）條，如操作系統程序會重復）條，如操作系統程序會重復地、無限地執行許多用戶請求。地、無限地執行許多用戶請求。 32022年4月8日8時08分4、算法的評價標準、算法的評價標準一、算法概述一、算法概述1）正確性）正確性 2）直觀性）直觀性(可交流性可交流性) 3）容錯性）容錯性(健壯性健壯性) 4）分級性）分級性 5

3、）高效性）高效性(時間時間,空間空間)*5、與算法執行時間有關的主要因素、與算法執行時間有關的主要因素 1）計算機速度）計算機速度 2）問題的規模）問題的規模 3）數據的原始狀態。）數據的原始狀態。 4）算法的結構）算法的結構* 42022年4月8日8時08分6、時間復雜性的評價方法、時間復雜性的評價方法一、算法概述一、算法概述 1）最少次數）最少次數-Tmin (n) 2）最壞次數）最壞次數-Tmax (n) 3）平均次數）平均次數-Tavg(n) 4）漸近階）漸近階-T(n) O(1) /O(n) / O(nlog2n) / O(n2)7、算法的描述、算法的描述 自然語言自然語言 高級語言

4、高級語言 偽代碼偽代碼 N-S圖圖*S1S2eS1S2while/forS 52022年4月8日8時08分一、算法概述一、算法概述7、算法的描述、算法的描述 用用N-S圖描述的求一元二次方程的根的算法圖描述的求一元二次方程的根的算法:取得方程的參數取得方程的參數:a,b,c計算判別式計算判別式:b2-4ac判別式判別式=0 ?輸出兩相等輸出兩相等實根實根判別式判別式0 ?輸出兩不等實根輸出兩不等實根 輸出兩共扼虛根輸出兩共扼虛根 62022年4月8日8時08分一、算法概述一、算法概述8、算法實例、算法實例 順序查找與二分查找順序查找與二分查找9、幾個重要概念、幾個重要概念 1)數組與指針數組與

5、指針 2)函數與函數接口函數與函數接口 3)傳值與傳址傳值與傳址(傳引用傳引用) 4)循環與遞歸循環與遞歸 72022年4月8日8時08分1、遞歸算法、遞歸算法二、分治策略二、分治策略 遞歸算法遞歸算法直接或間接調用自己的算法。直接或間接調用自己的算法。 遞歸算法的特點：遞歸算法的特點： 1）子問題結構相似）子問題結構相似,規模趨小規模趨小 2）存在遞歸邊界）存在遞歸邊界(遞歸結束條件遞歸結束條件) 如：如： 5！=5*4！ 4！=4*3！ 3！=3*2！ 2！=2*1！ 1！=1*0！ 0！=1int jc (int n) if (n=0) return 1; else return n*j

6、c(n-1);T(n)=1+T(n-1) =1+1+T(n-2) =n+T(0) 82022年4月8日8時08分2、分治法的基本思想、分治法的基本思想二、分治策略二、分治策略 分治法的基本思想是將一個規模為分治法的基本思想是將一個規模為n的問題分解為的問題分解為k個規個規模較少的子問題，這些子問題相互獨立且與原問題結構相模較少的子問題，這些子問題相互獨立且與原問題結構相同。遞歸地求解這些子問題，然后將這些子問題的解合并同。遞歸地求解這些子問題，然后將這些子問題的解合并得到原問題的解。得到原問題的解。 （n=n1+n2+nk）3、分治法運用舉例、分治法運用舉例1）求二叉樹的葉結點數）求二叉樹的葉

7、結點數int yz (BiNode *T) if (!T) return 0; else return yz(T-lchild) + yz(T-rchild);空樹空樹?返回零返回零返回左返回左,右子樹葉子數之和右子樹葉子數之和 92022年4月8日8時08分 先序遍歷：先序遍歷： 中序遍歷：中序遍歷：A B CG I D J E FHG C I B J D A F E H二、分治策略二、分治策略3、分治法運用舉例、分治法運用舉例 2)已知二叉樹已知二叉樹T的先序和中序遍歷序列分別為串的先序和中序遍歷序列分別為串l和和r，試構造該二叉樹試構造該二叉樹T 102022年4月8日8時08分ABCG

8、IDJEFHGCIBJDAFEH 某二叉樹的先序遍歷序列為某二叉樹的先序遍歷序列為ABCGIDJEFH，中序遍歷，中序遍歷序列為序列為DCIBJDAFEH，構造該二叉樹，構造該二叉樹:ABCGIDJGCIBJDEFHFEHBECGIGCIFFHHDJJD二、分治策略二、分治策略3、分治法運用舉例、分治法運用舉例 2)已知二叉樹已知二叉樹T的先序和中序遍歷序列分別為串的先序和中序遍歷序列分別為串l和和r，試構造該二叉樹試構造該二叉樹T(續續) 112022年4月8日8時08分二、分治策略二、分治策略 事實上：二叉樹由樹根和兩棵子樹構成，若分別完成事實上：二叉樹由樹根和兩棵子樹構成，若分別完成根及

9、左、右子樹的構造即可完成全部任務（一分三）。根及左、右子樹的構造即可完成全部任務（一分三）。 過程一：構造二叉樹的根結點過程一：構造二叉樹的根結點-關鍵是找到根結點關鍵是找到根結點 過程二：構造左子樹（與原問題相同且規模更小）過程二：構造左子樹（與原問題相同且規模更小） 過程三：構造右子樹（與原問題相同且規模更小）過程三：構造右子樹（與原問題相同且規模更小） 過程四：合并成一棵樹（指針修改）過程四：合并成一棵樹（指針修改）3、分治法運用舉例、分治法運用舉例 2)已知二叉樹已知二叉樹T的先序和中序遍歷序列分別為串的先序和中序遍歷序列分別為串l和和r，試構造該二叉樹試構造該二叉樹T(續續) 122

10、022年4月8日8時08分二、分治策略二、分治策略3、分治法運用舉例、分治法運用舉例 2)已知二叉樹已知二叉樹T的先序和中序遍歷序列分別為串的先序和中序遍歷序列分別為串l和和r，試構造該二叉樹試構造該二叉樹T（續）（續） 構造二叉樹的構造二叉樹的N-S圖：圖：遍歷序列為空遍歷序列為空返回空指針返回空指針建立根結點建立根結點構建左子樹構建左子樹構建右子樹構建右子樹左右子樹掛于根下左右子樹掛于根下返回根指針返回根指針 132022年4月8日8時08分二、分治策略二、分治策略3、分治法運用舉例、分治法運用舉例 3)整數劃分問題：將一個正整數整數劃分問題：將一個正整數n分解成一系列的正整分解成一系列的

11、正整數之和：數之和： n=n1+n2+nk （ n1 n2 nk ） 正整數正整數n的一種分解就稱為它的一個劃分。正整數的一種分解就稱為它的一個劃分。正整數n的的全部不同的劃分個數稱為全部不同的劃分個數稱為n的劃分數，記為的劃分數，記為p(n)。 例如：正整數例如：正整數6有：有： p(6)=11。 6=6 =5+1 =4+2 = 4+1+1 =3+3 = 3+2+1 = 3+1+1+1 =2+2+2 = 2+2+1+1 = 2+1+1+1+1 =1+1 +1+1+1+1n1 =6：1n1 =5：1n1 =4：2n1 =3：3n1 =2：3n1 =1：1 142022年4月8日8時08分二、分

12、治策略二、分治策略3、分治法運用舉例、分治法運用舉例 3)整數劃分問題（續）整數劃分問題（續） 1 當當mn時，最大分解數最大取時，最大分解數最大取n，故有，故有 q(n,m) = q(n,n)。 由于劃分方案與被分解數及最大分解數都有關，故設由于劃分方案與被分解數及最大分解數都有關，故設q(n,m)是是n的最大不超的最大不超m的分解個數。則分如下幾情形：的分解個數。則分如下幾情形： 2 當當m=n時，最大分解數有等于和小于時，最大分解數有等于和小于n兩種情形，有：兩種情形，有： q(n,n) =1+ q(n,n-1)。 3 當當nm1時，最大分解數有等于和小于時，最大分解數有等于和小于m兩種

13、情形，兩種情形，有：有： (等于等于m的分解數的分解數+小于小于m的分解數的分解數) q(n,m) = q(n-m,m)+ q(n,m-1) 。 4 m=1時，僅一種：時，僅一種：n=1+1+1，即：，即： q(n,1)=1。 152022年4月8日8時08分二、分治策略二、分治策略3、分治法運用舉例、分治法運用舉例 3)整數劃分問題（續）整數劃分問題（續）q(n,m)= 于是我們得到于是我們得到q(n,m)到的遞歸關系：到的遞歸關系： q(n,n) mn1+ q(n,n-1) m=n q(n-m,m)+ q(n,m-1) nm1 1 m=1 相信大家根據這個遞歸關系都能給出相應的算法。相信大

14、家根據這個遞歸關系都能給出相應的算法。 162022年4月8日8時08分二、分治策略二、分治策略4、遞歸算法小結、遞歸算法小結 優點優點:結構清晰，可讀性強，它為設計算法、調試程結構清晰，可讀性強，它為設計算法、調試程序帶來很大方便。序帶來很大方便。 缺點缺點:遞歸算法的運行效率較低，無論是耗費的計算遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。時間還是占用的存儲空間都比非遞歸算法要多。 172022年4月8日8時08分1、引例、引例-矩陣連乘問題矩陣連乘問題三、動態規劃三、動態規劃ABAB=mnmlnlCij=ai1*b1j+ai2*b2j+ain*bnj

15、 182022年4月8日8時08分1、引例、引例-矩陣連乘問題矩陣連乘問題(續續)三、動態規劃三、動態規劃 我們知道，矩陣的乘法滿足：我們知道，矩陣的乘法滿足：A*(B*C) =(A*B)*C，從計算量上考慮，兩種方案是否一樣呢？從計算量上考慮，兩種方案是否一樣呢？ 考查實例：考查實例：A10*100*B100*5*C5*50: 由于矩陣的乘法中相加的次數是固定的，計算量的差異由于矩陣的乘法中相加的次數是固定的，計算量的差異主要表現在相乘的次數上主要表現在相乘的次數上: B*C： 100 *5 *50 （100*50） A* ( B*C) ： 100 *5 *50 +10*100*50=750

16、00 A*B： 10*100*5 （10*5） (A*B)*C： 10*100*5+10*5*50=7500思考題：思考題： 1）矩陣的連乘中乘法的計算次數與什么有關？）矩陣的連乘中乘法的計算次數與什么有關？ 2）n個矩陣連乘，需要幾個參數？個矩陣連乘，需要幾個參數？ 192022年4月8日8時08分1、引例、引例-矩陣連乘問題矩陣連乘問題(續續 )三、動態規劃三、動態規劃 以以4個矩陣連乘為例，利用分治法的思想，我們有：個矩陣連乘為例，利用分治法的思想，我們有：1:4 1:12:41:23:41:34:42:23:4 2:34:4 1:12:2 3:34:41:12:3 1:23:33:34

17、:42:23:32:23:31:12:2自頂向下遞歸，有自頂向下遞歸，有許多重復計算許多重復計算 202022年4月8日8時08分1、引例、引例-矩陣連乘問題矩陣連乘問題(續續 )三、動態規劃三、動態規劃 若采用自底向上的方法，有：若采用自底向上的方法，有：1:4 1:32:41:12:23:34:41:23:42:3自底向上計算自底向上計算沒有重復計算沒有重復計算 212022年4月8日8時08分2、動態規劃的基本思想、動態規劃的基本思想三、動態規劃三、動態規劃動態規劃與分治法類似，也是將待求問題分解成若動態規劃與分治法類似，也是將待求問題分解成若干個子問題，通過求子問題的解來求出整個問題的

18、解。與干個子問題，通過求子問題的解來求出整個問題的解。與分治法不同的是，它的子問題往往不是相互獨立的。若用分治法不同的是，它的子問題往往不是相互獨立的。若用分治法來解，會出現許多的重復計算。動態規劃的思想是分治法來解，會出現許多的重復計算。動態規劃的思想是按問題規模從小到大逐步求出子問題的解，最后求出整個按問題規模從小到大逐步求出子問題的解，最后求出整個問題的解。問題的解。 3、動態規劃算法的基本要素、動態規劃算法的基本要素1）最優子結構（小最優）最優子結構（小最優大最優大最優） 2）重疊子問題（有重復子問題）重疊子問題（有重復子問題） 222022年4月8日8時08分4、動態規劃算法的實現步

19、驟、動態規劃算法的實現步驟三、動態規劃三、動態規劃1）分析最優解的結構。）分析最優解的結構。2）建立最優解遞歸關系。）建立最優解遞歸關系。3）自底向上計算最優值。）自底向上計算最優值。4）構造最優解。）構造最優解。 5、動態規劃算法舉例、動態規劃算法舉例 1）矩陣連乘問題）矩陣連乘問題 1 分析最優解結構分析最優解結構 設設Ai:j=AiAi+1Aj ，若，若Ai:j的最優解是在的最優解是在Ai:k Ak+1:j處取得，顯然處取得，顯然Ai:k和和 Ak+1:j也必然取得最優解。也必然取得最優解。如前所述，我們從一個、兩個如前所述，我們從一個、兩個逐步求出長度為逐步求出長度為n的最的最優解。優

20、解。 232022年4月8日8時08分5、動態規劃算法舉例、動態規劃算法舉例 1）矩陣連乘問題（續）矩陣連乘問題（續）三、動態規劃三、動態規劃 2 建立遞歸關系建立遞歸關系 設設n個矩陣的行列維數存儲在數組個矩陣的行列維數存儲在數組p0.n中。又設中。又設Ai:j=AiAi+1Aj，Ai:j的結合方法共有的結合方法共有j-i種。即：種。即： Ai:j=Ai:k Ak+1:j (k=i,i+1,i+2,j-1) 若設若設Ai:j的最少計算次數記為的最少計算次數記為mi,j。則易得：。則易得：mi,j=0 i=jmin mi,k+mk+1,j+pi-1*pk*pj ij 前半部最少次數，后半部最少

21、次數，前后相乘次數前半部最少次數，后半部最少次數，前后相乘次數 3 計算最優值計算最優值 這里僅給出算法的這里僅給出算法的N-S圖：圖： 242022年4月8日8時08分5、動態規劃算法舉例、動態規劃算法舉例 1）矩陣連乘問題（續）矩陣連乘問題（續）三、動態規劃三、動態規劃 有關變量說明：有關變量說明： p0.n存儲矩陣行列數的數組；存儲矩陣行列數的數組； m1.n1.n存儲最少計算次數的數組；存儲最少計算次數的數組； s1.n1.n存儲結合點的數組；存儲結合點的數組；for(i=1;i=n;i+)mii=0; sii=i; for(r=2;r0， wi 0 ， vi 0，(1 i n)，要求

22、找出，要求找出一組一組0-1元向量（元向量（x1,x2,x3.xn），使得），使得xiwi c且且xivi最大。最大。 1 分析最優解結構：分析最優解結構：若若0-1元向量（元向量（x1,x2,x3.xn）是最優解，即使得）是最優解，即使得xiwi c且且xivi最大，必有：最大，必有： 0-1元向量（元向量（x1,x2,x3.xn-1）是最優解，即使得是最優解，即使得xiwi c- xnwn且且xivi最大。最大。 292022年4月8日8時08分5、動態規劃算法舉例、動態規劃算法舉例 3）0-1背包問題背包問題(續續)三、動態規劃三、動態規劃 2 建立遞歸關系建立遞歸關系設設mi,j是即使

23、得是即使得xkwk j的的xkvk的最大值的最大值,即：即： mi,j=max xkvk (xkwk j, i k n)于是第于是第i種物品有兩種可能：不裝入種物品有兩種可能：不裝入/裝入：裝入：mi,j=0 i=n,wnjvn i=n,wn jmi+1,j ijmaxmi+1,j,mi+1,j-vi+vi in, xkwk +wi j第第i件物品不裝入件物品不裝入 第第i件物品裝入件物品裝入 302022年4月8日8時08分5、動態規劃算法舉例、動態規劃算法舉例 3）0-1背包問題背包問題(續續)三、動態規劃三、動態規劃 3 計算最優值計算最優值采用自底向上求解：采用自底向上求解： i取取n

24、1，而，而j取取0c。 對應算法對應算法N-S圖為：圖為： 進一步求精，可得：進一步求精，可得：i=n時，時， j :0c mi,jin時，時， j :0c mi,j 312022年4月8日8時08分5、動態規劃算法舉例、動態規劃算法舉例 3）0-1背包問題背包問題(續續)三、動態規劃三、動態規劃for(j=0;jwn;j+)mn,j=0;for(j =wn;j=1;i-)for(j=0;jwn;j+)mi,j=mi+1,j;for(j=wn;j=c;j+)mi,j=maxmi+1,j,mi+1,j-wi+vi; 322022年4月8日8時08分5、動態規劃算法舉例、動態規劃算法舉例 3）0-

25、1背包問題背包問題(續續)三、動態規劃三、動態規劃 4 構造最優解構造最優解 顯然最后要求出顯然最后要求出0-1向量向量X，以，以x1為例，與為例，與m2c -m1c是否為零有關是否為零有關。 于是有下列的求于是有下列的求X的的N-S圖：圖：for(i=1;i0 ? 1:0 332022年4月8日8時08分1、引例、引例-哈夫曼樹、最小生成樹哈夫曼樹、最小生成樹四、貪心算法四、貪心算法2、貪心算法的基本思想、貪心算法的基本思想貪心算法是通過一系列的選擇來得到一個問題的最貪心算法是通過一系列的選擇來得到一個問題的最優解。它所做的每一次選擇都是當前狀態下某種意義的最優解。它所做的每一次選擇都是當前

26、狀態下某種意義的最好選擇，即貪心選擇。希望通過每次的貪心選擇導致最終好選擇，即貪心選擇。希望通過每次的貪心選擇導致最終結果是問題的一個最優解（局部最優結果是問題的一個最優解（局部最優整體最優）。整體最優）。3、貪心算法與動態規劃算法的差別、貪心算法與動態規劃算法的差別 二者都具有最優子結構性質，但貪心算法需要確保局部二者都具有最優子結構性質，但貪心算法需要確保局部最優能使得整體最優（自頂向下），而動態規劃算法常需最優能使得整體最優（自頂向下），而動態規劃算法常需要做大量的選擇判斷（自底向上）。要做大量的選擇判斷（自底向上）。 342022年4月8日8時08分3、貪心算法與動態規劃算法的差別、貪

27、心算法與動態規劃算法的差別四、貪心算法四、貪心算法 0-1背包問題與背包問題（重量背包問題與背包問題（重量/價值價值/容量）。容量）。 這里的這里的0-1是指某件物品要么裝入，要么不裝。是指某件物品要么裝入，要么不裝。 前已介紹，前已介紹，0-1背包問題可以用動態規劃來求最優解，背包問題可以用動態規劃來求最優解，而背包問題用貪心算法求解比較容易：即將重量價值比大而背包問題用貪心算法求解比較容易：即將重量價值比大的先裝入的先裝入直到包裝滿（可裝入某物品的部分）。而直到包裝滿（可裝入某物品的部分）。而0-1背包問題卻不能用貪心算法來求解，因為貴者先的策略可背包問題卻不能用貪心算法來求解，因為貴者先

28、的策略可能會讓包裝不滿。能會讓包裝不滿。4、貪心算法的一般求解步驟、貪心算法的一般求解步驟1) 分析最優子結構性質；分析最優子結構性質；2) 自頂向下，構造最優解。自頂向下，構造最優解。 352022年4月8日8時08分計算機常用算法簡介計算機常用算法簡介(2)龔雄興龔雄興 2011年年5月月主要內容主要內容算法概述算法概述分治與遞歸分治與遞歸動態規劃動態規劃貪心算法貪心算法回溯法回溯法分限界法分限界法 362022年4月8日8時08分 數組循環移動問題數組循環移動問題: 1)長度為長度為n的數組向右循環移動的數組向右循環移動k位位,當當k=n時時,相當于相當于向右循環移動向右循環移動k %

29、n位位; 2)長度為長度為n的數組向左循環移動的數組向左循環移動k位位,相當于向右循環移相當于向右循環移動動n- (k % n)位位;012右移3位7890123456 故數組循環移動的核心是向右移動故數組循環移動的核心是向右移動k位的算法位的算法: RMove(a ,n,k) 372022年4月8日8時08分 數組循環移動問題數組循環移動問題: 算法算法1: 每次循環右移每次循環右移1位位,重復重復k次次 時間復雜性時間復雜性: 空間復雜性空間復雜性:012右移1位9012345678T(n)=kn S(n)=189012345677890123456右移1位右移1位 382022年4月8日

30、8時08分 數組循環移動問題數組循環移動問題:012右移3位0120123456 算法算法2: 申請申請k個輔助空間用于暫存最右邊個輔助空間用于暫存最右邊k個元素個元素,然然后全部元素右移后全部元素右移k位位 時間復雜性時間復雜性: 空間復雜性空間復雜性:T(n)=k+n S(n)=k7897897890123456 392022年4月8日8時08分 數組循環移動問題數組循環移動問題:0 1 2 3 4 5 6 7 8 9 算法算法3: 申請申請1個輔助空間用于暫存第個輔助空間用于暫存第1個元素個元素,依次找依次找應該移到該處的元素位置并移動應該移到該處的元素位置并移動(重復重復n-1次次)

31、07,74,41,18,85,52,29,96,63,307 8 9 0 1 2 3 4 5 6 時間復雜性時間復雜性: 空間復雜性空間復雜性:T(n)=n S(n)=1(i-k+n) %n i 注意注意,此算法對此算法對k與與n的關系有要求的關系有要求(本例中如本例中如k=2,5) k,n不能有平凡公因子不能有平凡公因子 (可通過多次移動來解決可通過多次移動來解決)0 402022年4月8日8時08分 數組循環移動問題數組循環移動問題:9 8 7 | 6 5 4 3 2 1 0 算法算法4: 利用就地逆置利用就地逆置0 1 2 3 4 5 6 7 8 9左k右n-k局部逆置整體逆置7 8 9

32、 0 1 2 3 4 5 6 時間復雜性時間復雜性: 空間復雜性空間復雜性:T(n)=2n S(n)=1void D(a,l,r) /逆置遞歸算法逆置遞歸算法 if(r-l=0)return; alr; D(a,l+1,r-1); 412022年4月8日8時08分5、貪心算法示例、貪心算法示例-多機調度問題多機調度問題四、貪心算法四、貪心算法 有個有個n作業，各需要一定的時間完成，任務作業，各需要一定的時間完成，任務i需要的時需要的時間是間是ti (i=0,2,3n-1) ，假設有，假設有m個性能相似的計算機來處個性能相似的計算機來處理上述作業，每個作業只能交一臺計算機處理，每臺計算理上述作業

33、，每個作業只能交一臺計算機處理，每臺計算機任一時刻只能處理一個作業，問如何調度這些作業，使機任一時刻只能處理一個作業，問如何調度這些作業，使得在最短的時間內處理完全部的作業。得在最短的時間內處理完全部的作業。 1 分析最優子結構性質分析最優子結構性質 最短時間完成全部任務就是說各計算機間處理的任務總最短時間完成全部任務就是說各計算機間處理的任務總時間相差最小，而這個差的極限值是時間相差最小，而這個差的極限值是0，即平均分配作業，即平均分配作業，但同一作業不能被分配給多臺計算機來完成，故作業分配但同一作業不能被分配給多臺計算機來完成，故作業分配的關鍵是各計算機完成的總時間差別最小。的關鍵是各計算

34、機完成的總時間差別最小。 當當nm時需要利用貪心算法來時需要利用貪心算法來分配分配 422022年4月8日8時08分5、貪心算法示例、貪心算法示例-多機調度問題多機調度問題(續續)四、貪心算法四、貪心算法 2 自頂向下，構造最優解自頂向下，構造最優解 為一達到各計算機完成的總作業時間差別最小這一目標。為一達到各計算機完成的總作業時間差別最小這一目標。我們必須：總將最大的作業分配給目前任務量最少的計算我們必須：總將最大的作業分配給目前任務量最少的計算機。機。 我們的算法策略中，需要對各作業的時間和目前各計算我們的算法策略中，需要對各作業的時間和目前各計算機已取得總任務量取最大最小值或進行排序，同

35、時我們還機已取得總任務量取最大最小值或進行排序，同時我們還需要標記各個作業的分配情況，故我們需要定義適當的數需要標記各個作業的分配情況，故我們需要定義適當的數據結構來存儲數據。據結構來存儲數據。作業數組作業數組t作業數組作業數組T計算機數組計算機數組J 操作演示操作演示. 注意注意:如何找最大作業如何找最大作業,如何找最小作業量如何找最小作業量,如何存貯如何存貯分配方案分配方案? 432022年4月8日8時08分5、貪心算法示例、貪心算法示例-多機調度問題多機調度問題(續續)四、貪心算法四、貪心算法0t01t12t23t3原原 作作編編 業業號號 時時間間n-1tn-10123作作 作作分分業

36、業 業業給給編編 時時計計號號 間間算算機機編編號號n-101已已2分分3得得的的作作業業量量m-1 442022年4月8日8時08分5、貪心算法示例、貪心算法示例-多機調度問題多機調度問題(續續)四、貪心算法四、貪心算法 有了上面的準備，我們可以得到下面的算法有了上面的準備，我們可以得到下面的算法N-S圖：圖： 最后統計各個計算機的工作量最后統計各個計算機的工作量,最大值即為全部任務完最大值即為全部任務完成的最短時間。成的最短時間。初始化初始化T J T按任務時間降序排列按任務時間降序排列for(i=0;in;i+)找最小作業量的計算機找最小作業量的計算機kTi分配給分配給Jk 452022

37、年4月8日8時08分5、貪心算法示例、貪心算法示例-多機調度問題多機調度問題(續續)四、貪心算法四、貪心算法 最后需要說明的是，就本問題而言，貪心算法所求只能最后需要說明的是，就本問題而言，貪心算法所求只能算是一個近似解，如任務算是一個近似解，如任務3，5，5，6，3分配給兩臺計算分配給兩臺計算機，所得就不是最優解機，所得就不是最優解(近似解近似解)。0 31 52 53 64 30 3601 1512 2513 0304 430012110 462022年4月8日8時08分1、回溯算法的基本思想、回溯算法的基本思想五、回溯算法五、回溯算法 回溯算法有回溯算法有“通用解題法通用解題法”之稱。它

38、的基本思想是在之稱。它的基本思想是在有限的可能解空間樹中進行深度優先探索（可能用到剪枝有限的可能解空間樹中進行深度優先探索（可能用到剪枝函數），直到找到一個或全部的解。函數），直到找到一個或全部的解。 旅行售貨員問題：出去推銷一次返回到起點旅行售貨員問題：出去推銷一次返回到起點(除起除起,終點終點外外,不重復頂點不重復頂點)的最小代價方案。的最小代價方案。1234630102054 其實就是從起點進行圖的深其實就是從起點進行圖的深度優先遍歷度優先遍歷,直到回到起點直到回到起點,不同不同的是要找出全部的方案并求最的是要找出全部的方案并求最優方案。優方案。 472022年4月8日8時08分1、回溯

39、算法的基本思想、回溯算法的基本思想五、回溯算法五、回溯算法 旅行售貨員問題：旅行售貨員問題：1:02:304:43:353:602:114:554:211:5912346301020543:64:404:261:252:143:192:293:241:25 482022年4月8日8時08分2、回溯算法求解的一般步驟、回溯算法求解的一般步驟五、回溯算法五、回溯算法 1）針對問題定義問題的解空間；）針對問題定義問題的解空間； 2）確定易于搜索的解空間結構；）確定易于搜索的解空間結構； 3）以深度優先的方式搜索解空間，直到找到一個或全）以深度優先的方式搜索解空間，直到找到一個或全部的解，并且在搜索過

40、程中適當使用剪枝函數以避免無效部的解，并且在搜索過程中適當使用剪枝函數以避免無效搜索。搜索。 492022年4月8日8時08分五、回溯算法五、回溯算法00010203040506071011121314151617202122232425262730313233343536374041424344454647505152535455565760616263646566677071727374757677x1+y1=x2+y23、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題: 皇后的捕捉條件皇后的捕捉條件:同行或同列或同對角線，同行或同列或同對角線，問如何在問如何在N*N的方格上放置的方格

41、上放置N個不相互捕捉的皇后。個不相互捕捉的皇后。x1-y1=x2-y2x1=x2 或 y1=y2或 |x1-x2|=| y1-y2| 502022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續)五、回溯算法五、回溯算法 N皇后問題主要需解決下列問題：皇后問題主要需解決下列問題： 1)皇后的存儲結構：皇后的存儲結構： 2)皇后相互捕捉的條件皇后相互捕捉的條件： 3)何時判斷下一列及下一行？何時判斷下一列及下一行？ 4)何時得到一種方案何時得到一種方案? 5)如何找到全部的解如何找到全部的解?|x1-x2|=| y1-y2|或同列或同列二維數組二維數組?一維一維?

42、本列或本行結束本列或本行結束全部全部N行都找到放法行都找到放法 考慮用一維全局數組考慮用一維全局數組X0.N-1來存儲來存儲N皇后的具體位皇后的具體位置值置值,即第即第i個皇后放置在第個皇后放置在第i行的第行的第Xi列列,則有判斷第則有判斷第i個皇個皇后與前邊已放置的后與前邊已放置的i-1個皇后是否不捕捉的算法個皇后是否不捕捉的算法N-S圖為圖為:每行的每列都試試每行的每列都試試 512022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續)五、回溯算法五、回溯算法 bool IsOk(int i)/檢查第檢查第i行是否可以放置的函數行是否可以放置的函數for(

43、j=0;ji;j+)第第j行與第行與第i行是否沖突行是否沖突?返回返回 false返回返回 turefor(j=0;j 遞歸回溯算法遞歸回溯算法 若設試放第若設試放第k行的遞歸回溯算法的函數為行的遞歸回溯算法的函數為:Check(k)，那，那么，至少應該傳遞以下幾個參數：么，至少應該傳遞以下幾個參數： 總皇后的數量：總皇后的數量：N； 皇后的放法數組：皇后的放法數組：X； 已找到的方案數目：已找到的方案數目：Sum。 目前試放的行號：目前試放的行號：k； (為簡單見，本例中，僅為簡單見，本例中，僅k作為形參傳入，其它用外部變量作為形參傳入，其它用外部變量) 有了上面的準備工作之后，就容易有下列

44、的試放第有了上面的準備工作之后，就容易有下列的試放第k行的遞歸算法行的遞歸算法Check(k)的的N-S圖：圖： 532022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續)五、回溯算法五、回溯算法 進一步求精進一步求精:全部行測試完全部行測試完?找到一個方案找到一個方案計數器累加計數器累加從第從第0列到最后一列列到最后一列試放于當前列試放于當前列該位置可放否該位置可放否?檢查下一行檢查下一行 void Check(int k): 542022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續)五、回溯算法五、回溯算法 注意，整個

45、問題求解的測試應該從首行即零行開始：注意，整個問題求解的測試應該從首行即零行開始： Sum=0; Check(0);k=N?記錄方案記錄方案計數器累加計數器累加for(j=0;j 迭代回溯算法迭代回溯算法 所謂迭代回溯所謂迭代回溯,是指不利用遞歸是指不利用遞歸,而是自己利用循環來而是自己利用循環來進行測試進行測試,以找到全部的放置方法。以找到全部的放置方法。012345671234561 迭代回溯的關鍵是迭代回溯的關鍵是:當我們找到一個放置方案后當我們找到一個放置方案后,如何如何繼續找到其它的方案繼續找到其它的方案?顯然顯然,可以從前向后或從后向可以從前向后或從后向前再試各行下一列的可行性。前

46、再試各行下一列的可行性。通常是從前向后找通常是從前向后找,若不可行若不可行,則從后向前回溯。據此知道，則從后向前回溯。據此知道，回溯到回溯到-1就應該結束了。就應該結束了。 562022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續)五、回溯算法五、回溯算法 2 迭代回溯算法迭代回溯算法 回溯過程中回溯過程中,需要注意以下幾個問題需要注意以下幾個問題:012345671234561找到一個可放置的位置本行未找到合適位置?本行找到一合適位置?已找到最后一行的位置? 572022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續)五、

47、回溯算法五、回溯算法 2 迭代回溯算法迭代回溯算法 若仍然用數組若仍然用數組X來存儲皇后的放置方案，則第來存儲皇后的放置方案，則第k行目行目前的方案是前的方案是k行行Xk列，取下一行和下一列的操作分別是列，取下一行和下一列的操作分別是k+和和Xk+。 1)當一行的方案全部試完當一行的方案全部試完(未找到合適位置未找到合適位置)? 回溯到上一行下一方案回溯到上一行下一方案: k-;Xk+; 2)當本行找到一合適位置？當本行找到一合適位置？是最后一行是最后一行?找下一行找下一行:計數計數,繼續迭代繼續迭代: Sum+,Xk+ k+;Xk=-1; 3)何時終止？何時終止？ N-1,2,1,0回溯完回

48、溯完: k=-1 582022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續) 2 迭代回溯迭代回溯五、回溯算法五、回溯算法初始化初始化當沒有全部找完當沒有全部找完取本行的下一列取本行的下一列當沒有找到合適位置當沒有找到合適位置取本行的下一列取本行的下一列找到一合適位置找到一合適位置?是最后一行是最后一行?計數器累計計數器累計試下一行試下一行回溯試上一行回溯試上一行(未找到未找到) 592022年4月8日8時08分3、回溯算法示例、回溯算法示例 1)N皇后問題皇后問題(續續) 2 迭代回溯迭代回溯五、回溯算法五、回溯算法k=0;Xk=-1while(k=0)X

49、k+whlie(XkN & !IsOk(k)Xk+Xk0， wi 0 ， vi 0，(0 i 左子樹目前已超載；左子樹目前已超載； 2右子樹目前已裝的與尚未裝的和不比已找到的大右子樹目前已裝的與尚未裝的和不比已找到的大（這一函數可確保最后找到的為最優解）。（這一函數可確保最后找到的為最優解）。 632022年4月8日8時08分五、回溯算法五、回溯算法3、回溯算法示例、回溯算法示例 2) 0-1背包問題（續）背包問題（續） 試裝第試裝第k件物品的遞歸回溯算法的件物品的遞歸回溯算法的N-S圖為：圖為：物品試完物品試完? 記錄當記錄當前最大前最大值值 第第k件可裝入件可裝入? 裝入第裝入第k

50、件件 統計剩余物品價值統計剩余物品價值 試裝下一件物品試裝下一件物品 第第k件能裝而不裝件能裝而不裝剩余物品會產生最優解剩余物品會產生最優解?(已裝已裝+剩余剩余)不裝第不裝第k件物品件物品試裝下一件物品試裝下一件物品 642022年4月8日8時08分1、分支限界法的基本思想、分支限界法的基本思想六、分支限界法六、分支限界法分支限界法類似于回溯法，也是一種在問題的解空分支限界法類似于回溯法，也是一種在問題的解空間樹上搜索最優解的算法。二者的主要區別是：回溯法主間樹上搜索最優解的算法。二者的主要區別是：回溯法主要是用來找全部的解，而分支限界法的目標常常是找出一要是用來找全部的解，而分支限界法的目

51、標常常是找出一個最優解。個最優解。由于分支限界法與回溯法的目標不同，就帶來了在由于分支限界法與回溯法的目標不同，就帶來了在空間樹中搜索的方式的不同。我們知道，回溯法采用的是空間樹中搜索的方式的不同。我們知道，回溯法采用的是深度優先探索，而分支限界法常用的探索方式有兩種：深度優先探索，而分支限界法常用的探索方式有兩種：1）普通隊列式（）普通隊列式（FIFO）；）； 2）優先隊列式）優先隊列式下面分別以下面分別以0-1背包問題為例來介紹其探索思想。背包問題為例來介紹其探索思想。 652022年4月8日8時08分五、回溯算法五、回溯算法 N=3,C=32,W=16,15,15 V=45,25,25的

52、的0-1背包背包問題回溯算法求解示意問題回溯算法求解示意:重重/值值16/4515/2515/25 C=300/016/4531/700/016/4531/70 16/4515/2530/5015/250/015/250/01、分支限界法的基本思想、分支限界法的基本思想:0-1背包問題背包問題46/95 31/70 顯然顯然,全部的解空間樹是一棵滿二叉樹全部的解空間樹是一棵滿二叉樹(完全二叉樹完全二叉樹)12346789101112513141530/50 662022年4月8日8時08分五、回溯算法五、回溯算法1、分支限界法的基本思想、分支限界法的基本思想:0-1背包問題背包問題231234

53、5678910 11 12 13 1411 12 13 14 15log2x=1物品物品1物品物品2物品物品3log2x=2log2x=3N件物品需要件物品需要多少個單元多少個單元?其中哪些是葉其中哪些是葉結點結點? 672022年4月8日8時08分五、回溯算法五、回溯算法 分支分支,限界限界:0/016/4531/700/016/4531/70 16/4515/2530/5015/250/015/250/01、分支限界法的基本思想、分支限界法的基本思想:0-1背包問題背包問題46/95 31/70123467891011125131415重重/值值16/4515/2

54、515/25 C=30 682022年4月8日8時08分重重/值值16/4515/2515/25 C=300/0/016/45/131/70/216/45/231/70/316/45/30/0/115/25/230/50/3 15/25/30/0/2六、分支限界法六、分支限界法2、分支限界法的算法演示：、分支限界法的算法演示：0-1背包問題背包問題(普通隊列式普通隊列式)0/0/016/45/1 0/0/1 16/45/2 15/25/2 0/0/2最后一層最后一層無子分支無子分支當前的加剩余當前的加剩余的未超過已求的未超過已求出的出的 692022年4月8日8時08分重重/值值16/4515

55、/2515/25 C=300/0/016/45/131/70/216/45/231/70/316/45/30/0/115/25/230/50/3 15/25/30/0/2六、分支限界法六、分支限界法2、分支限界法的算法演示：、分支限界法的算法演示：0-1背包問題背包問題(優先隊列式優先隊列式)0/0/016/45/1 0/0/1 16/45/2 15/25/2 0/0/2 702022年4月8日8時08分六、分支限界法六、分支限界法3、分支限界法運用示例、分支限界法運用示例布線問題布線問題在如圖所示的電路板中，設計一條在如圖所示的電路板中，設計一條A到到B的最短的路線的最短的路線AB 7120

56、22年4月8日8時08分六、分支限界法六、分支限界法3、分支限界法運用示例、分支限界法運用示例布線問題布線問題-設計一條設計一條A到到B的最短的路線的最短的路線-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1A-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1B-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-12121122333444445

57、55666777788888899999101010101010101111111111111212121213131313131314141414141415151515151616161616171717 722022年4月8日8時08分六、分支限界法六、分支限界法3、分支限界法運用示例、分支限界法運用示例-布線問題布線問題(續續)我們用一個二維數組我們用一個二維數組grid來存貯電路板的相關來存貯電路板的相關 信信息，比如：息，比如：-1表示邊界；表示邊界；0表示未布線；表示未布線；-2、-3、-4表表示已布的線；示已布的線；1、2、3、4用來標識搜索路徑；還需要用來標識搜索路徑；還需要

58、定義一個點的結構定義一個點的結構P(x,y)每一個點可向上、下、左、右四每一個點可向上、下、左、右四個方向搜索個方向搜索(0-3):Pxyoffsetxy00 -11012-1 0301 732022年4月8日8時08分六、分支限界法六、分支限界法3、分支限界法運用示例、分支限界法運用示例-布線問題布線問題(續續)初始化初始化當沒有搜索完當沒有搜索完對當前對點周邊每一方向對當前對點周邊每一方向空閑空閑?標號標號是終點是終點?退出退出入隊入隊隊空隊空?失敗失敗,退出退出出隊出隊:取下一頂點取下一頂點從當前編號到最小編號從當前編號到最小編號標記找到的路線標記找到的路線清理搜索用的編號清理搜索用的編號(