[計算機]演算法簡介(編輯修改稿)
2024-11-15 03:53 本頁面
【文章內容簡介】 9 EN D I F20 LO O P21 K = D ( M )22 D ( M ) = D ( J)23 D ( J ) = K24 Q SO R T(M, J 1)25 Q SO R T( J + 1,N )26 EN D I F27 EN D SU B演算法簡介 24 快速排序法 (cont.) 快速排序法 ? 最差時間複雜度為 O(n2) ，其中 n為資料個數 ? 一般狀況時間複雜度為 O(nlog2n) 個別擊破策略常用於計算幾何 (Computational Geometry) 的應用問題 演算法簡介 25 貪婪策略 (Greedy Method) ? 每次的決策都是朝向目前“最好”的方向前進 ? 櫃檯服務問題 ? 某一個銀行出納櫃檯要服務 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 顧客 服務時間A 5B 1C 4D 2E 3演算法簡介 27 背包問題 (Knapsack Problem) ? 假設有多個可分解的物件和一只限重 W的背包 ? 每件物件有其重量及其被選取放入背包內的利益 ? 請問要如何將物件放進背包內而使得獲得的利益最大 ? 解決的方法： ? 是每次在限重的情形下，選取尚未放入的物件中擁有最大的利益與重量的比值之物件放入背包內。 演算法簡介 28 背包問題 實例說明 ? 設背包限重 100，有 A， B， C， D， E共五個物件，其資料如表所示 物件 重量 利益 利益 /重量A 10 20 2 .0B 20 30 1 .5C 30 66 2 .2D 40 40 1 .0E 50 60 1 .2演算法簡介 29 背包問題 實例說明 (cont.) 解法 ? 依 利益 /重量由大至小順序放入物件，即 C, A, B, E, D順序考慮 物件 個數 累計利益 累計重量C 1 66 30A 1 86 40B 1 1 1 6 60E 0 .8 164 100演算法簡介 30 最小擴展樹 (Minimum Spanning Tree) 右圖 ? 由頂點 (Vertex) 及邊 (Edge) 構成 ? 每一邊都連接兩頂點，可指定其加權 (Weight) ，分有向和無向兩種 ? 圓圈代表頂點 ? 連接兩頂點的線為邊 ? 每個邊都有非負的加權 ? 例如頂點 V3與頂點 V5間的邊之加權為 5 31456872V2V3V1V4V5演算法簡介 31 最小擴展樹 (cont.) ? 無向圖 (Undirected Graph)：均是無方向邊的圖形。 ? 無向圖的路徑 (Path)：由頂點構成的序列，其中序列裏每個頂點與其後一個頂點之間必有邊相連 ? 例如 [V1, V5, V2]是一條從頂點V1到頂點 V2的路徑。 ? 聯通圖 (Connected Graph)：任兩頂點都存在一條路徑的無向圖 ? 例如右圖是聯通圖 31456872V2V3V1V4V5演算法簡介 32 最小擴展樹 (cont.) ? 迴圈 (Cycle)：從某頂點出發(fā)回到該頂點的路徑 ? 例如 [V1, V5, V2, V1]路徑就是迴圈 ? 無迴圈圖 (Acyclic Graph)：沒有迴圈的圖形 ? 樹 (Tree)：聯通的無迴圈圖 ? 圖形 G=(V, E)， V是頂點所成的集合， E是邊所成的集合 31456872V2V3V1V4V5演算法簡介 33 最小擴展樹 (cont.) ? 圖形 G=(V, E)的擴展樹 T=(V, E’)是包括所有 G的頂點的樹，其中 E’是 E的子集合。 ? 例如圖 (a)及 (b)都是右上圖的擴展樹 31456872V 2 V 3V 1 V 4V 53157V2V3V1V4V5 3162V2V3V1V4V5( a ) ( b )演算法簡介 34 最小擴展樹 (cont.) ? 擴展樹 T=(V, E’)的加權：集合 E’中所有的邊的加權的總和 ? 例如圖 (a)的擴展樹加權為 1+3+5+7=16，而圖 (b) 的擴展樹加權為 1+2+3+6=12。 ? 最小擴展樹問題：求出給定的聯通且加權的無向圖之最小擴展樹 ? 圖形 G的最小擴展樹就是 擁有最小加權的擴展樹 ? 如圖 (b)的擴展樹是 右上圖的最小擴展樹 3157V2V3V1V4V5 3162V2V3V1V4V5( a ) ( b )31456872V 2 V 3V 1 V 4V 5演算法簡介 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的最小擴展樹 ， 結束演算法執(zhí)行 。 演算法簡介 36 Kruskal演算法實例說明 31456872V 2
教學課件相關推薦
鄂ICP備17016276號-1