計(jì)算機(jī)算法設(shè)計(jì)與分析第2版4貪心算法-展示頁
2025-01-13 01:36本頁面
【正文】 法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是 2類算法的一個(gè)共同點(diǎn)。 13 貪心算法的基本要素 當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 動(dòng)態(tài)規(guī)劃算法通常以 自底向上 的方式解各子問題，而貪心算法則通常以 自頂向下 的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 12 貪心算法的基本要素 貪心選擇性質(zhì) 所謂 貪心選擇性質(zhì) 是指所求問題的 整體最優(yōu)解 可以通過一系列 局部最優(yōu) 的選擇，即貪心選擇來達(dá)到。 對于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢 ?這個(gè)問題很難給予肯定的回答。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。 貪心算法并不總能求得問題的 整體最優(yōu)解 。陰影長條表示的活動(dòng)是已選入集合 A的活動(dòng)，而空白長條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。 8 活動(dòng)安排問題 例： 設(shè)待安排的 11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下： i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14 9 活動(dòng)安排問題 算法 greedySelector 的計(jì)算過程 如左圖所示。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需 O(n)的時(shí)間安排 n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。也就是說，該算法的貪心選擇的意義是 使剩余的可安排時(shí)間段極大化 ，以便安排盡可能多的相容活動(dòng)。 } } 下面給出解活動(dòng)安排問題的貪心算法 GreedySelector : 各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲于數(shù)組 s和 f中且按結(jié)束時(shí)間的非減序排列 7 活動(dòng)安排問題 由于輸入的活動(dòng)以其完成時(shí)間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時(shí)間 的相容活動(dòng)加入集合 A中。 j=i。i=n。 int j=1。也就是說，當(dāng) si≥fj 或 sj≥fi 時(shí)，活動(dòng) i與活動(dòng) j相容。如果選擇了活動(dòng) i，則它在半開時(shí)間區(qū)間 [si, fi)內(nèi)占用資源。 5 活動(dòng)安排問題 設(shè)有 n個(gè)活動(dòng)的集合 E={1,2,… ,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。該問題要求高效地安排一系列爭用某一公共資源的活動(dòng)。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的 局部最優(yōu) 選擇。 ? （ 1）活動(dòng)安排問題； ? （ 2）最優(yōu)裝載問題； ? （ 3）哈夫曼編碼； ? （ 4）單源最短路徑； ? （ 5）最小生成樹； ? （ 6）多機(jī)調(diào)度問題。1 第 4章 貪心算法 2 ? 學(xué)習(xí)要點(diǎn) ? 理解貪心算法的概念。 ? 掌握貪心算法的基本要素 ? （ 1）最優(yōu)子結(jié)構(gòu)性質(zhì) ? （ 2）貪心選擇性質(zhì) ? 理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 ? 理解貪心算法的一般理論 ? 通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略。 3 顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。如單源最短路經(jīng)問題，最小生成樹問題等。 4 活動(dòng)安排問題 活動(dòng)安排問題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。貪心算法提供了一個(gè)簡單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。每個(gè)活動(dòng) i都有一個(gè)要求使用該資源的起始時(shí)間 si和一個(gè)結(jié)束時(shí)間 fi,且 si fi 。若區(qū)間 [si, fi)與區(qū)間 [sj, fj)不相交，則稱活動(dòng) i與活動(dòng) j是相容的。 6 活動(dòng)安排問題 templateclass Type void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true。 for (int i=2。i++) { if (s[i]=f[j]) { A[i]=true。 } else A[i]=false。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。 算法 greedySelector的效率極高。如果所給出的活動(dòng)未按非減序排列，可以用 O(nlogn)的時(shí)間重排。圖中每行相應(yīng)于算法的一次迭代。 10 活動(dòng)安排問題 若被檢查的活動(dòng) i的開始時(shí)間 Si小于最近選擇的活動(dòng) j的結(jié)束時(shí)間 fi，則不選擇活動(dòng) i，否則選擇活動(dòng) i加入集合A中。但對于活動(dòng)安排問題，貪心算法 greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合 A的規(guī)模最大。 11 貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有 2個(gè)重要的性質(zhì)： 貪心選擇性質(zhì) 和 最優(yōu)子結(jié)構(gòu)性質(zhì) 。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。但是，對于具
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1