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

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

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

4、m/2個(gè)，然后小紅給小明n/2個(gè)，結(jié)果小明吃了(m+n)/2個(gè)，小紅吃了(m-n)/2個(gè)。例2：雞兔同籠，共有頭m只，腿n只，問雞兔各幾只？(m, n是正整數(shù)，n是偶數(shù)，2mn4m)解答1 (搞笑法) ：訓(xùn)練雞兔聽從命令，然后讓它們抬起兩只腿，這樣雞兩腳朝天，兔如猿人兩腿直立，地上還有n-2m只腿, 因此有n/2-m只兔, 2m-n/2只雞.解答2 (調(diào)整法)：先設(shè)籠中全是雞, 此時(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è)計(jì)算法時(shí)應(yīng)該追求算法的通用性思考題1：一個(gè)16升的容器中裝滿了牛奶，另外有一個(gè)6升和一個(gè)11升的空容器，如何用它們來平分牛奶？提示：這是一個(gè)隱式圖搜索問題，圖搜索算法應(yīng)該設(shè)計(jì)成通用模塊，用它可以求解一大批趣味數(shù)學(xué)題，不同的題目有不同的后繼結(jié)點(diǎn)生成模塊，但它們?nèi)菀讓?shí)現(xiàn)。例如這一類的容器分液體問題可以有下面幾個(gè)變種：思考題1A: 小明拿著一個(gè)7升和一個(gè)11升的空容器來到水龍頭前，他如何才能帶回6升水呢？思考題1B: 小明拿著一個(gè)7升,一個(gè)13升和一個(gè)19升的空容器來到水龍頭前，他如何才能在兩個(gè)容器中各盛10升水呢？思

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

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

8、B的全體元素的和sum滿足某個(gè)性質(zhì)(廣義)。例如，在一個(gè)特定的區(qū)間a, b中，當(dāng)區(qū)間收縮成一個(gè)點(diǎn), a, a時(shí)，即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的情況下求狹義解時(shí)，子集40, 80, 100是一個(gè)解。優(yōu)化問題的蠻力算法：1 生成第一個(gè)候選對(duì)象；2 While (還有候選對(duì)象)3 if (當(dāng)前候選對(duì)象符合要求) break;4 else 生成下一個(gè)候選對(duì)象； 5 if (還有候選對(duì)象) 6 當(dāng)前最小對(duì)象指向當(dāng)前候選對(duì)象的拷貝；7 生成下一個(gè)候選對(duì)象；8 While (還有候選對(duì)象) 9 if (當(dāng)前候選對(duì)象符合要求 &當(dāng)前候選對(duì)象比當(dāng)前最小對(duì)象還小)10 當(dāng)前最小對(duì)象指向當(dāng)前候選對(duì)象的拷貝；11 生成下一個(gè)候選對(duì)象； 12 輸出當(dāng)前最小對(duì)象;欣賞專欄欣賞專欄-1：循環(huán)賽日程安排：循環(huán)