數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用-C++描述13

最優(yōu)化問(wèn)題貪婪算法思想1/21/20221Chapter13

The

Greedy

Method

每個(gè)最優(yōu)化問(wèn)題都包含一組限制條件

(constraint)和一個(gè)優(yōu)化函數(shù)

(optimization

function)，符合限制條件的問(wèn)題求解方案稱(chēng)為可行解

(feasible

solution)，使優(yōu)化函數(shù)取得最佳值的可行解稱(chēng)為最優(yōu)解

(optimal

solution)。1/21/20222最優(yōu)化問(wèn)題

有一艘大船準(zhǔn)備用來(lái)裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i個(gè)貨箱的重量為wi（1≤i≤n），而貨船的最大載重量為c。目的是在貨船上裝入最多的貨物。1/21/20223裝載問(wèn)題

設(shè)存在一組變量xi，其可能取值為0或1。如xi為0，則貨箱i將不被裝上船；如xi為1，則貨箱i將被裝上船。

目的是找到一組xi，使它滿足限制條

件Σwixi

≤c且xi∈{0,

1},

1≤i≤n。相應(yīng)的優(yōu)化函數(shù)是Σxi

滿足限制條件的每一組xi都是一個(gè)可行解，能使Σxi取得最大值的方案是最優(yōu)解。裝載問(wèn)題-最優(yōu)化問(wèn)題描述1/21/20224

城市及城市之間所有可能的通信連接可被視作一個(gè)無(wú)向圖，圖的每條邊都被賦予一個(gè)權(quán)值，權(quán)值表示建成由這條邊所表示的通信連接所要付出的代價(jià)。

包含圖中所有頂點(diǎn)（城市）的連通子圖都是一個(gè)可行解。設(shè)所有的權(quán)值都非負(fù)，則所有可能的可行解都可表示成無(wú)向圖的一組生成樹(shù)，而最優(yōu)解是其中具有最小代價(jià)的生成樹(shù)。

限制條件：所有的邊構(gòu)成一個(gè)生成樹(shù)。優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。1/21/20225最小代價(jià)通訊網(wǎng)絡(luò)

在貪婪算法(greedy

method)中采用逐步構(gòu)造最優(yōu)解的方法。

在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。

作出貪婪決策的依據(jù)稱(chēng)為貪婪準(zhǔn)則

(greedy

criterion)。1/21/20226算法思想最短路徑

如圖所示的有向網(wǎng)絡(luò)，路徑的長(zhǎng)度定義為路徑所經(jīng)過(guò)的各邊的耗費(fèi)之和。要求找一條從初始頂點(diǎn)s到達(dá)目的頂點(diǎn)d的最短路徑。1/21/20227最短路徑-貪婪算法思想1/21/20228

貪婪算法分步構(gòu)造這條路徑，每一步在路徑中加入一個(gè)頂點(diǎn)。

假設(shè)當(dāng)前路徑已到達(dá)頂點(diǎn)q，且頂點(diǎn)q并不是目的頂點(diǎn)d。加入下一個(gè)頂點(diǎn)所采用的貪婪準(zhǔn)則為：選擇離q最近且目前不在路徑中的頂點(diǎn)。

這種貪婪算法并不一定能獲得最短路徑。(例1->5)以前的貪婪算法1/21/20229

在機(jī)器調(diào)度問(wèn)題中，貪婪算法-LPT調(diào)度并不能保證最優(yōu)，然而，那是一種直覺(jué)的傾向且一般情況下結(jié)果總是非常接近最優(yōu)值。它利用的規(guī)則就是在實(shí)際環(huán)境中希望人工機(jī)器調(diào)度所采用的規(guī)則。

算法并不保證得到最優(yōu)結(jié)果，但通常所得結(jié)果與最優(yōu)解相差無(wú)幾，這種算法也稱(chēng)為啟發(fā)式方法(heuristics)。因此LPT方法是一種啟發(fā)式機(jī)器調(diào)度方法。

