《算法設(shè)計(jì)與分析5.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、算法設(shè)計(jì)與分析基礎(chǔ)IntroductiontotheDesignandAnalysisofAlgorithms第五章減治法DecreaseandConquer第5章減治法算法策略插入排序深度優(yōu)先搜索DFS廣度優(yōu)先搜索BFS拓?fù)渑判蛏山M合對(duì)象減常因子法減可變規(guī)模法概念與算法策略算法策略減治法：利用給定規(guī)模與較小規(guī)模問(wèn)題解之間的關(guān)系求解問(wèn)題的方法。實(shí)現(xiàn)——自頂向下：規(guī)模減?。ㄟf歸）自底向上：規(guī)模增大（非遞歸）減常量法：常量通常為1（減1法）減常因子法：常因子通常為2（減半法）減可變規(guī)模法：每次減去的規(guī)模不同原問(wèn)題(規(guī)模n)子問(wèn)題(規(guī)模n-1)子問(wèn)題解原問(wèn)題解減一技術(shù)子問(wèn)題(規(guī)模n/2)子問(wèn)題解

2、原問(wèn)題解原問(wèn)題(規(guī)模n)減半技術(shù)×插入排序插入排序?qū)個(gè)元素A[0,...,n-1]排序（非降序?yàn)槔p一策略——分析過(guò)程自頂向下（規(guī)模減小）減去一個(gè)元素A[n-1],對(duì)A[0,...,n-2]排序（非降序）原問(wèn)題的解=減一規(guī)模的解+A[n-1]對(duì)數(shù)組遞歸減一，分解到僅一個(gè)元素為止；再合并得到原問(wèn)題解。插入算法——有三種方法插入一個(gè)元素，左右掃描稱直接插入法左掃描：從左向右掃描有序子數(shù)組，遇到第一個(gè)≥A[n-1]元素為止，在該元素前插入A[n-1].若未找到，則插在最后。右掃描：從右向左掃描有序子數(shù)組，遇到第一個(gè)≤A[n-1]元素為止，在該元素后插入A[n-1].若未找到，則插在最前。常用：

3、右掃描法。問(wèn)：理由是什么？理由：子數(shù)組若有等值元素，右掃描插入時(shí)需移動(dòng)的元素個(gè)數(shù)少?！逶诘戎翟睾?，前面等值元素都不用移動(dòng)位置插入排序算法與算例折半插入法——組合利用減一法和減半法子數(shù)組有序，用折半查找為插入元素在其中找到一個(gè)合適的位置。算法偽碼基于遞歸思想設(shè)計(jì)，但非遞歸實(shí)現(xiàn)（從底向上）下劃線為待插元素思考：為什么是右掃描插入V？插入排序效率分析插入排序效率分析輸入規(guī)模：元素個(gè)數(shù)n基本操作：比較操作A[j]>V效率類別：輸入A為升序，每次插入只需比較1次——最佳效率輸入A為降序——最差效率，其他——平均效率最佳效率：要插入n-1個(gè)元素，共需比較n-1次（線性效率）也可據(jù)偽碼計(jì)算：最差效

