第六章基本算法設(shè)計策略——分治法ppt課件

1、VI、根本算法設(shè)計戰(zhàn)略根本戰(zhàn)略分治法貪婪法動態(tài)規(guī)劃法搜索戰(zhàn)略6.1分治法 快速排序算法的設(shè)計與分析快速變換:FFT及快速數(shù)論變換例：整數(shù)相乘N位整數(shù)相乘需求 次乘法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從而，僅需3次乘法即可完成該算法即STARSSEN矩陣乘法的來源 極大極小同時查找數(shù)組中的最大最小元用分治法處理上述問題：假設(shè)集合中只需1個元素，那么它既是最大值也是最小值；假設(shè)

2、有2個元素，那么一次比較可得到最大和最?。患僭O(shè)把集合分成兩個子集合，由兩組最大元比較得到最大元，兩組最小元比較得到最小元。遞歸的運(yùn)用這個算法！2FFT卷積：多項(xiàng)式的積： 及 ，并且 ，那么DFT定義：序列 的離散傅氏變換為該變換的逆變換為： 令 ，那么上式可寫為 ：其它的一個重要性質(zhì)：時域卷積對應(yīng)于頻域積。 多項(xiàng)式的積兩個多項(xiàng)式的積：其中此即卷積運(yùn)算； 序列運(yùn)算可用蝶形表示： 對于以下的8個的情形， 這一描畫復(fù)雜并且不直觀。 這一變換基于運(yùn)算中的性質(zhì)：從算法分析角度：于是：分別思索對其奇數(shù)項(xiàng)和偶數(shù)項(xiàng)作傅氏變換：那么 從而，可以將對N個量的傅氏變換變成為對兩個規(guī)模更小的序列在小為一半的變換。這樣

3、，將變換的量大大減小。 實(shí)踐計算時，留意到對另外一半 時：復(fù)雜度 令，那么得從而快速傅氏變換的復(fù)雜性度為運(yùn)用：大數(shù)乘法利用FFT計算積A=1634，B=9827即對A與B進(jìn)展逐一做積進(jìn)展反變換：舍入成整數(shù) ：數(shù)表示成 ： 即16057318 留意到能夠的截斷誤差，運(yùn)用數(shù)論變換更為適宜思索在模F的域上的變換：其中 ， 為在模F域上的逆。普通取F：Mersenne數(shù) 或Fermat數(shù)這樣即可免去誤差。缺陷：無直接的物理意義。數(shù)論變換數(shù)論變換取Fermat數(shù)F=257， 找到為反數(shù)論變換后得貪婪法以當(dāng)前的信息為根底做出最正確決策 Huffman編碼 例：分?jǐn)?shù)分解 給定分?jǐn)?shù) 分解為 其中算法：找到最接

4、近的數(shù)i=1Label2: If p=1 then k(i)=q stop1/k(i)=largest reciprocal less than p/qp/q=p/q-1/k(i)goto label2;算法但上面算法給出的結(jié)果為該算法非最優(yōu)的：背包問題假定有一個包可放N個物品，每個物品重值，包可以放的分量為W。使在不超重的情況下裝物品有最大的價值。例：背包可包容分量：為W=100；物品分量價值180202301534014運(yùn)用貪婪法，那么只能放入一個物品：即物品1，價值20；顯然，最優(yōu)解為物品2和物品3：價值29假設(shè)允許分?jǐn)?shù)的，那么可以找到最優(yōu)解。該問題是NP完全問題！物品分量價值單價160

5、200.333220100.5340120.3435110.314運(yùn)用貪婪法：價值：物品1、3，分量100，價值為32；單價：物品2、1，分量80，價值為30；最優(yōu)值：物品2、3、4，分量95，價值33例：TSP假定游覽商要訪問N個城市，每個城市都有到其它城市的路，要找一個最短的途徑。E12111012-ABCDEA-1091512B10-111311C911-1110D151311-12算法：在剩下的城市中找最近的點(diǎn)做為下一個目的；運(yùn)用貪婪法，從A出發(fā)得到的最短途徑：一個更好的選擇：活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪婪算法有效求解的很好例子。該問題要求高

6、效地安排一系列爭用某一公共資源的活動。貪婪算法提供了一個簡單、美麗的方法使得盡能夠多的活動能兼容地運(yùn)用公共資源。設(shè)有n個活動的集合E=1,2,n，其中每個活動都要求運(yùn)用同一資源，如演講會場等，而在同一時間內(nèi)只需一個活動能運(yùn)用這一資源。每個活動i都有一個要求運(yùn)用該資源的起始時間si和一個終了時間fi,且si m時，首先將n個作業(yè)依其所需的處置時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處置機(jī)。算法所需的計算時間為O(nlogn)。一個實(shí)例例如，設(shè)7個獨(dú)立作業(yè)1,2,3,4,5,6,7由3臺機(jī)器M1，M2和M3加工處置。各作業(yè)所需的處置時間分別為2,14,4,16,6,5,3。按算法greed

7、y產(chǎn)生的作業(yè)調(diào)度如以下圖所示，所需的加工時間為17。最小生成樹性質(zhì)用貪婪算法設(shè)計戰(zhàn)略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)引見的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是運(yùn)用貪婪算法設(shè)計戰(zhàn)略的例子。雖然這2個算法做貪婪選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。假設(shè)(u,v)E，且uU，vV-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的最小生成樹的P

8、rim算法的根本思想是：首先置S=1，然后，只需S是V的真子集，就作如下的貪婪選擇：選取滿足條件iS，j V-S，且cij最小的邊，將頂點(diǎn)j添加到S中。這個過程不斷進(jìn)展到S=V時為止。.在這個過程中選取到的一切邊恰好構(gòu)成G的一棵最小生成樹。利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T一直包含G的某棵最小生成樹中的邊。因此，在算法終了時，T中的一切邊構(gòu)成G的一棵最小生成樹。 例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下圖。例：算法改良在上述Prim算法中，還該當(dāng)思索如何有效地找出滿足條件iS,jV-S，且權(quán)cij最小的邊(i,j)。實(shí)現(xiàn)這個目的的較簡單的方法是設(shè)置2個

9、數(shù)組closest和lowcost。在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對closest和lowcost作必要的修正。用這個方法實(shí)現(xiàn)的Prim算法所需的計算時間為O(n2)。3、Kruskal算法Kruskal算法構(gòu)造G的最小生成樹的根本思想是，首先將G的n個頂點(diǎn)看成n個孤立的連通分支。將一切的邊按權(quán)從小到大排序。然后從第一條邊開場，依邊權(quán)遞增的順序查看每一條邊，并按下述方法銜接兩個不同的連通分支：當(dāng)查看到第k條邊(v,w)時，假設(shè)端點(diǎn)v和w分別是當(dāng)前兩個不同的連通分支T1和T2中的頂點(diǎn)時，就用邊(v,w)將T1和T2銜接成一個連通分支，然后繼續(xù)查看第k+1條邊；假設(shè)端點(diǎn)v和w在當(dāng)前的同一個連通分支中，就直接再查看第k+1條邊。這個過程不斷進(jìn)展到只剩下一個連通分支時為止。例如，對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖。闡明有關(guān)闡明：關(guān)于集合的一些根本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。按權(quán)的遞增順序查看等價于對優(yōu)先隊列執(zhí)行deleteMin運(yùn)算?？梢杂枚褜?shí)現(xiàn)這個優(yōu)先隊