根據(jù)LPT調(diào)度的完成時(shí)間與最佳調(diào)度的完成時(shí)間之間的關(guān)系，LPT啟發(fā)式方法具有限定性能(bounded

performance)。具有限定性能的啟發(fā)式方法稱(chēng)為近似算法(approximation

algorithm)貪婪算法1/21/202210

在有些應(yīng)用中，貪婪算法所產(chǎn)生的結(jié)果總是最優(yōu)的解決方案。

但對(duì)其他一些應(yīng)用，生成的算法只是一種啟發(fā)式方法?？赡苁且部赡懿皇墙扑惴?。

可利用如下貪婪準(zhǔn)則：從剩下的貨箱中，選擇重量最小的貨箱。

這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。

根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。1/21/202211貨箱裝船問(wèn)題n=8,[w1,...w8]=[100,200,50,90,150,50,20,80],c=400。1/21/202212貨箱裝船問(wèn)題例利用貪婪算法能產(chǎn)生最佳裝載。1/21/202213貨箱裝船問(wèn)題0/1背包問(wèn)題

在0/1背包問(wèn)題中，需對(duì)容量為c的背包進(jìn)行裝載。從n個(gè)物品中選取裝入

背包的物品，每件物品i的重量為wi，價(jià)值為pi。

對(duì)于可行的背包裝載，背包中物品的總重量不能超過(guò)背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即取得最大值。約束條件為∑

wixi<=c和xi∈[0,1](1≤i≤n)。1/21/2022140/1背包問(wèn)題1/21/202215

在這個(gè)表達(dá)式中，需求出xt的值。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包。

0/1背包問(wèn)題是一個(gè)一般化的貨箱裝載問(wèn)題，即每個(gè)貨箱所獲得的價(jià)值不同。

貨箱裝載問(wèn)題轉(zhuǎn)化為背包問(wèn)題的形式為：船作為背包，貨箱作為可裝入背包的物品。0/1背包問(wèn)題貪婪策略11/21/202216

貪婪準(zhǔn)則：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品。

利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。

n=3,w=[100,10,10],p=[20,15,15],c=105。0/1背包問(wèn)題貪婪策略21/21/202217 重量貪婪準(zhǔn)則：從剩下的物品中選擇可裝入背包的重量最小的物品。

雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解。n=2,w=[10,20],p=[5,100],c=25。0/1背包問(wèn)題貪婪策略31/21/202218

價(jià)值密度貪婪準(zhǔn)則：從剩余物品中選擇可裝入包的pi

/wi值最大的物品。這種策略也不能保證得到最優(yōu)解。n=3,w=[20,15,15],p=[40,25,25],c=30。0/1背包問(wèn)題1/21/2022190/1背包問(wèn)題是一個(gè)NP-復(fù)雜問(wèn)題。

一個(gè)復(fù)雜的工程通?？梢苑纸獬梢唤M小任務(wù)的集合，完成這些小任務(wù)意味著整個(gè)工程的完成。

任務(wù)的先后順序可用有向圖表示--稱(chēng)為頂點(diǎn)活動(dòng)(Activity

On

Vertex,AOV)網(wǎng)絡(luò)。有向圖的頂點(diǎn)代表任務(wù)，有向邊(i,

j) 表示先后關(guān)系：任務(wù)j開(kāi)始前任務(wù)i必須完成。1/21/202220拓?fù)渑判騿?wèn)題任務(wù)有向圖1/21/202221假設(shè)某專(zhuān)業(yè)的學(xué)生在學(xué)習(xí)期間總共要學(xué)9門(mén)課程(分別用C0,C1,…,C8表示)，其中有些課程是獨(dú)立于其它課程的，而另一些課程必須在學(xué)完其先修課程后才能開(kāi)始。對(duì)各課程間的先后關(guān)系可以用一

