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

1、VI、基本算法設(shè)計(jì)策略基本策略分治法貪婪法動(dòng)態(tài)規(guī)劃法搜索策略6.16.1分治法分治法快速排序算法的設(shè)計(jì)與分析快速變換: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矩陣乘法的來(lái)源極大極小?同時(shí)查找數(shù)組中的最大最小元用分治法解決上述問(wèn)題：如果集合中只有1個(gè)元素，則它既是最大值也是最小值；如果有2個(gè)元素，則一次比較可得到最大和最?。蝗绻鸭戏殖蓛蓚€(gè)子集合，由兩組最大元比較得到最大元，兩組最小元比較得到最小元。遞歸的應(yīng)用這個(gè)算法！?nn? ? ?T(n )?T?T?2? ? ?22? ? ?T(1)?0,T(2)?1?3T(n) ?n? 222FFT卷積：多項(xiàng)式的積：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，則上式可寫(xiě)為 ：knXk ?xnWNn?0N?11xn ?N?XkWk?0N?1?nkN其它的一個(gè)重要性質(zhì)：時(shí)域卷積對(duì)應(yīng)于頻域積。多項(xiàng)式的積兩個(gè)多項(xià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此即卷積運(yùn)算；序列運(yùn)算可用蝶形表示：對(duì)于以下的8個(gè)的情形，這一描述復(fù)雜并且不直觀。W?1這一變換基于運(yùn)

4、算中的性質(zhì)：從算法分析角度：NNN ?1n?0?12knNn?0NN( 2n?1)kXk ?xnW?x2n ?W?x2n ? 1 ? W?N?122nkNn?0于是：分別考慮對(duì)其奇數(shù)項(xiàng)和偶數(shù)項(xiàng)作傅氏變換：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從而，可以將對(duì) N個(gè)量的傅氏變換變成為對(duì)兩個(gè)規(guī)模更小的序列（在小為一半）的變換。這樣，將變換的量大大減小。N實(shí)際計(jì)算時(shí)，注意到對(duì)另外一半k?時(shí)：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計(jì)算積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對(duì)A與B進(jìn)行逐一做積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)進(jìn)行反變換：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)截?cái)嗾`差，使用數(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 ?這樣即可免去誤差。缺陷：無(wú)直接的物理意義。數(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)貪婪法貪婪法以當(dāng)前的信息為基礎(chǔ)做出最佳決策Huffman編碼例：分?jǐn)?shù)分解給定分?jǐn)?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背包問(wèn)題假定有一個(gè)包可放 N個(gè)物品，每個(gè)物品Oi重wi值vi，包能夠放的重量為 W。使在不超重的情況下裝物品有最大的價(jià)值。例：背包可容納重量：為 W=100；物品123重量803040價(jià)值201514使用貪婪法，則只能放入一個(gè)物品：即物品1，價(jià)值20；顯然，最優(yōu)解為物品2和物品3：價(jià)值29如果允許分?jǐn)?shù)的，則可以找到最優(yōu)解。該問(wèn)題是NP完全問(wèn)

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

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

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

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

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