《演算法简介》PPT课件.ppt

演算法簡介 1 第二十章演算法簡介 知己知彼 百戰不貽 孫子 演算法簡介 2 內容 前言20 1演算法分析20 2個別擊破策略20 3貪婪策略20 4動態規劃20 5刪除與搜尋策略20 6課後習題20 7欲罷不能 演算法簡介 3 前言 演算法 Algorithm 電腦上解決問題的方法包括明確的輸出入資料和詳細且有限的執行步驟了解每個演算法在不同狀況下所花的時間 而從中挑選適合的演算法以迅速得到答案演算法設計策略 演算法簡介 4 20 1演算法分析 在電腦上解決問題的基本架構演算法以程式描述後在電腦上執行 資料輸入至程式後 經過程式對資料的運算 最後產生解答 演算法簡介 5 時間複雜度 TimeComplexity 假設演算法A能解問題P問題P的輸入資料量為N假設資料量為N的資料樣本 DataInstance 有D1 D2 Di Dm共m種令T Di 表示當輸入資料為Di時演算法A要執行的運算或步驟的總次數演算法A的最好狀況時間複雜度 Best CaseTimeComplexity T Di 1 i m 中最小的值 即min1 i m T Di 演算法簡介 6 時間複雜度 cont 演算法A的最差狀況時間複雜度 Worst CaseTimeComplexity T Di 1 i m 中最大者 即max1 i m T Di 演算法A的一般狀況時間複雜度 Average CaseTimeComplexity T Di 1 i m 的平均值或期望值 在某機率假設下 說 演算法A的時間複雜度為C 就是指其最差狀況時間複雜度為C 演算法簡介 7 時間複雜度 cont 範例若問題P之輸入資料量為N的樣本有D1 D2 D3三種 且T D1 3 T D2 N T D3 N3演算法A的最好狀況時間複雜度為3演算法A的最差狀況為N3演算法A的一般狀況為 3 N N3 3稱演算法A的時間複雜度為N3 演算法簡介 8 漸近上限 AsymptoticUpperBound O階次 如果存在某固定正實數c及某個非負整數m使得對所有的n m 不等式g n c f n 都成立 則g n O f n 稱f n 為g n 的漸近上限Example N2 10N O N2 因為當n 10時 N2 10N 2N2稱N2為N2 10N的漸進上限 演算法簡介 9 漸近下限 AsymptoticLowerBound 階次 若存在某固定正變數c及某非負整數m使得對所有nm 不等式g n c f n 都成立 則g n f n 稱f n 為g n 的漸近下限Examplen3 n2 因為當n 1時 n31 n2 所以n2為n3的漸近下限 演算法簡介 10 真正階次 ExactOrder 若存在某固定正變數c及某非負整數m使得對所有nm 不等式g n c f n 都成立 則g n f n 稱f n 為g n 的漸近下限ExampleN2 10N N2 因為N2 10N O N2 且N2 10N N2 演算法簡介 11 真正階次 cont 當n足夠大時 2n n3 n2 nlogn n logn 演算法簡介 12 指數函數分析 指數函數 ExponentialFunction 例如 f n cp n 其中c為常數 p n 為n的多項式函數 PolynomialFunction 如n n2 10 log2n nlog2n Example 2n 3n 4logn等函數函數值上升速度相當快時間複雜度為指數函數階次的演算法在資料量足夠多時需要相當長的時間才能解得答案 演算法簡介 13 多項式時間演算法 Polynomial TimeAlgorithm 時間複雜度是O p n 的演算法 其中p n 為n的多項式函數電腦上可解 Tractable 的問題能用多項式時間演算法解得答案的問題 即能用電腦在合理時間內求得答案例如 排序及搜尋等問題 演算法簡介 14 排序法及搜尋法的時間複雜度 演算法簡介 15 最佳演算法 OptimalAlgorithm 若可解問題P的演算法A的時間複雜度為t 而解問題P的演算法最少需要t時間 則稱演算法A是解問題P的最佳演算法例如 兩兩合併排序法是最佳排序演算法排序n個數的問題最少需要O nlog2n 時間兩兩合併排序法的時間複雜度是O nlog2n 演算法簡介 16 難解問題 IntractableProblem 若問題P無法以多項式時間演算法解得答案 則問題P無法於電腦上在合理時間內求得答案 稱問題P為難解問題 或NP Complete問題Example旅行推銷員問題 TravellingSalesmanProblem 圖形塗色問題 Graph ColoringProblem 裝箱問題 Bin PackingProblem 演算法簡介 17 20 2個別擊破策略 Divide and ConquerMethod 將原來的問題P分解成2個或多個子問題待個別解決這些子問題後再經由合併 merge 處理 整理出原來問題的答案 因為分割後的子問題是資料量較小的問題P 因此解子問題時又可遞迴應用上述的方法 經由分割及合併的過程得到解答Example 二分搜尋法 兩兩合併排序法 演算法簡介 18 兩兩合併排序法 一開始就將資料分割成兩部份處理 然後再遞迴細分各資料直至不能細分為止接著就兩兩合併成排序的序列 慢慢的將分割的資料合併成排序的序列 最後得到所有資料的排序結果 演算法簡介 19 二分搜尋法 假設陣列D中依序放有4 3 5 2 6 7 1等七個整數 目標是將這些數依小到大順序排序首先觀察第一個數4在最後排序好的序列中應是第四位 即應放在D 4 如果能將不大於4的數放在D 1 至D 3 中 而不小於4的數放在D 5 至D 7 中 則只要再分別排序好D 1 至D 3 的數及D 5 至D 7 內的數 那原來排序問題就解決了 演算法簡介 20 二分搜尋法 cont 方法令i 2 j 7從D i 開始向右找到第一個不小於D 1 的數 以i記錄其陣列的索引從D j 開始向左找到第一個不大於D 1 的數 以j記錄其陣列索引若i j 則交換D i 與D j 的內容 並繼續前述的左右搜尋 若i j 則交換D 1 與D j 的內容 並停止搜尋 演算法簡介 21 二分搜尋法 cont 確定4的位置將不大於4的資料放其左方將不小於4的資料放其右方 演算法簡介 22 快速排序法 QuickSort 原來的排序問題可細分為排序D 1 至D 3 的數及排序D 5 至D 7 的數的兩個子問題待解決子問題題後 可依序將答案組合起來 就是原來的答案 而分割後的子問題仍是排序問題可再利用前一段敘述的方法排序之 演算法簡介 23 快速排序法 程式 QSORT副程式以快速排序法對陣列D M 至D N 的元素排序 演算法簡介 24 快速排序法 cont 快速排序法最差時間複雜度為O n2 其中n為資料個數一般狀況時間複雜度為O nlog2n 個別擊破策略常用於計算幾何 ComputationalGeometry 的應用問題 演算法簡介 25 20 3貪婪策略 GreedyMethod 每次的決策都是朝向目前 最好 的方向前進櫃檯服務問題某一個銀行出納櫃檯要服務n位顧客 銀行的目標是希望顧客在櫃檯等待的平均時間要最少解決之道是每次都從尚未服務的顧客中 選擇需要服務時間最短的顧客來服務 如此就可達到預期目標 演算法簡介 26 貪婪策略 實例說明 假設有5個顧客A B C D E幾乎同時到達銀行櫃檯 其所需服務時間如表所示銀行櫃檯將依序服務B D E C A顧客在櫃檯等待的平均時間為 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 5 7 演算法簡介 27 背包問題 KnapsackProblem 假設有多個可分解的物件和一只限重W的背包每件物件有其重量及其被選取放入背包內的利益請問要如何將物件放進背包內而使得獲得的利益最大解決的方法 是每次在限重的情形下 選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內 演算法簡介 28 背包問題 實例說明 設背包限重100 有A B C D E共五個物件 其資料如表所示 演算法簡介 29 背包問題 實例說明 cont 解法依利益 重量由大至小順序放入物件 即C A B E D順序考慮 演算法簡介 30 最小擴展樹 MinimumSpanningTree 右圖由頂點 Vertex 及邊 Edge 構成每一邊都連接兩頂點 可指定其加權 Weight 分有向和無向兩種圓圈代表頂點連接兩頂點的線為邊每個邊都有非負的加權例如頂點V3與頂點V5間的邊之加權為5 演算法簡介 31 最小擴展樹 cont 無向圖 UndirectedGraph 均是無方向邊的圖形 無向圖的路徑 Path 由頂點構成的序列 其中序列裏每個頂點與其後一個頂點之間必有邊相連例如 V1 V5 V2 是一條從頂點V1到頂點V2的路徑 聯通圖 ConnectedGraph 任兩頂點都存在一條路徑的無向圖例如右圖是聯通圖 演算法簡介 32 最小擴展樹 cont 迴圈 Cycle 從某頂點出發回到該頂點的路徑例如 V1 V5 V2 V1 路徑就是迴圈無迴圈圖 AcyclicGraph 沒有迴圈的圖形樹 Tree 聯通的無迴圈圖圖形G V E V是頂點所成的集合 E是邊所成的集合 演算法簡介 33 最小擴展樹 cont 圖形G V E 的擴展樹T V E 是包括所有G的頂點的樹 其中E 是E的子集合 例如圖 a 及 b 都是右上圖的擴展樹 演算法簡介 34 最小擴展樹 cont 擴展樹T V E 的加權 集合E 中所有的邊的加權的總和例如圖 a 的擴展樹加權為1 3 5 7 16 而圖 b 的擴展樹加權為1 2 3 6 12 最小擴展樹問題 求出給定的聯通且加權的無向圖之最小擴展樹圖形G的最小擴展樹就是擁有最小加權的擴展樹如圖 b 的擴展樹是右上圖的最小擴展樹 演算法簡介 35 Kruskal演算法 Kruskal演算法 依據邊的加權由小到大的順序考慮該邊是否為最小擴展樹的邊步驟1 將圖形G V E 所有的邊依其加權由小到大排好 依序為e1 e2 e3 em 步驟2 建立圖形T V E 其中E 設i 1 步驟3 若ei加入圖形T中不產生迴圈 則將ei加入圖形T 即E E ei 否則 i i 1 步驟4 若圖形T不是圖形G的擴展樹 則重複步驟3 否則 圖形T是圖形G的最小擴展樹 結束演算法執行 演算法簡介 36 Kruskal演算法實例說明 演算法簡介 37 最短路徑問題 ShortestPathProblem 下圖是S A B T四個地點的交通路線 各路線分別標上距離令D a b 表示從a到b的最短路徑長度可知D S T D S A D A B D B T 10 15 20 45利用貪婪策略就能得到答案 演算法簡介 38 最短路徑問題 cont 若要找下圖的D S T 則D S T 24 20 44 此結果並不等於D S A D A B D B T 45以動態規劃策略找一般圖形的最短路徑 演算法簡介 39 20 4動態規劃 個別擊破策略是遞迴地將問題分成較小的問題後分別求得解答 然後合併這些部份答案成為完整的答案由上至下 Top Down 的計算策略Fibonacci函數f n f 0 0f 1 1f n f n 1 f n 2 n 2 演算法簡介 40 以個別擊破策略計算f 5 過程如下圖所示其中f 3 f 2 f 1 f 0 被重複計算許多次如果能先依序將f 0 f 1 f 2 f 3 f 4 的結果計算出來 就可避免重複計算 增進計算速度 演算法簡介 41 以個別擊破策略計算f 5 cont 以陣列FIB儲存Fibonacci函數 利用下面的方法計算f n FIB 0 0FIB 1 1FORI 2TOnFIB I FIB I 1 FIB I 2 NEXTI 演算法簡介 42 動態規劃 DynamicProgramming 策略 將問題分成小問題 然後直接解小問題 將結果儲存起來以備之後使用由下至上 Bottom Up 計算策略 演算法簡介 43 二項式係數 BinomialCoefficient B n k n k n k 當n k的值不小時 難計算n 及k 計算速度慢B n k B n 1 k 1 B n 1 k if0 k n1ifk 0ork n以動態規劃策略計算之 演算法簡介 44 二項式係數 cont 以動態規劃策略計算B n k 令陣列BI是一個二維陣列 有n 1個列 編號從0至n k 1個欄 編號從0到k 將B n k 的值儲存於BI n k 內FORI 0TOnFORJ 0TOmin i k IFJ 0ORJ ITHENBI I J 1ELSEBI I J BI I 1 J 1 BI I 1 J ENDIFNEXTJNEXTI 演算法簡介 45 有向圖的最短路徑問題 ShortestPathProblem 找出在有向及非負加權的圖形上任兩頂點的最短路徑 圓圈代表頂點連接兩頂點的線稱為邊每個邊都有方向也有對應的非負的加權有向圖的路徑是一個頂點序列 其中序列裏每個頂點到其後一個頂點的邊一定存在例如 V1 V3 V2 就是一條從頂點V1至頂點V2的路徑 路徑的長度為路徑上所有的邊的加權的和例如路徑 V1 V3 V2 的長度為6 4 10 演算法簡介 46 有向圖的最短路徑問題 cont 假設圖形有n個頂點 分別是V1 Vn 令dk i j 表示只有經過集合 V1 V2 Vk 中某頂點的Vi到Vj的最短路徑長度 令d0 i j 為Vi到Vj的邊的加權經過集合 V1 Vk 中某些頂點的Vi到Vj最短路徑可能不經過Vk 也可能經過Vk如果不經過Vk 則dk i j dk 1 i j 如果經過Vk 則dk i j dk 1 i k dk 1 k j dk i j min dk 1 i j dk 1 i k dk 1 k j 演算法簡介 47 有向圖的最短路徑問題 cont 演算法簡介 48 有向圖的最短路徑問題 cont 假設Vi到Vj的最短路徑經過Vk 則Vi到Vk的路徑也是最短的路徑 而Vk到Vj的路徑也是最短的 例如 由V2到V4的最短路徑為 V2 V1 V4 而路徑 V2 V1 也是V2到V1的最短路徑 而路徑 V1 V4 也是V1到V4的最短路徑最佳解包含其組成份子的最佳解之特性 稱為最佳化原則 PrincipleofOptimality 如果最佳化問題能應用此最佳化原則 則可以用動態規劃策略設計遞迴運算式來求得最佳解 演算法簡介 49 20 5刪除與搜尋策略 Prune and SearchMethod 包含多次的處理 每次的處理都會將輸入資料刪除固定的百分比 並運用同樣的方法遞迴地以刪除後的資料當作輸入資料重新解問題 經過若干次處理後 資料量將可縮小到能用固定常數的時間解得答案Example 二元搜尋法的每個步驟能去除一半的資料 是典型的刪除與搜尋演算法 演算法簡介 50 刪除與搜尋策略 cont 找出n個數的第k小的數直接的解法 將這n個數由小到大排好後 然後就能依序找出第k小的數O nlog2n 時間 刪除與搜尋策略 O n 時間 演算法簡介 51 刪除與搜尋策略 範例 假設n為5的倍數步驟1 將此n個數 分成n 5個數堆 每堆5個數 步驟2 分別將各數堆排序 步驟3 令P為數堆中間值的中間值 步驟4 令S1為小於P的數所成的集合 S2為等於P的數所成的集合 S3為大於P的數所成的集合 步驟5 若S1的元素個數大於或等於K 則丟棄S2及S3 並繼續利用本演算法找尋S1中的第K小的數 否則 如果S1與S2的元素個數和大於或等於K 則P為第K小數 否則 令K K S1 S2 丟棄S1及S2 並繼續利用本演算法找尋S3中的第K 小的數 演算法簡介 52 刪除與搜尋策略 範例 cont 假設n 25 經過步驟1分成25 5 5個數堆後的資料 演算法簡介 53 刪除與搜尋策略 範例 cont 各數堆排序後 此時各數堆的中間值分別為11 8 10 12 22 而11是這些數的中間值 演算法簡介 54 刪除與搜尋策略 範例 cont 將數堆位置調整後 左上角的矩形部份為S1和S2 而右下角的矩形部份為S2和S3 演算法簡介 55 刪除與搜尋策略 範例 cont 步驟5可能丟棄S2及S3 或丟棄S1及S2 被丟棄的資料至少為n 4個數每執行一次此演算法 資料將只剩下n n 4 3n 4個數 令T n 表示此演算法在n個數中找第k小的數所需的時間T n T 3n 4 O n 步驟1至步驟4需O n 時間得T n O n 刪除與搜尋策略能應用於如雙變數的線性規劃問題 單中心問題等計算幾何問題 演算法簡介 56 20