算法設(shè)計與分析20111

1、算法設(shè)計與分析2011-秋季學(xué)期秋季學(xué)期課程介紹課程介紹 教學(xué)教學(xué)參考書參考書1 M. H. Alsuwaiyel：Algorithms: Design Techniques and Analysis,電子電子工業(yè)出版社工業(yè)出版社影印本影印本, 1999.2 R.C.Lee, S.S.Tseng, Y.T.Tsai：算法設(shè)計與分析：算法設(shè)計與分析導(dǎo)論導(dǎo)論, 王王衛(wèi)東譯，機械衛(wèi)東譯，機械工業(yè)出版社，工業(yè)出版社，2005.3 Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein：算法：算法導(dǎo)論導(dǎo)論, MIT第第3

2、版版, 2009. 教學(xué)教學(xué)內(nèi)容內(nèi)容1. 引論引論 2. 分治法分治法 3. 動態(tài)規(guī)劃動態(tài)規(guī)劃 4. 集合算法集合算法5. 隨機算法隨機算法 6. 計算模型計算模型 7. NP完全問題完全問題 教學(xué)教學(xué)方式方式問題驅(qū)動，鼓勵實驗，強調(diào)探索，欣賞專欄問題驅(qū)動，鼓勵實驗，強調(diào)探索，欣賞專欄第一第一章：引論章：引論 兩個中心問題： 旅行商問題：在一個完全網(wǎng)絡(luò)中求長度最小的哈密爾頓回路。 0-1背包問題： 給定n種物品和一個背包，每個物品具有特定重量和價值，背包具有最大負荷重量，如何向背包中放入物品使得它們的總價值達到最大。 本學(xué)期要求對這兩個問題分別至少實現(xiàn)4種不同的算法并分析算法效率，對特定數(shù)據(jù)記

3、錄運行時間來驗證你的分析。1.1 特殊算法和通用算法特殊算法的例子：例1：小明和小紅共吃了m個蘋果，小明比小紅多吃了n個，小明和小紅各吃了幾個蘋果？(m, n是正整數(shù)，mn)解答1 (蠻力法)：因為mn, 說明小明沒把m個蘋果都吃了，小明最少吃了m/2+1(向下取整)個蘋果，最多吃了m-1個蘋果，在這些可能中檢查小明比小紅多吃了幾個，若多吃了n個，這就是答案。解答1的缺點：1. 若m值很大，比如10000，該方法太麻煩。(算法效率低)2. 有時無解，如m=10, n=3時, 6-4=2，7-3=4， 8-2=6，9-1=8哪個也不等于3。(算法失敗)解答2(調(diào)整法)：小明和小紅先平分蘋果，各得

4、m/2個，然后小紅給小明n/2個，結(jié)果小明吃了(m+n)/2個，小紅吃了(m-n)/2個。例2：雞兔同籠，共有頭m只，腿n只，問雞兔各幾只？(m, n是正整數(shù)，n是偶數(shù)，2mn4m)解答1 (搞笑法) ：訓(xùn)練雞兔聽從命令，然后讓它們抬起兩只腿，這樣雞兩腳朝天，兔如猿人兩腿直立，地上還有n-2m只腿, 因此有n/2-m只兔, 2m-n/2只雞.解答2 (調(diào)整法)：先設(shè)籠中全是雞, 此時缺n-2m腿，然后用兔子換雞，換一只多兩條腿，共需換n/2-m只，因此有n/2-m只兔, 2m-n/2只雞.通用算法的例子：高斯消元法解線性方程組。例1只需輸入矩陣(1, 1, m/1, -1, n),例2只需輸入

5、矩陣(1, 1, m/2, 4, n).結(jié)論：通用算法能頂一大堆特殊算法，所以在設(shè)計算法時應(yīng)該追求算法的通用性思考題1：一個16升的容器中裝滿了牛奶，另外有一個6升和一個11升的空容器，如何用它們來平分牛奶？提示：這是一個隱式圖搜索問題，圖搜索算法應(yīng)該設(shè)計成通用模塊，用它可以求解一大批趣味數(shù)學(xué)題，不同的題目有不同的后繼結(jié)點生成模塊，但它們?nèi)菀讓崿F(xiàn)。例如這一類的容器分液體問題可以有下面幾個變種：思考題1A: 小明拿著一個7升和一個11升的空容器來到水龍頭前，他如何才能帶回6升水呢？思考題1B: 小明拿著一個7升,一個13升和一個19升的空容器來到水龍頭前，他如何才能在兩個容器中各盛10升水呢？思

6、考題1C: 小明有兩個100毫升的容器中裝滿了牛奶，另外有一個40毫升和一個70毫升的空碗，如何用它們在兩個碗中各盛30毫升的牛奶，并且一點兒牛奶也不潑掉呢？要求：用一個通用圖搜索模塊和4個后繼結(jié)點生成模塊同時求解這4個問題，并自己找?guī)讉€其它的隱式圖搜索問題，如狼羊白菜過河等，利用通用圖搜索模塊求解。1.2 蠻力法思考題2：求一個4位數(shù)x和一個一位數(shù)y, 使得x與y的乘積z也是4位數(shù)，且x, y, z包含了所有1到9的數(shù)字。對組合問題求一個解的蠻力算法：1 生成第一個候選對象；2 While (還有候選對象)3 if (當(dāng)前候選對象符合要求) break;4 else 生成下一個候選對象； 5

7、 if (還有候選對象) 輸出當(dāng)前候選對象；注：(1)蠻力算法可以看作通用算法，只需實現(xiàn)一個遍歷器和檢查函數(shù)；(2) 常見的候選范圍包括全體允許重復(fù)的排列，全體不允許重復(fù)的排列，全體遞增排列(即組合)等，全集的全體子集可以表示為允許重復(fù)的0-1排列，也可以表示為集合元素下標的全體組合。對組合問題求全體解的蠻力算法：1 生成第一個候選對象；num=0;2 While (還有候選對象)3 if (當(dāng)前候選對象符合要求) 4 輸出當(dāng)前候選對象; +num; 4 生成下一個候選對象； 注：上述算法同時具有計數(shù)功能，如果只要求計數(shù)，只須刪去輸出語句。例：子集和數(shù)問題設(shè)A為正整數(shù)的集合，求A的子集, 使得

8、B的全體元素的和sum滿足某個性質(zhì)(廣義)。例如，在一個特定的區(qū)間a, b中，當(dāng)區(qū)間收縮成一個點, a, a時，即sum=a(狹義)。例: 在A=2, 7, 36, 40, 53, 59, 62, 69, 77, 80, 87, 89, 95, 98, 100, 102, 103, 106, 112, 115, a=220的情況下求狹義解時，子集40, 80, 100是一個解。優(yōu)化問題的蠻力算法：1 生成第一個候選對象；2 While (還有候選對象)3 if (當(dāng)前候選對象符合要求) break;4 else 生成下一個候選對象； 5 if (還有候選對象) 6 當(dāng)前最小對象指向當(dāng)前候選對象的拷貝；7 生成下一個候選對象；8 While (還有候選對象) 9 if (當(dāng)前候選對象符合要求 &當(dāng)前候選對象比當(dāng)前最小對象還小)10 當(dāng)前最小對象指向當(dāng)前候選對象的拷貝；11 生成下一個候選對象； 12 輸出當(dāng)前最小對象;欣賞專欄欣賞專欄-1：循環(huán)賽日程安排：循環(huán)