基本算法設(shè)計策略分治法

1、VI、基本算法設(shè)計策略基本策略分治法貪婪法動態(tài)規(guī)劃法搜索策略6.16.1分治法分治法快速排序算法的設(shè)計與分析快速變換:FFT及快速數(shù)論變換例：整數(shù)相乘N位整數(shù)相乘需要O(N2)次乘法4837*5261=4837=48*100+37=100*w+x5261=52*100+61=100*y+z4837*5261=(100*w+x)*(100*y+z)=10000wy+100(wz+xy)+xz(w+x)(y+z)=wy+(wz+xy)+xz)z?y)(x?w(r ?wy?p?xz?q?q?)q?p?r(10?p10) ?z?y10)(x?w10(2242從而，僅需3次乘法即可完成該算法即STARS

2、SEN矩陣乘法的來源極大極小?同時查找數(shù)組中的最大最小元用分治法解決上述問題：如果集合中只有1個元素，則它既是最大值也是最小值；如果有2個元素，則一次比較可得到最大和最??；如果把集合分成兩個子集合，由兩組最大元比較得到最大元，兩組最小元比較得到最小元。遞歸的應(yīng)用這個算法！?nn? ? ?T(n )?T?T?2? ? ?22? ? ?T(1)?0,T(2)?1?3T(n) ?n? 222FFT卷積：多項式的積：ikA(x)?ax及B(x) ? A(x)B(x) ?c x，(x) ?bi?kix，并且Cminm? nk? 0i?0i?0ajbk? j則ck?j?0k?xi,i ? 0,? ,N?1

3、DFT定義：序列的離散傅氏變換為?X k ?xne?n?0N?1? jnk2?N?jnk 2?N該變換的逆變換為：x?n ?X k eN ?11Nk? 0令WN? e? j2?N，則上式可寫為 ：knXk ?xnWNn?0N?11xn ?N?XkWk?0N?1?nkN其它的一個重要性質(zhì)：時域卷積對應(yīng)于頻域積。多項式的積兩個多項式的積：A( x)?ajxj?0n?1jB(x) ?bjxj?0m ?1jC(x) ? A(x)B(x) ?c x?jjj?0n?m ?2a其中cj?kbj? kk?0j此即卷積運算；序列運算可用蝶形表示：對于以下的8個的情形，這一描述復(fù)雜并且不直觀。W?1這一變換基于運

4、算中的性質(zhì)：從算法分析角度：NNN ?1n?0?12knNn?0NN( 2n?1)kXk ?xnW?x2n ?W?x2n ? 1 ? W?N?122nkNn?0于是：分別考慮對其奇數(shù)項和偶數(shù)項作傅氏變換：E2nknkX k?x2n? W?x2n? W?N?N/2n?0n?0N?12N?12X k?x2n?1? W?x2n?1? W?On?0N?12N?122nkNn?0knN/2則knEkOXk ?xnW? X k? W ?X k?NNn?0N?1從而，可以將對 N個量的傅氏變換變成為對兩個規(guī)模更小的序列（在小為一半）的變換。這樣，將變換的量大大減小。N實際計算時，注意到對另外一半k?時：2N

5、X? k ?xnW?2n?0N?12n?0N?12n?0N?1N(?k)n2Nknn?xnW W?xnW?(?1)?Nn?0N?1nNN?1kn2NNn?02nk(2n?1)k?x2n?W?x2n? 1? W?N?NNEkOX? k?xnW? X k?W ?X k?N2n?0N?1N(?k)n2N復(fù)雜度NN?T(N) ? 2T() ?22?T(2) ? 0?m，則得令N ? 2T(2 )?(m ?1)2mm ?1從而快速傅氏變換的復(fù)雜性度為O(Nlog N)應(yīng)用：大數(shù)乘法利用FFT計算積A=1634，B=9827b ? b ? (7,2,8,9,0,0,0,0)a a ? a ? (4,3,6

6、,1,0,0,0,0)b0170172i11W? exp() ? i8822?0.71? 0.71i即W8?AAAAAAA0? 14? ? 2 ? 2i? 2.58 ? 3.16 i? 6? 2.58 ? 3.16 i? ? 2 ? 2i? 5.42 ? 8.54 iA1? 5.42 ? 8.84 i234567B?(26,2.03?15.81 i,?1?7i,11.97?0.19i,4,11.97?0.19i,?1?7i,2.03?1 .8 i)a對A與B進行逐一做積ci?i?biC ? (364,?128.76 ?103.64i,16 ?12i,30.28 ? 38.32i,24,30.2

7、8 ? 38.32i,16 ?12i,?12 .76 ?1.6 i)進行反變換：c ?(27.88,28.86,79.99,79.32,77.12,62.13,9.01,?0.32)舍入成整數(shù) ：c ? (28,29,80,79,77,62,9,0)數(shù)表示成 ：ic ? 10?ii?07c ? (28,29,80,79,77,62,9,0)c ? (8,31,80,79,77,62,9,0)c ? (8,1,83,79,77,62,9,0)c ? (8,1,3,87,77,62,9,0)c ? (8,1,3,7,85,62,9,0)c ? (8,1,3,7,5,70,9,0)c16057318

8、? (8,1,3,7,5,0,16,0)c ? (8,1,3,7,5,0,6,1)截斷誤差，使用數(shù)論變換更為適合即注意到可能的數(shù)論變換考慮在模F的域上的變換：Xk ?xn?n?0N?1k?0N?1knxn ? NN?1?Xk? nk其中?1(modF)，N為在模F域上的逆。p2 ?1一般取F：Mersenne數(shù)Mp?t或Fermat數(shù)2?1F1t?2 ?這樣即可免去誤差。缺陷：無直接的物理意義。數(shù)論變換?NN ? 8,? 4?(mod F)取Fermat數(shù)F=257，找到為? 1a a ? a ? (4,3,6,1,0,0,0,0)017b b ? b ? (7,2,8,9,0,0,0,0)0

9、17?14?193? ?64(mod257)?18?225? ?32(mod 257)11?14?2?14?314?T?48?14?5?14?614?7?14?112344111111111111 ?45674444 ?141664?1? 4?16? 64?46101214?441444?116?1?16116?1?16?6912151821444444?164?164?1? 6416? 4 ?(mod257)?1220281?11?11?11?1?141414?101520253035?1? 416? 64?14?1664444444?12183036421?16?1161?16?11644

10、1444?1421283542491? 64?16? 4?164164444444?反數(shù)論變換后得T a(14,?81,30,104,6,24,?34,?31)8Tb? (26,?52,?113,43,4,65,111,?28)8(T a)(T b) ? (107,100,?49,103,24,18,81,?31)88c ? (28,29,80,79,77,62,9,0)貪婪法貪婪法以當前的信息為基礎(chǔ)做出最佳決策Huffman編碼例：分數(shù)分解給定分數(shù)p分解為其中qp111q?k? ?1k2kn1? k2? ? kn25?113?1557?1112?5?70k算法算法：找到最接近的數(shù)i=1Lab

11、el2: If p=1 then k(i)=q stop1/k(i)=largest reciprocal less than p/qp/q=p/q-1/k(i)goto label2;該算法非最優(yōu)的：但上面算法給出的結(jié)果為811?15230811?1535背包問題假定有一個包可放 N個物品，每個物品Oi重wi值vi，包能夠放的重量為 W。使在不超重的情況下裝物品有最大的價值。例：背包可容納重量：為 W=100；物品123重量803040價值201514使用貪婪法，則只能放入一個物品：即物品1，價值20；顯然，最優(yōu)解為物品2和物品3：價值29如果允許分數(shù)的，則可以找到最優(yōu)解。該問題是NP完全問

12、題！物品1234重量60204035價值20101211單價0.3330.50.30.314使用貪婪法：價值：物品1、3，重量100，價值為32；單價：物品2、1，重量80，價值為30；最優(yōu)值：物品2、3、4，重量95，價值33例：TSP假定旅行商要訪問N個城市，每個城市都有到其它城市的路，要找一個最短的路徑。算法：在剩下的城市中找最近的點做為下一個目標；AABCD-10915B10-1113C911-11D151311-E12111012E12111012-使用貪婪法，從 A出發(fā)得到的最短路徑：910111315A? ? C? E? B? D? Acos t ? 9 ? 10 ? 11 ?

13、13 ? 15 ? 5一個更好的選擇：1011111212A? ? B? ? C? ? D? ? E? ? Acost?10?11?11?12?12?5活動安排問題? 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。? 設(shè)有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動 i都有一個要求使用該資源的起始時間 si和一個結(jié)束時間fi,且sim時，首

14、先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn )。一個實例? 例如，設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。最小生成樹性質(zhì)? 用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的 Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：? 設(shè)G=(V,E

15、)是連通帶權(quán)圖，U是V的真子集。如果(u,v)?E，且u?U，v?V-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在 G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。? MST的證明.Prim算法? 設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。? 構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，j V-S，且cij最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。.? 在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。? 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易

16、證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此，在算法結(jié)束時，T中的所有邊構(gòu)成G的一棵最小生成樹。? 例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如圖所示。例：算法改進? 在上述Prim算法中，還應(yīng)當考慮如何有效地找出滿足條件i?S,j?V-S，且權(quán)cij最小的邊(i,j)。實現(xiàn)這個目的的較簡單的辦法是設(shè)置2個數(shù)組closest和lowcost。? 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對closest和lowcost作必要的修改。? 用這個辦法實現(xiàn)的Prim算法所需的計算時間2為O(n)。3、Kruskal算法? Kruskal算法構(gòu)造G的最小生成樹的基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權(quán)從小到大排序 。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法 連接兩個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前兩個不同的連通分支 T1和T2中的頂點時，就用邊 (v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第 k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第 k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。? 例如，對前面的連通帶權(quán)圖，