算法設(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)東譯，機(jī)械衛(wèi)東譯，機(jī)械工業(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. 隨機(jī)算法隨機(jī)算法 6. 計算模型計算模型 7. NP完全問題完全問題 教學(xué)教學(xué)方式方式問題驅(qū)動，鼓勵實驗，強(qiáng)調(diào)探索，欣賞專欄問題驅(qū)動，鼓勵實驗，強(qiáng)調(diào)探索，欣賞專欄第一第一章：引論章：引論 兩個中心問題： 旅行商問題：在一個完全網(wǎng)絡(luò)中求長度最小的哈密爾頓回路。 0-1背包問題： 給定n種物品和一個背包，每個物品具有特定重量和價值，背包具有最大負(fù)荷重量，如何向背包中放入物品使得它們的總價值達(dá)到最大。 本學(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排列，也可以表示為集合元素下標(biāo)的全體組合。對組合問題求全體解的蠻力算法：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)