個(gè)AOV網(wǎng)表示，如下圖所示。C2C6C0C3C1C5C4C7C8

在很多條件下，任務(wù)的執(zhí)行是連續(xù)進(jìn)行的。可根據(jù)所建議的順序來(lái)裝配。

在由任務(wù)建立的有向圖中，邊(i,j)表示在裝配序列中任務(wù)i在任務(wù)j的前面，具有這種性質(zhì)的序列稱(chēng)為拓?fù)湫蛄?topological

orders或topological

sequences)。

根據(jù)任務(wù)的有向圖建立拓?fù)湫蛄械倪^(guò)程稱(chēng)為拓?fù)渑判颍╰opologicalsorting）。1/21/202223拓?fù)渑判騿?wèn)題例1/21/202224有哪些拓?fù)湫蛄?142356是拓?fù)湫蛄?

算法按從左到右的步驟構(gòu)造拓?fù)湫蛄?，每一步在排好的序列中加入一個(gè)頂點(diǎn)。利用如下貪婪準(zhǔn)則來(lái)選擇頂點(diǎn)：從剩下的頂點(diǎn)中，選擇頂點(diǎn)w，使得w不存在這樣的入邊

(v,w)，其中頂點(diǎn)v不在已排好的序列結(jié)構(gòu)中出現(xiàn)。

注意到如果加入的頂點(diǎn)w違背了這個(gè)準(zhǔn)則

(即有向圖中存在邊(v,w)且v不在已構(gòu)造的序列中)，則無(wú)法完成拓?fù)渑判?，因?yàn)轫旤c(diǎn)v必須跟隨在頂點(diǎn)w之后。1/21/202225拓?fù)渑判騿?wèn)題貪婪策略設(shè)n是有向圖中的頂點(diǎn)數(shù)設(shè)V是一個(gè)空序列

while(true){設(shè)w不存在入邊(v,w)，其中頂點(diǎn)v不在V中如果沒(méi)有這樣的w，break。把w添加到V的尾部}if(V中的頂點(diǎn)數(shù)少于n)算法失敗

else

V是一個(gè)拓?fù)湫蛄?/21/202226拓?fù)渑判騜ool

Network::Topological(int

v[]){//計(jì)算有向圖中頂點(diǎn)的拓?fù)浯涡?/如果找到了一個(gè)拓?fù)浯涡?，則返回true，此時(shí)，在v

[0:n-1]中記錄拓?fù)浯涡?/如果不存在拓?fù)浯涡?，則返回falseint

n=Vertices();//計(jì)算入度int

*InDegree

=

new

int

[n+1];InitializePos();//圖遍歷器數(shù)組for

(int

i=1;

i<=n;

i++)//初始化

InDegree[i]=0;1/21/202227拓?fù)渑判?/計(jì)算各頂點(diǎn)入度f(wàn)or

(i=1;

i<=n;

i++){//從i出發(fā)的邊

int

u=Begin(i);while

(u)

{InDegree[u]++

;u

=

NextVertex(i)

;

}}}//把入度為０的頂點(diǎn)壓入堆棧(保存候選頂點(diǎn))

LinkedStack<int>

S;for

(i

=

1;

i

<=

n;

i++)if

(!InDegree[i])

S.Add(i);1/21/202228拓?fù)渑判?/產(chǎn)生拓?fù)浯涡騣=0;//數(shù)組v的游標(biāo)while

(!S.IsEmpty()){//從堆棧中選擇

int

w;//下一個(gè)頂點(diǎn)S.Delete(w)

;v[i++]

=

w;int

u=Begin(w);while

(u){//修改入度InDegree[u]--;if

(!InDegree[u])

S.Add(u);u

=

NextVertex(w)

;

}}1/21/202229拓?fù)渑判駾eactivatePos()

;delete

[]

InDegree;return

(i

==

n);}1/21/202230拓?fù)渑判?/p>