4、率對(duì)每個(gè)元素如第i個(gè)元素插入，從j=i-1比較到j(luò)=0，共i次比較，即插入元素A[i]要與前面的全部元素都比較一次。平均效率：比最差效率快2倍。若遇到基本有序數(shù)組，比選擇排序和冒泡排序的性能略優(yōu)。圖的遍歷深度優(yōu)先搜索DFS(Depth-FirstSearch)隨后兩節(jié)討論圖的一些常用算法，可看作是減一技術(shù)的應(yīng)用。圖是一種令人感興趣的、有著廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)。許多實(shí)際問(wèn)題的計(jì)算模型——圖結(jié)構(gòu)1.領(lǐng)土問(wèn)題2.交通網(wǎng)絡(luò)3.通信網(wǎng)絡(luò)4.棋局、迷宮……圖的遍歷——從起點(diǎn)出發(fā)訪問(wèn)所有頂點(diǎn)?？赡苡龅降膯?wèn)題：1.非連通圖：不能訪問(wèn)到某些頂點(diǎn)。2.存在回路：要防止陷入死循環(huán)?！獮槊總€(gè)頂點(diǎn)設(shè)置訪問(wèn)標(biāo)志(mar

5、k).開始時(shí)：所有頂點(diǎn)的訪問(wèn)標(biāo)志置零遍歷時(shí)：已訪問(wèn)頂點(diǎn)的標(biāo)志被標(biāo)記，以后不訪問(wèn)它，防止回路循環(huán)結(jié)束時(shí)：檢查頂點(diǎn)標(biāo)志。若有未標(biāo)記頂點(diǎn)，則重選起點(diǎn)，繼續(xù)遍歷深度優(yōu)先搜索DFS許多圖的算法要求對(duì)圖進(jìn)行遍歷或周游(graphtraversal).主要兩種：DFS(Depth-FirstSearch),BFS(Breadth-FirstSearch).DFS深度優(yōu)先搜索過(guò)程簡(jiǎn)述從任一頂點(diǎn)（問(wèn)題確定）出發(fā)，沿某一路徑搜索該路徑上所有未訪問(wèn)頂點(diǎn)，到達(dá)死端（所有相鄰頂點(diǎn)都已訪問(wèn)過(guò)），沿原路后退一條邊，從那里繼續(xù)訪問(wèn)未訪問(wèn)過(guò)的頂點(diǎn)（回溯）；當(dāng)回溯到開始頂點(diǎn)，并且它成為死端時(shí)，DFS過(guò)程結(jié)束。頂點(diǎn)選擇策略：搜索

6、過(guò)程中，若某頂點(diǎn)有多個(gè)鄰接頂點(diǎn)，可以按頂點(diǎn)編號(hào)（或其他策略如優(yōu)先值大小選擇頂點(diǎn)）進(jìn)行訪問(wèn)，下頁(yè)圖示。DFS搜索的非遞歸實(shí)現(xiàn)——棧過(guò)程1.當(dāng)前頂點(diǎn)入棧2.將棧頂頂點(diǎn)的下一個(gè)未訪問(wèn)鄰接頂點(diǎn)入棧若棧頂頂點(diǎn)無(wú)未訪問(wèn)鄰接頂點(diǎn)，該頂點(diǎn)退棧（回溯）3.重復(fù)2，直到?？諡橹?，DFS過(guò)程結(jié)束DFS算法構(gòu)造出一棵DFS樹（或森林）DFS算法過(guò)程圖示DFS算法過(guò)程圖示（以樹為例）12345678910111213141516171819202122根據(jù)訪問(wèn)順序，用連續(xù)整數(shù)標(biāo)記各個(gè)頂點(diǎn)，如圖。紅色箭頭表示回溯過(guò)程。DFS算法的棧過(guò)程圖示DFS棧過(guò)程圖示AEBCDF從頂點(diǎn)A開始DFSACABCAFBCADFBCAEF

7、BCAFBCABCACAAFBCA頂點(diǎn)選擇策略——未訪問(wèn)鄰接頂點(diǎn)有多個(gè)，按頂點(diǎn)編號(hào)的字母序訪問(wèn)。?？諘r(shí)，DFS遍歷結(jié)束。DFS可產(chǎn)生進(jìn)棧、退棧兩種頂點(diǎn)線性序列，可按實(shí)際情況的需要選用。頂點(diǎn)進(jìn)棧的線性序列：ACBFDE頂點(diǎn)退棧的線性序列：DEFBCADFS樹與森林DFS樹與森林DFS可構(gòu)造出一棵深度優(yōu)先搜索樹（可轉(zhuǎn)換為有根樹）或森林樹邊：圖中當(dāng)前頂點(diǎn)到未訪問(wèn)兒子頂點(diǎn)的邊，如CB,FE回邊：圖中當(dāng)前頂點(diǎn)到已訪問(wèn)祖