考研復習資料大匯總(編輯修改稿)
2024-11-19 22:24 本頁面
【文章內(nèi)容簡介】 c[i][j]=c[i1][j]。 b[i][j]=2。} else { c[i][j]=c[i][j1]。 b[i][j]=3。 } }}構(gòu)造最長公共子序列void LCS(int i， int j， char *x， int **b){ if (i = =0 || j= =0) return。 if (b[i][j]== 1){ LCS(i1， j1， x， b)。 coutx[i]。 } else if (b[i][j]== 2) LCS(i1， j， x， b)。 else LCS(i， j1， x， b)。}貪心法 —— 活動安排問題 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。貪心法 —— 活動安排問題 設有 n 個活動的集合 E={1,2,…,n }，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動 i 都有一個要求使用該資源的 起始時間 si 和一個 結(jié)束時間 fi ,且 si fi 。如果選擇了活動 i，則它在半開時間區(qū)間[si, fi)內(nèi)占用資源。 若區(qū)間 [si, fi)與區(qū)間 [sj, fj)不相交，則稱 活動 i 與活動 j 是相容 的。也就是說，當 si≥fj 或 sj≥fi 時，活動 i 與活動 j 相容。在下面所給出的解活動安排問題的貪心算法 :int greedySelector(int s[], int f[], boolean a[]) { int n=。 a[1]=true。 int j=1。 int count=1。 for (int i=2。 i=n。 i++) { if (s[i]=f[j]) { a[i]=true。 j=i。 count++。 } else a[i]=false。 } return count。 }各活動的起始時間和結(jié)束時間存儲于數(shù)組 s和 f 中且 按結(jié)束時間的非減序排列 貪心法 —— 活動安排問題 由于輸入的活動以其完成時間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時間 的相容活動加入集合 A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的 意義是意義是 使剩余的可安排時使剩余的可安排時間段極大化間段極大化 ，以便安排盡可能多的相容活動，以便安排盡可能多的相容活動 。算法 greedySelector的效率極高。當輸入的活動已按結(jié)束時間的非減序排列，算法只需 O(n)的時間安排 n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用 O(nlogn)的時間重排。 貪心法 —— 活動安排問題 例： 設待安排的 11個活動的開始時間和結(jié)束時間 按結(jié)束時間的非減序排列 如下：i 1 2 3 4 5 6 7 8 9 10 11S[i]1 3 0 5 3 5 6 8 8 2 12f[i] 4 5 6 7 8 9 10 11 12 13 14貪心法 —— 活動安排問題 活動安排問題 算法 greedySelector 的計算過程 如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。i 1 2 3 4 5 6 7 8 9 10 11S[i]1 3 0 5 3 5 6 8 8 2 12f[i] 4 5 6 7 8 9 10 11 12 13 14貪心法 —— 多機調(diào)度問題多機調(diào)度問題 要求給出一種作業(yè)調(diào)度方案，使所給的 n個作業(yè)在盡可能短的時間內(nèi)由 m 臺機器加工處理完成。設有 n 個獨立的作業(yè) {1,2,…, n}，由 m 臺相同的機器進行加工處理。作業(yè) i 所需的處理時間為 ti。這個問題是 NP 完全問題 ，到目前為止還沒有有效的解法。對于這一類問題 ,用 貪心選擇策略 有時可以設計出較好的近似算法。 約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。貪心法 —— 多機調(diào)度問題采用 最長處理時間作業(yè)優(yōu)先 的貪心選擇策略可以設計出解多機調(diào)度問題的較好的近似算法。按此策略，當 時，只要將機器 i 的 [0, ti]時間區(qū)間分配給作業(yè) i 即可。當
公司管理相關(guān)推薦
鄂ICP備17016276號-1