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

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

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

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

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

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

6、e return 0; 在沒有匹配勝利的時(shí)候，從下一個(gè)位置開場重新匹配。其實(shí)我們在嘗試匹配的時(shí)候，可以得到有關(guān)S的很多信息。KMP算法就可以充分利用這些信息串匹配的KMP算法 由D.E.Knuth,J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)。 假設(shè)我們在嘗試到T的第K的字符時(shí)失敗，那么闡明從i開場的k的字符就是T的一個(gè)前綴。 這個(gè)信息可以通知我們什么呢？ 我們可以預(yù)先求出這個(gè)信息：假設(shè)有一個(gè)串是T的長度為K的前綴，那么它的同樣為T的前綴的、最長真后綴有多長？ 假設(shè)長度為K，那么我們可以跳過K-K個(gè)符號(hào)，試圖匹配這個(gè)符號(hào)。 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個(gè)元素下標(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。 不斷迭代，到收斂為止。 這個(gè)算法可以得出正確結(jié)果，但是效率

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