【正文】 :37:5301:37Feb2326Feb23 1越是無(wú)能的人，越喜歡挑剔別人的錯(cuò)兒。 :37:5301:37:53February 26, 2023 1他鄉(xiāng)生白發(fā)，舊國(guó)見(jiàn)青山。下面的 定理 表明可用帶權(quán)擬陣的貪心算法解任務(wù)時(shí)間表問(wèn)題。 (1) n個(gè)單位時(shí)間任務(wù)的集合 S={1,2,?,n} ； (2) 任務(wù) i的截止時(shí)間 ,1≤i≤n,1≤ ≤n ，即要求任務(wù) i在時(shí)間 之前結(jié)束； (3) 任務(wù) i的誤時(shí)懲罰 ,1≤i≤n, 即任務(wù) i未在時(shí)間 之前結(jié)束將招致的 懲罰；若按時(shí)完成則無(wú)懲罰。 ? if (A∪{x} ?I) A=A∪{x}。 當(dāng)擬陣 M中的獨(dú)立子集 A沒(méi)有可擴(kuò)展元素時(shí)，稱(chēng) A為 極大獨(dú)立子集 。 按此策略，當(dāng) 時(shí)，只要將機(jī)器 i的 [0, ti]時(shí)間區(qū)間分配給作業(yè) i即可，算法只需要 O(1)時(shí)間。將所有的邊按權(quán)從小到大排序。 32 例 7 最小生成樹(shù) 最小生成樹(shù)性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。一個(gè)頂點(diǎn)屬于集合 S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 前綴碼 對(duì)每一個(gè)字符規(guī)定一個(gè) 0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。 Sort(w, t, n)。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。 設(shè)有 n個(gè)活動(dòng)的集合 E={1,2,?,n} ，其中每個(gè)活動(dòng)都要求使用同一資源 (如演講會(huì)場(chǎng) )，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。 ? for (i=1。 7 最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 。i10。4 貪心算法與最優(yōu)策略 1 ? 學(xué)習(xí)要點(diǎn) ? 貪心算法的概念。i++)n[i]=0。 換句話(huà)說(shuō)，問(wèn)題的整體最優(yōu)性依賴(lài)于其局部子問(wèn)題解的最優(yōu)性。i=n。 每個(gè)活動(dòng) i都有一個(gè)要求使用該資源的起始時(shí)間 si和一個(gè)結(jié)束時(shí)間 fi,且 si fi 。也就是說(shuō)，該算法的貪心選擇的意義是 使剩余的可安排時(shí)間段極大化 ，以便安排盡可能多的相容活動(dòng)。 for (int i = 1。這種編碼稱(chēng)為 前綴碼 。 初始時(shí)， S中僅含有源。本節(jié)介紹的構(gòu)造最小生成樹(shù)的 Prim算法和 Kruskal算法 都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接 2個(gè)不同的連通分支：當(dāng)查看到第 k條邊 (v,w)時(shí)，如果端點(diǎn) v和w分別是當(dāng)前 2個(gè)不同的連通分支 T1和 T2中的頂點(diǎn)時(shí)，就用邊 (v,w)將 T1和 T2連接成一個(gè)連通分支，然后繼續(xù)查看第 k+1條邊；如果端點(diǎn) v和 w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第 k+1條邊。 當(dāng) 時(shí)，首先將 n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。 ),( GGG ISM ?45 貪心算法的理論基礎(chǔ) 下面的關(guān)于 極大獨(dú)立子集 的性質(zhì)是很有用的。 ? } ? return A ? } 48 貪心算法的理論基礎(chǔ) 算法 greedy的計(jì)算時(shí)間復(fù)雜性為 。 任務(wù)時(shí)間表問(wèn)題 要求確定 S的一個(gè)時(shí)間表（最優(yōu)時(shí)間表）使得總誤時(shí)懲罰達(dá)到最小。 tN55 貪心算法的理論基礎(chǔ) 定理 ： 設(shè) S是帶有截止時(shí)間的單位時(shí)間任務(wù)集， I是 S的所有獨(dú)立任務(wù)子集構(gòu)成的集合。 2023年 2月 26日星期日 上午 1時(shí) 37分 53秒 01:37: 1比不了得就不比，得不到的就不要。 01:37:5301:37:5301:37Sunday, February 26, 2023 1知人者智，自知者明。 01:37:5301:37:5301:372/26/2023 1:37:53 AM 1越是沒(méi)有本領(lǐng)的就越加自命不凡。 01:37:5301:37:5301:37Sunday, February 26, 2023 1乍見(jiàn)翻疑夢(mèng)，相悲各問(wèn)年。 任務(wù)時(shí)間表問(wèn)題 要求使總誤時(shí)懲罰達(dá)到最小，這等價(jià)于使任務(wù)時(shí)間表中的及時(shí)任務(wù)的懲罰值之和達(dá)到最大。 51 貪心算法的理論基礎(chǔ) 具有 截止時(shí)間 和 誤時(shí)懲罰 的單位時(shí)間任務(wù)時(shí)間表問(wèn)題可描述如下。 ? 將 S中元素依權(quán)值 W（大者優(yōu)先）組成優(yōu)先隊(duì)列； ? while (S!=?) { ? (x)。 給定擬陣 M=(S,I)，對(duì)于 I中的獨(dú)立子集 A? I，若 S有一元素 x? A，使得將 x加入 A后仍保持獨(dú)立性，即 A∪{x} ? I,則稱(chēng) x為 A的 可擴(kuò)展元素 。 41 例 7 多機(jī)調(diào)度問(wèn)題 采用 最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先 的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。 用這個(gè)辦法實(shí)現(xiàn)的 Prim算法所需的 計(jì)算時(shí)間 為 )( 2nO37 例 7 最小生成樹(shù) Kruskal算法 Kruskal算法構(gòu)造 G的最小生成樹(shù)的 基本思想 是，首先將 G的 n個(gè)頂點(diǎn)看成 n個(gè)孤立的連通分支。 例如 ，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊 (v,w)的權(quán)c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 27 例 6 單源最短路徑 其 基本思想 是，設(shè)置頂點(diǎn)集合 S并不斷地作 貪心選擇來(lái)擴(kuò)充這個(gè)集合。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。 20 templateclass Type void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]。 ? } ? } 各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和 f中且按結(jié)束時(shí)間的非減序排列 17 例 3 活動(dòng)安排問(wèn)題 由于輸入的活動(dòng)以其完成時(shí)間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時(shí)間 的相容活動(dòng)加入集合 A中。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。i++) x[i]=0。 對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。