算法設(shè)計(jì)技巧與分析 貪心法(第8章)

2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院0Algorithms:

DesignTechniquesandAnalysis

算法設(shè)計(jì)技巧與分析2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院1第八章貪心法貪心法的基本思想8.1

引言應(yīng)用8.2

單源最短路問(wèn)題8.3

最小生成樹(shù)（Kruskal算法）8.4

最小生成樹(shù)（Prim算法）8.5

文件壓縮2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院28.1

引言貪心法的適用問(wèn)題貪心法又叫優(yōu)先策略，顧名思義就是“擇優(yōu)錄取”，它是一種非常簡(jiǎn)單好用的求解最優(yōu)化問(wèn)題的方法，在許多方面的應(yīng)用非常成功。貪心法的基本思想貪心算法是根據(jù)一種貪心準(zhǔn)則(greedycriterion)來(lái)逐步構(gòu)造問(wèn)題的解的方法。在每一個(gè)階段，都作出了相對(duì)該準(zhǔn)則最優(yōu)的決策。決策一旦作出，就不可更改。由貪心法得到的問(wèn)題的解可能是最優(yōu)解，也可能只是近似解。能否產(chǎn)生問(wèn)題的最優(yōu)解需要加以證明。所選的貪心準(zhǔn)則不同，則得到的貪心算法不同，貪心解的質(zhì)量當(dāng)然也不同。因此，貪心算法的好壞關(guān)鍵在于正確的選擇貪心準(zhǔn)則。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院3背包問(wèn)題問(wèn)題

給定一個(gè)承重量為M的背包，n個(gè)重量分別為w1,w2,…,wn的物品。已知物品i放入背包能產(chǎn)生pi的價(jià)值（放入單位重量的物品i，產(chǎn)生的價(jià)值為pi/wi），i=1,2,…,n。如何裝包才能獲得最大價(jià)值？

實(shí)際上，就是要求找到一組非負(fù)且不超過(guò)1的實(shí)數(shù)x1,x2,…,xn滿足∑i=1nxiwi≤M，且使得∑i=1n

xipi達(dá)到最大值。

2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院4背包問(wèn)題實(shí)例

n=3,M=20,(w1,w2,w3)=(18,15,10),(p1,p2,p3)=(25,24,15).求解思想貪心準(zhǔn)則1——根據(jù)物品的價(jià)值由大到小來(lái)放。（由實(shí)例可知，它不是最優(yōu)貪心準(zhǔn)則）貪心準(zhǔn)則2——根據(jù)物品的重量由小到大來(lái)放。（由實(shí)例可知，它不是最優(yōu)貪心準(zhǔn)則）貪心準(zhǔn)則3——根據(jù)價(jià)值/重量（即單位價(jià)值）由大到小來(lái)放。（可以證明它是最優(yōu)貪心準(zhǔn)則）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院58.2單源最短路問(wèn)題問(wèn)題

設(shè)G=<V,E>是一個(gè)有向圖，圖中每一條邊都有一個(gè)非負(fù)長(zhǎng)度。單源最短路徑問(wèn)題就是要求出從圖中一個(gè)指定的點(diǎn)s（稱為源點(diǎn)）到其它每個(gè)點(diǎn)的長(zhǎng)度最短的路徑。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院68.2單源最短路問(wèn)題貪心準(zhǔn)則Dijkstra算法的基本思想(1)X←{1};Y←V-{1}(2)對(duì)于每個(gè)點(diǎn)v∈Y

，若有一條從1到v的邊，則令

[v]=該邊的邊長(zhǎng)，否則令

[v]=∞。令

[1]=0(3)while

Y≠{}(4)令y∈Y

為

[]中最小的y(5)將y

從Y移到X中(6)更新Y中與y相連的點(diǎn)

[]值(7)endwhile.2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院78.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院88.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院98.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院108.2單源最短路問(wèn)題Dijkstra算法算法8.1DIJKSTRA2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院118.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院128.2單源最短路問(wèn)題正確性：

引理8.1