給出有向圖G，它的每條邊都有一個(gè)非負(fù)的長(zhǎng)度（耗費(fèi)）

a

[i][j]，路徑的長(zhǎng)度即為此路徑所經(jīng)過(guò)的邊的長(zhǎng)度之和。

對(duì)于給定的源頂點(diǎn)s，需找出從它到圖中其他任意頂點(diǎn)（稱(chēng)為目的）的最短路徑。1/21/202231單源最短路問(wèn)題單源最短路問(wèn)題1/21/202232

利用E.

Dijkstra發(fā)明的貪婪算法可以解決最短路徑問(wèn)題，它通過(guò)分步方法求出最短路徑。

每一步產(chǎn)生一個(gè)到達(dá)新的目的頂點(diǎn)的最短路徑。下一步所能達(dá)到的目的頂點(diǎn)通過(guò)如下貪婪準(zhǔn)則選?。涸谶€未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑長(zhǎng)度最短的目的頂點(diǎn)。

也就是說(shuō)，Dijkstra的方法按路徑長(zhǎng)度順序產(chǎn)生最短路徑。1/21/202233單源最短路問(wèn)題貪婪策略

首先最初產(chǎn)生從s到它自身的路徑，這條路徑?jīng)]有邊，其長(zhǎng)度為0。在貪婪算法的每一步中，產(chǎn)生下一個(gè)最短路徑。

一種方法是在目前已產(chǎn)生的最短路徑中加入一條可行的最短的邊，結(jié)果產(chǎn)生的新路徑是原先產(chǎn)生的最短路徑加上一條邊。這種策略并不總是起作用。

另一種方法是在目前產(chǎn)生的每一條最短路徑中，考慮加入一條最短的邊，再?gòu)乃羞@些路徑中先選擇最短的，這種策略即是

Dijkstra算法。1/21/202234分析

可以驗(yàn)證按長(zhǎng)度順序產(chǎn)生最短路徑時(shí)，下一條最短路徑總是由一條已產(chǎn)生的

最短路徑加上一條邊形成。

實(shí)際上，下一條最短路徑總是由已產(chǎn)生的最短路徑再擴(kuò)充一條最短的邊得到的，且這條路徑所到達(dá)的頂點(diǎn)其最短路徑還未產(chǎn)生。1/21/202235分析單源最短路問(wèn)題1/21/202236

可用一種簡(jiǎn)便的方法來(lái)存儲(chǔ)最短路徑?？梢岳脭?shù)組p，p[i]給出從s到達(dá)i的路徑中頂點(diǎn)i前面的那個(gè)頂點(diǎn)。在本例中p[1:5]=[0,1,1,3,4]。從s到頂點(diǎn)i的路徑可反向創(chuàng)建。從i出發(fā)按

p[i],p[p[i]],p[p[p[i]]],…的順序，直到到達(dá)頂點(diǎn)s或0。

在本例中，如果從i=5開(kāi)始，則頂點(diǎn)序列為p[i]=4,p[4]=3,p[3]=1=s，因此路徑為1,3,4,5。1/21/202237分析

為能方便地按長(zhǎng)度遞增的順序產(chǎn)生最短路徑，定義d[i]為在已產(chǎn)生的最短路徑中加入一條最短邊的長(zhǎng)度，從而使得擴(kuò)充的路徑到達(dá)頂點(diǎn)i。最初，僅有從s到s的一條長(zhǎng)度為0的路徑，這時(shí)對(duì)于每個(gè)頂點(diǎn)i，d[i]等于a[s][i]（a是有向圖的長(zhǎng)度鄰接矩

陣）。為產(chǎn)生下一條路徑，需要選擇還未產(chǎn)生最短路徑的下一個(gè)節(jié)點(diǎn)，在這些節(jié)點(diǎn)中d值最小的即為下一條路徑的終點(diǎn)。當(dāng)獲得一條新的最短路徑后，由于新的最短路徑可能會(huì)產(chǎn)生更小的d值，因此有些頂點(diǎn)的

