[計算機(jī)]演算法簡介-資料下載頁
2025-10-10 03:53本頁面
【正文】 ? 例如 ﹐ 由 V2到 V4的最短路徑為 [V2, V1, V4]﹐ 而路徑 [V2, V1]也是 V2到 V1的最短路徑 ﹐ 而路徑 [V1, V4]也是 V1到 V4的最短路徑 ? 最佳解包含其組成份子的最佳解之特性 ﹐ 稱為 最佳化原則 (Principle of Optimality) ? 如果最佳化問題能應(yīng)用此最佳化原則 ﹐ 則可以用動態(tài)規(guī)劃策略設(shè)計遞迴運(yùn)算式來求得最佳解 演算法簡介 49 刪除與搜尋策略 (PruneandSearch Method) ? 包含多次的處理 ， 每次的處理都會將輸入資料刪除固定的百分比 ， 並運(yùn)用同樣的方法遞迴地以刪除後的資料當(dāng)作輸入資料重新解問題 ， 經(jīng)過若干次處理後 ， 資料量將可縮小到能用固定常數(shù)的時間解得答案 ? Example：二元搜尋法的每個步驟能去除一半的資料 ， 是典型的刪除與搜尋演算法 演算法簡介 50 刪除與搜尋策略 (cont.) 找出 n 個數(shù)的第 k 小的數(shù) ? 直接的解法：將這 n 個數(shù)由小到大排好後，然後就能依序找出第 k 小的數(shù) ? O(nlog2n)時間。 ? 刪除與搜尋策略： O(n)時間 演算法簡介 51 刪除與搜尋策略 範(fàn)例 假設(shè) n 為 5 的倍數(shù) ? 步驟 1 ： 將此 n 個數(shù)，分成 n/5 個數(shù)堆 ,每堆 5 個數(shù)。 ? 步驟 2 ：分別將各數(shù)堆排序。 ? 步驟 3 ：令 P 為數(shù)堆中間值的中間值。 ? 步驟 4 ：令 S1 為小於 P 的數(shù)所成的集合， S2為等於 P 的數(shù)所成的集合， S3為大於 P 的數(shù)所成的集合。 ? 步驟 5 ：若 S1 的元素個數(shù)大於或等於 K，則丟棄 S2及 S3，並繼續(xù)利用本演算法找尋 S1 中的第 K 小的數(shù)。否則，如果 S1 與 S2 的元素個數(shù)和大於或等於 K ，則 P 為第 K 小數(shù) 。否則，令 K’ = K |S1| |S2| ，丟棄 S1及 S2，並繼續(xù)利用本演算法找尋 S3 中的第 K’小的數(shù) 演算法簡介 52 刪除與搜尋策略 範(fàn)例 (cont.) ? 假設(shè) n =25，經(jīng)過步驟 1 分成 25/5 =5 個數(shù)堆後的資料 3 21 20 11 2 5 13 4 8 15 1 14 19 6 10 7 16 9 23 12 17 22 18 24 25 圖 演算法簡介 53 刪除與搜尋策略 範(fàn)例 (cont.) ? 各數(shù)堆排序後，此時各數(shù)堆的中間值分別為 11 , 8 , 10 , 12 , 22 ， 而 11 是這些數(shù)的中間值。 2 3 11 20 21 4 5 8 13 15 1 6 10 14 19 7 9 12 16 23 17 18 22 24 25 圖 演算法簡介 54 刪除與搜尋策略 範(fàn)例 (cont.) ? 將數(shù)堆位置調(diào)整後，左上角的矩形部份為 S1 和 S2，而右下角的矩形部份為 S2 和 S3 2 3 11 20 21 4 5 8 13 15 1 6 10 14 19 7 9 12 16 23 17 18 22 24 25 圖 S2?S3最少 n/4個數(shù) S1?S2最少 n/4個數(shù) 演算法簡介 55 刪除與搜尋策略 範(fàn)例 (cont.) ? 步驟 5可能丟棄 S2及 S3，或丟棄 S1及 S2， ? 被丟棄的資料至少為 n/4個數(shù) ? 每執(zhí)行一次此演算法，資料將只剩下 n(n/4) = 3n/4個數(shù)。 ? 令 T(n)表示此演算法在 n個數(shù)中找第 k小的數(shù)所需的時間 ? T(n) = T(3n/4) + O(n) ? 步驟 1至步驟 4需 O(n)時間 ? 得 T(n) = O(n) ? 刪除與搜尋策略能應(yīng)用於如雙變數(shù)的線性規(guī)劃問題、單中心問題等計算幾何問題。 演算法簡介 56 課後練習(xí) 1. 以快速排序法完成下列１ 0個數(shù)的排序： 10, 21， 5， 31， 42， 24， 90， 50， 15， 2。 2. 假設(shè)有面額１５元、１０元、５元及１元郵票。若某郵件需４９元的郵資，為了讓郵票張數(shù)最少，請問這些面額的郵票各需幾張？ (提示：貪婪策略 ) 3. 分別以 O、 Ω 、 θ 階次表示下列各函數(shù)： a) + n b) n + log2n c) 2n + nlog2n 演算法簡介 57 課後練習(xí) (cont.) 4. 請以動態(tài)規(guī)劃演算法找出下圖任兩頂點的最短路徑： V24V352V171V4621演算法簡介 58 課後練習(xí) (cont.) 5. 請以刪除與搜尋演算法找出下列 25個數(shù)的第10小的數(shù)： 25， 50， 1， 10， 31， 55， 97， 87， 101， 32 40， 21， 75， 41， 60， 34， 63， 15， 86， 11 47， 33， 74， 81， 44。 演算法簡介 59 6. 設(shè)背包限重３０，有 A， B， C三件可分解的物件，其資料如下表： 請問應(yīng)如何將物件放入背包以獲得最大利益？ 7. 若將習(xí)題 4的圖形視為無向圖，請問此無向圖的最小擴(kuò)展樹為何？ 課後練習(xí) (cont.) 物件 重量 利益A 5 50B 10 60C 20 140演算法簡介 60 欲罷不能 ? Brassard and Bratley, Fundamentals of Algorithmics, PrenticeHall, 1996. ? Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press, 2021. ? Horowitz, Computer Algorithms in C++, 1998. ? Lee, Tseng, Chang and Tsai, Introduction to Design and Analysis of Algorithms (2nd Ed.), Flag Publishing (旗標(biāo) ), 2021。 ? Neapditan and Naimipour, Foundations of Algorithms, . Heath and Company, 1996
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1