在Dijkstra算法中,當(dāng)步驟8中選擇一個(gè)結(jié)點(diǎn)y時(shí),如果

[y]<∞，則

[y]=

[y]，其中

[y]表示從源點(diǎn)到y(tǒng)的距離。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院138.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院148.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院158.2單源最短路問(wèn)題改進(jìn):一個(gè)在稠密圖上是線性時(shí)間的算法基本思想：使用最小堆數(shù)據(jù)結(jié)構(gòu)來(lái)保存集合Y中的結(jié)點(diǎn)，使得距X中結(jié)點(diǎn)最近的Y中的結(jié)點(diǎn)

y能夠在時(shí)間O(logn)內(nèi)得到。與每個(gè)結(jié)點(diǎn)v相關(guān)的關(guān)鍵字是

[v]。算法8.2

SHORTESTPATH

2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院168.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院178.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院188.2單源最短路問(wèn)題復(fù)習(xí)2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院198.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院208.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院218.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院228.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院238.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院248.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院258.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院268.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院278.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院288.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院298.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院308.2單源最短路問(wèn)題2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院31最小生成樹(shù)問(wèn)題

設(shè)G=<V,E>是一個(gè)每條邊都有權(quán)的無(wú)向連通圖。G的一棵生成樹(shù)<V,T>是G的一個(gè)生成子圖且該子圖是一棵樹(shù)，簡(jiǎn)記作T。G的權(quán)最小的生成樹(shù)

T被稱作是最小生成樹(shù)。給定無(wú)向帶權(quán)圖G=<V,E>，要求求G的一棵最小生成樹(shù)。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院32

實(shí)例——最小代價(jià)通訊網(wǎng)絡(luò)

考慮n個(gè)城市的通訊網(wǎng)絡(luò)建設(shè)問(wèn)題。要求所有城市能互相通訊，且總的建設(shè)成本最小。城市與城市間所有可能的通訊連接可被視作一個(gè)無(wú)向圖G=<V,E>，圖的每條邊都賦予一個(gè)權(quán)值，權(quán)值表示建成由這條邊所表示的通訊連接所要付出的代價(jià)。包含圖中所有頂點(diǎn)（城市）的無(wú)回路連通子圖是一個(gè)可行解，它是圖的一棵生成樹(shù)，其代價(jià)為該子圖中邊的權(quán)之和。設(shè)所有的權(quán)值都非負(fù)，要求找出代價(jià)最小的生成樹(shù)。最小生成樹(shù)2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院33求解思想Prim算法

該算法要求選擇n-1條邊。其貪心準(zhǔn)則：從剩下的邊中，選擇一條權(quán)值最小的邊，并且它的加入應(yīng)使得和已經(jīng)選定的邊集仍然構(gòu)成一棵樹(shù)。Kruskal算法（避圈法）

該算法要求選擇n-1條邊。其貪心準(zhǔn)則：從剩下的邊中選擇一條和已經(jīng)選定的邊集不構(gòu)成圈（即回路）的有最小權(quán)值的邊。破圈法

該算法是通過(guò)刪除原圖中的若干條邊來(lái)得到最小生成樹(shù)。其貪心準(zhǔn)則：在剩下的圖中任意選擇一條回路，去掉其一條最大權(quán)值的邊來(lái)打破該回路。最小生成樹(shù)2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院348.3最小生成樹(shù)（Kruskal算法）貪心準(zhǔn)則Kruskal算法的基本思想（1）對(duì)G中的邊按照其權(quán)值的非減次序排序；置T={}。

（2）依次來(lái)考慮圖中的每一條邊是否加入生成樹(shù)T中。若當(dāng)前被考慮的邊與T中已經(jīng)有的邊不構(gòu)成回路，將該邊加入T中；否則該邊不加入T中。然后再考慮下一條邊。直到所有的邊都考慮完為止。實(shí)例——圖8.42024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院358.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院368.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院378.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院388.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院398.3最小生成樹(shù)（Kruskal算法）Kruskal算法2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院408.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院418.3最小生成樹(shù)（Kruskal算法）復(fù)習(xí)2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院428.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院438.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院448.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院458.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院468.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院478.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院488.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院498.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院508.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院518.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院528.3最小生成樹(shù)（Kruskal算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院538.3最小生成樹(shù)（Kruskal算法）Kruskal算法時(shí)間復(fù)雜度:O(mlogm)正確性:

