算法設(shè)計的基本思路ppt課件

1、算法設(shè)計的根本思緒趙建華南京大學(xué)計算機系一些根本思緒 復(fù)用已有的計算結(jié)果 經(jīng)過預(yù)處置或改動計算方法，計算出可共用的中間結(jié)果 防止或減少無效的計算保管/查詢中間計算結(jié)果的方法 待求解的問題可以逐層分解成多個小問題； Q分解成為Q1，Q2，Qn Qi分解成為Qi1，Qi2，Qim 假設(shè)Qij之間有很多重合的地方，那么我們可以在第一次求解Qij的時候記錄結(jié)果，并且在之后經(jīng)過查詢來防止反復(fù)求解Qij。 在運用中，有某個問題需求多次求解。且每次求解有很多可以反復(fù)利用的情況。 這個可以看作是上面一個問題的衍生情況。保管/查詢的例子1 棋類博弈問題 每個玩家的得分是他的最大塊棋子的個數(shù)。 得分高的人博得競賽

2、。 問題：當(dāng)棋盤上只需10個空格的時候，求能否某人一定贏。描畫運用一個Config數(shù)據(jù)構(gòu)造來描畫棋局記錄了各個棋子的位置；記錄了下一步誰下最根本的博弈遞歸函數(shù)boolean win(Configure cfg)if(cfg是最終結(jié)局)計算各個player的得分，并前往勝負(fù)結(jié)果for(每個能夠的后繼結(jié)局cfg)if(!win(cfg)return true；/存在使對方必輸?shù)淖叻╮eturn false中間結(jié)果的保管 Configure數(shù)據(jù)類型最多有1024個取值。 win函數(shù)的計算過程：有10!個執(zhí)行軌跡，因此必然有很多次反復(fù)的計算過程。 處理方法： 運用數(shù)據(jù)結(jié)果保管各個Configure的結(jié)

3、果； win函數(shù)在每次調(diào)用之前首先查詢，假設(shè)曾經(jīng)計算過那么不需求查詢； 在調(diào)用前往之前，將此結(jié)果存放到map中 保證了每個Configure只需求計算一次 如何保管結(jié)果？偽代碼boolean win(int playerNo, Configure cfg)if(map(PlayerNo, cfg)有定義)return map(PlayerNo, cfg)if(cfg是最終結(jié)局)計算各個player的得分，并前往勝負(fù)結(jié)果for(每個能夠的后繼結(jié)局cfg)if(!win(1-playerNo, Configure cfg)/存在使對方必輸?shù)淖叻▽ap(PlayerNo, cfg)設(shè)置為true；

4、return true；將map(PlayerNo, cfg)設(shè)置為falsereturn false；進一步思索 可以改動計算得分的方法來提高效率。 只需最終格局才可以算出最后的得分，但是 一個格局可以生成多個后繼格局； 可以改動計算得分的方法 對于每個格局，計算中間結(jié)果：分成多少相連的塊，每塊的棋子個數(shù)是多少； 后繼格局的中間結(jié)果可以根據(jù)前驅(qū)格局的結(jié)果快速計算得到； 。另一個情況 對于某個數(shù)據(jù)類型D，我們需求計算其函數(shù)值f，且f(D)定義為F(g(D1),g(D2),g(Dn)，其中 Di是D的數(shù)據(jù)分量，或者是D的一部分。 那么，我們可以給每個數(shù)據(jù)分量添加一個額外的cache域g。 當(dāng)ca

5、che有效時，g的值就等于g(Di)。 當(dāng)Di的值被修正時，Di.g的值無效。 計算f的時候，假設(shè)Di.g的值有效，那么不需求計算g(Di)；否那么在計算g(Di)之后，將Di.g設(shè)置為結(jié)果值。 當(dāng)f的執(zhí)行次數(shù)較多，而對Di的修正相對不頻繁的時候，這個技術(shù)適用。 大家思索一下排版的算法如何提高效率。假設(shè)一個字符就是一個box字符串匹配算法原始匹配算法int Index(String S,String T,int pos) i=pos;j=1;/這里的串的第1個元素下標(biāo)是1 while(i=S.Length & jT.Length) return i-T.Length;/匹配勝利 els

6、e return 0; 在沒有匹配勝利的時候，從下一個位置開場重新匹配。其實我們在嘗試匹配的時候，可以得到有關(guān)S的很多信息。KMP算法就可以充分利用這些信息串匹配的KMP算法 由D.E.Knuth,J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)。 假設(shè)我們在嘗試到T的第K的字符時失敗，那么闡明從i開場的k的字符就是T的一個前綴。 這個信息可以通知我們什么呢？ 我們可以預(yù)先求出這個信息：假設(shè)有一個串是T的長度為K的前綴，那么它的同樣為T的前綴的、最長真后綴有多長？ 假設(shè)長度為K，那么我們可以跳過K-K個符號，試圖匹配這個符號。 KMP的關(guān)鍵是求出K到K的映射，它和S無關(guān)KK 串S：KMP的總體

7、算法int Index_KMP(String S,String T,int pos) i=pos;j=1;/這里的串的第1個元素下標(biāo)是1 while(i=S.Length & jT.Length) return i-T.Length;/匹配勝利 else return 0; KMP的NEXTvoid get_nextval(String T,int &next) i=1;j=0;next1=0; while(i j ) return 0;if(node.rightBnd Dw+Mw,v，那么將Dv修正為Dw+Mw,v。 不斷迭代，到收斂為止。 這個算法可以得出正確結(jié)果，但是效率

8、差。 緣由是有很多無效的計算 在迭代中得到了某個結(jié)點w的某個Dw之后，很能夠以后會被覆蓋掉。而由這個Dw 產(chǎn)生的其他途徑長度也會被覆蓋掉。這些計算過程都是無效的。例子 假設(shè)首先按照abc，abe這樣的計算過程，那么計算得到的a-c，a-e的間隔都是無效的。521543abcedf盡能夠地減少無效值的計算Dijkstra的最短途徑算法算法：、 在中選擇一個k最小的結(jié)點k，將k并入，并從中去掉，假設(shè)為那么轉(zhuǎn)到；、 用k結(jié)點和中其他結(jié)點進展一遍比較，假設(shè)DiDk+Mki，那么用Dk+Mki取代原來的i，反復(fù)；、算法終了，此時m中保管的就是從到m結(jié)點的最短途徑。 原理：每次被參與到S的結(jié)點k的Dk值不會被改動。例子1 POJ2227 The Wedding Juicer 由高度不一，底部為單位正方形的木柱組成的一個正方形； 問這樣的正方形可以裝多少液體； 某個木柱上方可以存放的液體的高度相當(dāng)于最小的從該木柱到達邊緣的途徑上的最高高度。 可以運用類似于Dijkstra算法的思想處理；244564132515378107921045