d值可能會(huì)發(fā)生變化。1/21/202238算法分析1)初始化d[i]=a[s][i]（1≤i≤n），對(duì)于鄰接于s的所有頂點(diǎn)i，置p[i]=s,對(duì)于其余的頂點(diǎn)置p[i]=0；對(duì)于p[i]≠0的所有頂點(diǎn)建立L表。

2)若L為空，終止，否則轉(zhuǎn)至3)。從L中刪除d值最小的頂點(diǎn)->i。對(duì)于與i鄰接的所有還未到達(dá)的頂點(diǎn)j，更 新d[j]值為min{d[j],d[i]+a[i][j]}；若

d[j]發(fā)生了變化且j還未在L中，則置

p[j]=i，并將j加入L，轉(zhuǎn)至2。1/21/202239最短路徑算法的描述40template<class

T>void

AdjacencyWDigraph<T>::ShortestPaths(int

s,T

d[],int

p[]){//尋找從頂點(diǎn)s出發(fā)的最短路徑,在d中返回最短距離，在p中返回前繼頂點(diǎn)if(s<1||s>n)throw

OutOfBounds();Chain<int>L;//路徑可到達(dá)頂點(diǎn)的列表ChainIterator<int>I;//初始化d,p,Lfor(int

i=1;i<=n;i++){d[i]=a[s][i];if(d[i]==NoEdge)p[i]=0;else{

p[i]=s;

L.Insert(0,i);}1}/21/2022最短路徑程序//更新d,pwhile(!L.IsEmpty()){//尋找具有最小d的頂點(diǎn)vint

*v=I.Initialize(L);int

*w=I.Next();while(w){if(d[*w]<d[*v])v=w;w=I.Next();}1/21/202241最短路徑程序//從L中刪除通向頂點(diǎn)v的下一最短路徑并更新dint

i=*v;L.Delete(*v);for(int

j=1;j<=n;j++){if(d[j]>d[i]+a[i][j])){//減小d[j]d[j]=d[i]+a[i][j];//將j加入Lif(!p[j])L.Insert(0,j);p[j]=i;}}}

}1/21/202242最短路徑程序

若圖是連通的無(wú)向圖或強(qiáng)連通的有向圖，則從其中任何一個(gè)頂點(diǎn)出發(fā)都可以系統(tǒng)地訪問(wèn)到圖中所有的頂點(diǎn)。

圖的所有頂點(diǎn)加上遍歷過(guò)程中經(jīng)過(guò)的邊構(gòu)成圖的生成樹(shù)。有n個(gè)頂點(diǎn)圖的生成樹(shù)必有n-1條邊。1/21/202243圖的生成樹(shù)

圖的生成樹(shù)不是唯一的，從不同的頂點(diǎn)出發(fā)，按不同的方法遍歷，可以得到不同的生成樹(shù)。

對(duì)于連通的網(wǎng)絡(luò)G，邊是帶權(quán)的，而G的生成樹(shù)的各個(gè)邊也帶權(quán)。把在網(wǎng)絡(luò)G的各個(gè)生成樹(shù)中各邊的權(quán)值之和為最小的生成樹(shù)，稱(chēng)為G的最小生成樹(shù)。1/21/202244圖的最小生成樹(shù)

至少可以采用三種不同的貪婪策略來(lái)選擇這n-1條邊。

這三種求解最小生成樹(shù)的貪婪算法策略是：1.Kruskal算法

2.Prim算法

3.Sollin算法1/21/202245最小耗費(fèi)生成樹(shù)問(wèn)題 Kruskal算法每次選擇n-1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。1/21/202246Kruskal算法

注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹(shù)。

Kruskal算法分e步，其中e是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來(lái)考慮這e條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將

其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則

將其拋棄，否則，將它選入。1/21/202247分析例1/21/202248例1/21/202249例1/21/2022