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

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

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

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

4、近的數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;算法但上面算法給出的結果為該算法非最優(yōu)的：背包問題假定有一個包可放N個物品，每個物品重值，包可以放的分量為W。使在不超重的情況下裝物品有最大的價值。例：背包可包容分量：為W=100；物品分量價值180202301534014運用貪婪法，那么只能放入一個物品：即物品1，價值20；顯然，最優(yōu)解為物品2和物品3：價值29假設允許分數的，那么可以找到最優(yōu)解。該問題是NP完全問題！物品分量價值單價160

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

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

7、y產生的作業(yè)調度如以下圖所示，所需的加工時間為17。最小生成樹性質用貪婪算法設計戰(zhàn)略可以設計出構造最小生成樹的有效算法。本節(jié)引見的構造最小生成樹的Prim算法和Kruskal算法都可以看作是運用貪婪算法設計戰(zhàn)略的例子。雖然這2個算法做貪婪選擇的方式不同，它們都利用了下面的最小生成樹性質：設G=(V,E)是連通帶權圖，U是V的真子集。假設(u,v)E，且uU，vV-U，且在一切這樣的邊中，(u,v)的權cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質有時也稱為MST性質。MST的證明.Prim算法設G=(V,E)是連通帶權圖，V=1,2,n。構造G的最小生成樹的P

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

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