引理8.2

算法Kruskal在無(wú)向帶權(quán)連通圖中找到一棵最小生成樹(shù)。

證明思路:

對(duì)

T的大小進(jìn)行歸納證明，其中T是一棵最小生成樹(shù)的邊集的一個(gè)子集。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院548.4最小生成樹(shù)（PRIM算法）貪心準(zhǔn)則Prim算法的基本思想(1)T←{};X←{1};Y←V-{1}(2)while

Y≠{}(3)設(shè)(x,y)是一條滿足x∈X且y∈Y的權(quán)值最小的邊(4)X←X∪{y}(5)Y←Y-{y}(6)T←T∪{(x,y)}(7)endwhile2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院558.4最小生成樹(shù)（PRIM算法）實(shí)例——圖8.52024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院568.4最小生成樹(shù)（PRIM算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院578.4最小生成樹(shù)（PRIM算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院588.4最小生成樹(shù)（PRIM算法）Prim算法2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院598.4最小生成樹(shù)（PRIM算法）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院608.4最小生成樹(shù)（PRIM算法）Prim算法算法8.4PRIM時(shí)間復(fù)雜度:(n2)正確性:

引理8.3

算法PRIM在無(wú)向帶權(quán)連通圖中找到一棵最小生成樹(shù)。證明思路：通過(guò)對(duì)T的大小進(jìn)行歸納證明，其中T滿足(X,T)是一棵最小生成樹(shù)的子樹(shù)。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院618.4最小生成樹(shù)（PRIM算法）改進(jìn):一個(gè)在稠密圖上是線性時(shí)間的算法基本思想：使用最小堆

來(lái)保存點(diǎn)集Y，使得兩點(diǎn)分別在點(diǎn)集Y和V-Y的一條最小成本的邊能夠在時(shí)間O(logn)內(nèi)得到。算法8.5MST時(shí)間復(fù)雜度:

定理8.52024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院628.5

文件壓縮（Huffman算法）

問(wèn)題

設(shè)

F

是一個(gè)字符流文件，其中的字符取自字母表C={c1,c2,…,cn}。設(shè)f(ci)表示字符ci

出現(xiàn)在文件中的頻率，1≤i≤n。希望用某種方式將文件壓縮得盡可能小，且易于根據(jù)壓縮文件恢復(fù)得到原文件。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院638.5

文件壓縮（Huffman算法）直接算法

使用定長(zhǎng)碼給每個(gè)字符編碼。哈夫曼編碼（Huffman算法）

使用變長(zhǎng)碼給字符編碼，使得出現(xiàn)頻率高的字符的編碼盡可能短。2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院648.5

文件壓縮（Huffman算法）實(shí)例

假設(shè)有一個(gè)數(shù)據(jù)文件包含100000個(gè)字符，我們要用壓縮的方式來(lái)存儲(chǔ)它。該文件中各個(gè)字符出現(xiàn)的頻率如下表所示。要壓縮表示這個(gè)文件中的信息有多種方法。我們考慮用0，1碼串來(lái)表示字符的方法，即每個(gè)字符用唯一的一個(gè)0，1串來(lái)表示。問(wèn)題要求使用二進(jìn)制數(shù)字0，1碼串來(lái)編碼，保證編碼是前綴碼的前提下使得壓縮文件最短。（為了使得譯碼容易，編碼必須具有性質(zhì)：任一字符的代碼都不是其它字符代碼的前綴。我們稱這樣的編碼為前綴碼。）2024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院658.5

文件壓縮（Huffman算法）

abcdef頻率（千次）4513121695定長(zhǎng)碼000001010011100101變長(zhǎng)碼0101100111110111002024/3/21華南師范大學(xué)計(jì)算機(jī)學(xué)院668.5

文件壓縮（Huffman算法）