計(jì)算機(jī)算法設(shè)計(jì)與分析第2版4貪心算法-資料下載頁(yè)
2025-01-04 01:36本頁(yè)面
【正文】 法的理論基礎(chǔ) Set greedy (M,W) {A=?。 將 S中元素依權(quán)值 W（大者優(yōu)先）組成優(yōu)先隊(duì)列； while (S!=?) { (x)。 if (A∪{x} ?I) A=A∪{x}。 } return A } 50 貪心算法的理論基礎(chǔ) 算法 greedy的計(jì)算時(shí)間復(fù)雜性為 。 引理 (擬陣的貪心選擇性質(zhì) ) 設(shè) M=(S,I)是具有權(quán)函數(shù) W的帶權(quán)擬陣，且 S中元素依權(quán)值從大到小排列。又設(shè) x? S是 S中第一個(gè)使得 {x}是獨(dú)立子集的元素，則存在 S的最優(yōu)子集 A使得 x? A。 算法 greedy在以貪心選擇構(gòu)造最優(yōu)子集 A時(shí)，首次選入集合 A中的元素 x是單元素獨(dú)立集中具有最大權(quán)的元素。此時(shí)可能已經(jīng)舍棄了 S中部分元素?？梢宰C明這些被舍棄的元素不可能用于構(gòu)造最優(yōu)子集。 ))(log( nnfnnO ?51 貪心算法的理論基礎(chǔ) 引理 ： 設(shè) M=(S,I)是擬陣。若 S中元素 x不是空集 的可擴(kuò)展元素，則 x也不可能是 S中任一獨(dú)立子集 A的可擴(kuò)展元素。 引理 (擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì) ) 設(shè) x是求帶權(quán)擬陣 M＝ (S， I)的最優(yōu)子集的貪心算法greedy所選擇的 S中的第一個(gè)元素。那么，原問(wèn)題可簡(jiǎn)化為求帶權(quán)擬陣 M’=(S’,I’)的 最優(yōu)子集 問(wèn)題，其中： S’={y|y? S且 {x,y} ? I} I’={B|B? S{x}且 B∪{x} ? I} M’的權(quán)函數(shù)是 M的權(quán)函數(shù)在 S’上的限制 (稱 M’為 M關(guān)于元素 x的 收縮 )。 52 貪心算法的理論基礎(chǔ) 定理 (帶權(quán)擬陣貪心算法的正確性 ) 設(shè) M＝ (S,I)是具有權(quán)函數(shù) W的帶權(quán)擬陣，算法greedy返回 M的最優(yōu)子集。 任務(wù)時(shí)間表問(wèn)題 給定一個(gè) 單位時(shí)間任務(wù) 的有限集 S。關(guān)于 S的一個(gè)時(shí)間表 用于描述 S中單位時(shí)間任務(wù)的執(zhí)行次序。時(shí)間表中第 1個(gè)任務(wù)從時(shí)間 0開(kāi)始執(zhí)行直至?xí)r間 1結(jié)束，第 2個(gè)任務(wù)從時(shí)間 1開(kāi)始執(zhí)行至?xí)r間 2結(jié)束， … ，第 n個(gè)任務(wù)從時(shí)間 n1開(kāi)始執(zhí)行直至?xí)r間 n結(jié)束。 53 貪心算法的理論基礎(chǔ) 具有 截止時(shí)間 和 誤時(shí)懲罰 的單位時(shí)間任務(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ú)懲罰。 任務(wù)時(shí)間表問(wèn)題 要求確定 S的一個(gè)時(shí)間表（最優(yōu)時(shí)間表）使得總誤時(shí)懲罰達(dá)到最小。 id ididiwiwid54 貪心算法的理論基礎(chǔ) 這個(gè)問(wèn)題看上去很復(fù)雜，然而借助于 擬陣 ，可以用 帶權(quán)擬陣的貪心算法 有效求解。 對(duì)于一個(gè)給定的 S的時(shí)間表，在截止時(shí)間之前完成的任務(wù)稱為 及時(shí)任務(wù) ，在截止時(shí)間之后完成的任務(wù)稱為 誤時(shí)任務(wù) 。 S的任一時(shí)間表可以調(diào)整成 及時(shí)優(yōu)先形式 ，即其中所有及時(shí)任務(wù)先于誤時(shí)任務(wù)，而不影響原時(shí)間表中各任務(wù)的及時(shí)或誤時(shí)性質(zhì)。 類似地，還可將 S的任一時(shí)間表調(diào)整成為 規(guī)范形式 ，其中及時(shí)任務(wù)先于誤時(shí)任務(wù)，且及時(shí)任務(wù)依其截止時(shí)間的非減序排列。 55 貪心算法的理論基礎(chǔ) 首先可將時(shí)間表調(diào)整為及時(shí)優(yōu)先形式，然后再進(jìn)一步調(diào)整及時(shí)任務(wù)的次序。 任務(wù)時(shí)間表問(wèn)題 等價(jià)于 確定最優(yōu)時(shí)間表中 及時(shí)任務(wù)子集 A的問(wèn)題。一旦確定了及時(shí)任務(wù)子集 A，將 A中各任務(wù)依其截止時(shí)間的非減序列出，然后再以任意次序列出誤時(shí)任務(wù)，即 SA中各任務(wù)，由此產(chǎn)生 S的一個(gè)規(guī)范的最優(yōu)時(shí)間表。 對(duì)時(shí)間 t=1,2,… ,n， 設(shè) (A)是任務(wù)子集 A中所有截止時(shí)間是 t或更早的任務(wù)數(shù)。考察任務(wù)子集 A的獨(dú)立性。 tN56 貪心算法的理論基礎(chǔ) 引理 ： 對(duì)于 S的任一任務(wù)子集 A，下面的各命題是等價(jià)的。 (1) 任務(wù)子集 A是獨(dú)立子集。 (2) 對(duì)于 t=1,2,… ,n， (A)≤t 。 (3) 若 A中任務(wù)依其截止時(shí)間非減序排列，則 A中所有任務(wù)都是及時(shí)的。 任務(wù)時(shí)間表問(wèn)題 要求使總誤時(shí)懲罰達(dá)到最小，這等價(jià)于使任務(wù)時(shí)間表中的及時(shí)任務(wù)的懲罰值之和達(dá)到最大。下面的 定理 表明可用帶權(quán)擬陣的貪心算法解任務(wù)時(shí)間表問(wèn)題。 tN57 貪心算法的理論基礎(chǔ) 定理 ： 設(shè) S是帶有截止時(shí)間的單位時(shí)間任務(wù)集， I是 S的所有獨(dú)立任務(wù)子集構(gòu)成的集合。則有序?qū)?(S,I)是擬陣。 由 定理 ，用帶權(quán)擬陣的貪心算法可以求得最大權(quán) (懲罰 )獨(dú)立任務(wù)子集 A，以 A作為最優(yōu)時(shí)間表中的及時(shí)任務(wù)子集，容易構(gòu)造最優(yōu)時(shí)間表。 任務(wù)時(shí)間表問(wèn)題的貪心算法的 計(jì)算時(shí)間復(fù)雜性是 。其中 f(n)是用于檢測(cè)任務(wù)子集 A的獨(dú)立性所需的時(shí)間。用引理 (2)容易設(shè)計(jì)一個(gè) 時(shí)間算法來(lái)檢測(cè)任務(wù)子集的獨(dú)立性。因此，整個(gè)算法的計(jì)算時(shí)間 為 。具體算法 greedyJob可描述如 P130。 )( 2nO)(nO))(log( nnfnnO ?58 貪心算法的理論基礎(chǔ) 用抽象數(shù)據(jù)類型并查集 UnionFind可對(duì)上述算法作進(jìn)一步改進(jìn)。如果不計(jì)預(yù)處理的時(shí)間，改進(jìn)后的算法fasterJob所需的 計(jì)算時(shí)間 為 。 )log( * nnO59 課后作業(yè) 習(xí)題 41， 44， 424， 425， 426， 427， 428， 431， 432 60
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1