計(jì)算理論與算法分析設(shè)計(jì)課件：貪心法

貪心法（貪婪法）

2024/7/52

of158數(shù)錢

一出納員支付一定數(shù)量的現(xiàn)金。假設(shè)他手

中有各種面值的紙幣和硬幣，要求他用最

少的貨幣數(shù)支付規(guī)定的現(xiàn)金。

例如，現(xiàn)有4種硬幣：它們的面值分別為1

分、2分、5分和1角。要支付2角5分。首先支付2個(gè)1角硬幣，然后支付一個(gè)5分

硬幣，這就是貪心策略。2024/7/53

of158貪心法不一定能產(chǎn)生正確的答案。例如，若引進(jìn)一個(gè)1角1分的硬幣，設(shè)從如下集合{1,1,2,2,2,5,10,10,11,11}中數(shù)出25分，按貪心法，共4個(gè)硬幣。但最優(yōu)解僅為3個(gè)硬幣。這說(shuō)明貪心法得到的解只是一個(gè)可行解。2024/7/54

of158貨郎擔(dān)（TSP）問(wèn)題設(shè)售貨員要到五個(gè)城市去售貨，最后再回到出發(fā)的城市。已知從一個(gè)城市到其他城市的費(fèi)用，求總費(fèi)用最少的路線2024/7/55

of158權(quán)為13從不同結(jié)點(diǎn)出發(fā)：

1）結(jié)點(diǎn)a為起點(diǎn)：

2）結(jié)點(diǎn)b為起點(diǎn)：

3）結(jié)點(diǎn)c為起點(diǎn)：

4）結(jié)點(diǎn)d為起點(diǎn)：權(quán)為13權(quán)為13權(quán)為13abcd213743或者152024/7/56

of158而實(shí)際上圖中最短哈密頓

回路的長(zhǎng)度為12。即abcdaabcd2137432024/7/57

of158Huffman編碼某通訊系統(tǒng)只使用5種字符a、b、c、d、e，使用頻率分別為0.1,0.14,0.2,0.26,0.3,利用二叉樹設(shè)計(jì)不等長(zhǎng)編碼：1）構(gòu)造以a、b、c、d、e為葉子的二叉樹；2）將該二叉樹所有左分枝標(biāo)記0，所有右

分枝標(biāo)記1；3）從根到葉子路徑上標(biāo)記作為葉子結(jié)點(diǎn)所

對(duì)應(yīng)字符的編碼；2024/7/58

of158

acbdea:000b:001c:01d:10e:115種字符a、b、c、d、e，使用頻率分別為0.1,0.14,0.2,0.26,0.330000-(1000+1400)*3-(2000+2600+3000)*2=76002024/7/59

of158Huffman編碼:貪心選擇性質(zhì)《算法導(dǎo)論》P234以及教材P1122024/7/510

of158Huffman編碼:貪心選擇性質(zhì)2024/7/511

of158背包問(wèn)題

已知一個(gè)容量大小為M重量的背包和n種物品，物品i的重量為wi,假定物品i的一部分xi放入背包會(huì)得到vixi這么大的收益，這里，0≤xi≤1，vi>0。采用怎樣的裝包方法才會(huì)使裝入背包的物品總效益最大？例：考慮以下情況下的背包問(wèn)題

n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)2024/7/512

of158n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

1)按效益值非增次序?qū)⑽锲芬来畏湃氡嘲?/p>

(x1,x2,x3)Σwixi

Σvixi2)按物品重量的非降次序?qū)⑽锲芬来畏湃氡嘲?1,2/15,0)2028.2(0,2/3,1)20312024/7/513

of158n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

3)按vi/wi的非增次序?qū)⑽锲芬来畏湃氡嘲?/p>

(x1,x2,x3)Σwixi

Σvixi

(0,1,1/2)2031.5算法：背包問(wèn)題的貪心算法2024/7/514

of158voidGreedyKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//使v1/w1≥v2/w2≥…≥vn/wn

for(inti=1;i<=n;i++)x[i]=0;floatc=M;

for(inti=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}2024/7/515

of158算法的時(shí)間復(fù)雜性為

O(nlogn)下面來(lái)證明使用此貪心算法所得到的貪

心解是一個(gè)最優(yōu)解。證明的基本思想是：把這個(gè)貪心解與任一個(gè)最優(yōu)解相比較，如

果這兩個(gè)解不同，就去找開始不同的第一

個(gè)xi，然后設(shè)法用貪心解的這個(gè)xi去代換最優(yōu)解的那個(gè)xi，并證明在分量作了代換2024/7/516

of158

之后其總效益與代換之前無(wú)任何損失。反復(fù)進(jìn)行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明了貪心解是最優(yōu)解。定理：如果v1/w1

≥v2/w2

≥···

≥

vn/wn,

則此算法對(duì)于給定的背包問(wèn)題實(shí)例生成一

個(gè)最優(yōu)解。2024/7/517

of1582024/7/518

of158j是使xj

≠1的最小下標(biāo),k是使

yk

≠xk的最小下標(biāo)。X=(1,1,1/2,0)Y=(1,1,2/3,1/3)j=3,k=3,所以k=j,并且y3>x3(2)X=(1,1,1/2,0)Y=(1,1,1/2,1/2)j=3,k=4,所以k>j,并且y4>x4從而證明了yk<xk

，并且k<=j2024/7/519

of158j是使xj

≠1的最小下標(biāo),k是使

yk

≠xk的最小下標(biāo)。n=4,M=16,(v1,v2,v3,v4)=(20,12,6,6)(w1,w2,w3,w4)=(10,12,6,6)X=(1,1/2,0,0)Y=(1,1/3,1/6,1/6)并且k=2,j=2Z=(1,1/2,z3,z4)代換w3(y3－z3)+w4(y4－z4)=w2(1/2－1/3)6(1/6－z3)+6(1/6－z4)=12*1/6z3+z4=0即推得Z=(1,1/2,0,0)＝X2024/7/520

of1582024/7/521

of158有限期的任務(wù)安排問(wèn)題用貪心法求解有限期的任務(wù)安排問(wèn)題：假設(shè)只能在同一臺(tái)機(jī)器上加工n個(gè)任務(wù)，每個(gè)任務(wù)i完成時(shí)間均是一個(gè)單位時(shí)間。又設(shè)每個(gè)任務(wù)i都有一個(gè)完成期限di>0,當(dāng)且僅當(dāng)任務(wù)i在它的期限截止以前被完成時(shí)，任務(wù)i才能獲得pi的效益，每個(gè)任務(wù)的期限從整個(gè)工序的開工開始計(jì)時(shí)，問(wèn)應(yīng)如何安排加工順序，才能獲得最大效益？n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2)2024/7/522

of158有限期的任務(wù)安排問(wèn)題

首先按效益非增次序進(jìn)行排序，然后按照

期限依次對(duì)此次序進(jìn)行調(diào)整，排在后面的

或提前或排除。算法的粗略描述

voidGreedy-Job(D,J,n)

/*任務(wù)按p1≥p2≥···

≥

pn

的次序輸入，它們的期限值D[i]≥1,1≤i≤n,n≥1,J是可以在它們的期限截止前完成的任務(wù)的集合*/2024/7/523

of158{

J←{1};

for(i=2;i<=n;i++)

if（J∪{i}

的所有任務(wù)都能在它

們的截止期限前完成）

J←J∪{i};

}定理：算法Greedy-Job對(duì)于有期限的任務(wù)

安排問(wèn)題得到一個(gè)最優(yōu)解。

證明：X→Y→Z

貪心解最優(yōu)解2024/7/524

of158假設(shè)n個(gè)任務(wù)已按p1≥p2≥···

≥

pn

排序。首先將任務(wù)1存入解數(shù)組J中，然后處理任務(wù)2到任務(wù)n。假設(shè)已處理了i-1個(gè)任務(wù),其中有k個(gè)任務(wù)已記入J(1),J(2),···,J(k)之中，并且有d(J(1))≤d(J(2))≤···≤d(J(k))?，F(xiàn)在處理任務(wù)i。為了判斷J∪{i}是否可行，只需看能否找出這樣的位置：可以按期限的非降次序插入任務(wù)i，使得i在此處插入后，有d(J(r))≥r,1≤r≤k+1。2024/7/525

of158

找任務(wù)i可能的插入位置可如下進(jìn)行：（a）若d(i)>d(J(k)),即任務(wù)i的期限比這k個(gè)任務(wù)的所有期限都長(zhǎng)，則i可直接加入到k個(gè)任務(wù)的后面，即J(k+1)=i（b）將d(J(k)),d(J(k-1)),···,d(J(1))逐個(gè)與d(i)比較,直到找到位置q，它使得①d(J(q))≤d(i)<d(J(t))q<t≤k2024/7/526

of158

此時(shí)若②d(J(t))>tq<t≤k這說(shuō)明：第t個(gè)要加工的任務(wù)以及它以后加工的所有任務(wù)都可以向后移動(dòng)一個(gè)單位時(shí)間。即這k-q個(gè)任務(wù)均可延遲一個(gè)單位時(shí)間加工。在以上條件成立的情況下，只要③

d(i)≥q+1，就可將任務(wù)i插入到第q+1個(gè)位置上，從而得到一個(gè)按期限的非降次序排列的含有k+1個(gè)任務(wù)的可行解。2024/7/527

of158以上過(guò)程反復(fù)進(jìn)行到對(duì)第n個(gè)任務(wù)處理完畢。所得到的貪心解就是一個(gè)最優(yōu)解。

任務(wù)0123456

pi030252015105

di0352231J(1)=3J(2)=4J(3)=1J(4)=2

總效益：902024/7/528

of158voidgreedy-job(d,J,n,k)

/*任務(wù)按p1≥p2≥···

≥

pn

的次序輸入，它們的期限值d(i)≥1,1≤i≤n,n≥1,J(i)是最優(yōu)解中的第i個(gè)任務(wù)，結(jié)束時(shí)d(J(i))≤d(J(i+1))*/2024/7/529

of158{d(0)←0;J(0)←0;k←1;J(1)←1;

for(i=2;i<=n;i++)

{q←k;

if(d(J(q))<d(i)){J(q+1)←i;k←k+1;}

else

{while(d(J(q))>d(i)&&d(J(q))>q)

q←q-1;

if(d(J(q))≤d(i)&&d(i)>q)2024/7/530

of158

{

for(t=k;t<=q+1;t--)

J(t+1)←J(t);

J(q+1)←i;k←k+1;

}

}

}

}

2024/7/531

of158活動(dòng)安排:問(wèn)題描述有n個(gè)活動(dòng)集E={1,2,…,n}使用同一資源，而同一時(shí)間內(nèi)同一資源只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)的使用時(shí)間為[si,fi)i=1,…,n，si為開始時(shí)間，fi為結(jié)束時(shí)間，若[si,fi)與[sj,fj)不相交稱活動(dòng)i和活動(dòng)j是相容的。問(wèn)題：選出最大的相容活動(dòng)子集合。2024/7/532

of158貪心策略將各活動(dòng)按結(jié)束時(shí)間排序f1≤f2≤…≤fn，先選出活動(dòng)1，然后按活動(dòng)編好從小到大的次序依次選擇與當(dāng)前活動(dòng)相容的活動(dòng)。注：這種策略使剩余的可安排時(shí)間極大化，以便于安排盡可能多的相容活動(dòng)。

證明：見《算法導(dǎo)論》P2242024/7/533

of1582024/7/534

of158voidActivitySelection(intn,s[],f[],boola[]){//f[]已排序，a[]記錄選擇的活動(dòng)，即a[i]=true表示活動(dòng)i已選擇

a[1]=true;

intj=1;

for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;}elsea[i]=false;}}T(n)=O(nlogn)2024/7/535

of158活動(dòng)安排:計(jì)算示例11個(gè)活動(dòng)已按結(jié)束時(shí)間排序，用貪心算法求解：

i1234567891011start_timei

130535688212finish_timei

456789101112131401234567891011121314timea1a2a3a4a5a6a7a8a9a10a11相容活動(dòng)：{a3,a9,a11},{a1,a4,a8,a11},{a2,a4,a9,a11}01234567891011121314timea1a2a3a4a5a6a7a8a9a10a112024/7/536

of158最小生成樹最小生成樹的定義Kruskal算法Prim算法2024/7/537

of158網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。最小生成樹2024/7/538

of158最小生成樹

設(shè)G=(V,E)是一個(gè)無(wú)向連通帶權(quán)圖，如果G的一個(gè)子圖T’是一棵包含G的所有頂點(diǎn)的樹(G的生成樹)，生成樹T’上各邊權(quán)的總和(生成樹的耗費(fèi))最小，則T’稱為G的最小生成樹(MST：minimumspanningtree)144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS2024/7/539

of158

Kruskal最小生成樹算法

Kruskal

在1956年提出了1個(gè)最小生成樹算法。設(shè)G=(V,E)是一個(gè)連通帶權(quán)圖，V={1,2,…,n}。將圖中的邊按其權(quán)值由小到大排序，然后作如下的貪婪選擇，由小到大順序選取各條邊，若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮。如此依次進(jìn)行，到選夠（n-1）條邊即得到最小生成樹。最小生成樹2024/7/540

of158例如，對(duì)于下圖中的帶權(quán)圖各邊按權(quán)值排序?yàn)椋篸13=1d46=2d25=3d36c4d14=

5d34=5d23=5d12=6d35=6d56=62024/7/541

of158按Kruskal算法選取邊的過(guò)程如下圖所示。2024/7/542

of158

Kruskal最小生成樹算法最小生成樹//在一個(gè)具有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)中找棵最小生成樹令E為網(wǎng)絡(luò)中邊的集合令T為所選邊的集合,初始化T為空集

while(E不是空集&&T中元素個(gè)數(shù)不等于n-1){

令(u,v)為E中最小代價(jià)的邊;E=E-(u,v);//從中刪除該邊;if((u,v)加入T中不會(huì)產(chǎn)生環(huán))

將(u,v)加入T;}算法復(fù)雜度為O(n+eloge)2024/7/543

of158Prim最小生成樹算法

Prim在1957年提出另一種算法，這種算法特別適用于邊數(shù)相對(duì)較多，即比較接近于完全圖的圖。此算法是按逐個(gè)將頂點(diǎn)連通的步驟進(jìn)行的，它只需采用一個(gè)頂點(diǎn)集合。這個(gè)集合開始時(shí)是空集，以后將已連通的頂點(diǎn)陸續(xù)加入到集合中去，到全部頂點(diǎn)都加入到集合中了，就得到所需的生成樹。

最小生成樹2024/7/544

of158Prim最小生成樹算法設(shè)G=(V,E)是一個(gè)連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的一棵最小生成樹的Prim算法的過(guò)程是：首先從圖的任一頂點(diǎn)起進(jìn)行，將它加入集合S中置，S={1}，然后作如下的貪婪選擇，從與之相關(guān)聯(lián)的邊中選出權(quán)值c[i][j]最小的一條作為生成樹的一條邊，此時(shí)滿足條件i

S，j

V-S，并將該j加入集合中，表示連兩個(gè)頂點(diǎn)已被所選出的邊連通了。

最小生成樹2024/7/545

of158

以后每次從一個(gè)端點(diǎn)在集合S中而另一個(gè)端點(diǎn)在集合S外的各條邊中選取權(quán)值最小的一條作為生成樹的一條邊，并把其在集合外的那個(gè)頂點(diǎn)加入到集合S中。如此進(jìn)行下去，直到全部頂點(diǎn)都加入到集合中S。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。由于Prim算法中每次選取的邊兩端總是一個(gè)已連通頂點(diǎn)和一個(gè)未連通頂點(diǎn)，故這個(gè)邊選取后一定能將該未連通點(diǎn)連通而又保證不會(huì)形成回路。最小生成樹2024/7/546

of158例如，對(duì)于下圖(a)中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下圖(b)所示。2024/7/547

of158Prim最小生成樹算法最小生成樹//在一個(gè)具有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)中找棵最小生成樹令E為網(wǎng)絡(luò)中邊的集合令T為所選邊的集合,初始化T為空集另S為已在樹中節(jié)點(diǎn)的集合,置S={1};while(E不是空集&&T中元素個(gè)數(shù)不等于n-1){

令(u,v)為u在S中,v不在S中最小代價(jià)的邊;if(沒(méi)有這樣的邊)break;E=E-(u,v);//從中刪除該邊;

將(u,v)加入T;}算法復(fù)雜度為O(n2)2024/7/548

of158排序之車間作業(yè)計(jì)劃模型一：一臺(tái)機(jī)器、n個(gè)零件的排序

目的：使得各加工零件在車間里停留的平均

時(shí)間最短。零件加工時(shí)間11.822.030.540.951.361.5若按此順序：(1.8+3.8+4.3+5.2+6.5+8)/6=4.9實(shí)際上最短：3,4,5,6,1,2(0.5+1.4+2.7+4.2+6+8)/6=3.82024/7/549

of158排序之車間作業(yè)計(jì)劃模型二：兩臺(tái)機(jī)器、n個(gè)零件的排序目的：使得完成全部工作的總時(shí)間最短。2024/7/550

of158某車間需要用一臺(tái)車床和一臺(tái)銑床加工A、B、C、D四個(gè)零件。每個(gè)零件都需要先用車床加工，再用銑床加工。車床與銑床加工每個(gè)零件所需的工時(shí)（包括加工前的準(zhǔn)備時(shí)間以及加工后的處理時(shí)間）如表。工時(shí)（小時(shí)）ABCD車床8624銑床31312若以A、B、C、D零件順序安排加工，則共需32小時(shí)。適當(dāng)調(diào)整零件加工順序，可產(chǎn)生不同實(shí)施方案，我們稱可使所需總工時(shí)最短的方案為最優(yōu)方案。在最優(yōu)方案中，零件A在車床上的加工順序安排在第（1）位，四個(gè)零件加工共需（2）小時(shí)。

（1）A.1

B.2

C.3

D.4

（2）A.21

B.22

C.23

D.242024/7/551

of158以A、B、C、D零件順序安排加工，則共需32小時(shí)。工時(shí)（小時(shí)）ABCD車床8624銑床31312車床ABCD8624銑床313128142032基本方法：在第一臺(tái)機(jī)器上加工時(shí)間越少的零件越早加工；在第二臺(tái)機(jī)器上加工時(shí)間越少的零件越晚加工；2024/7/552

of158(1)第一個(gè)：第二個(gè)：第三個(gè)：第四個(gè):工時(shí)（小時(shí)）ABCD車床8624銑床31312(2)第一個(gè)：第二個(gè)：第三個(gè)：第四個(gè):(3)第一個(gè)：第二個(gè)：第三個(gè)：第四個(gè):(4)第一個(gè)：第二個(gè)：第三個(gè)：第四個(gè):BBCBCADBCACDAB:222024/7/553

of158練習(xí)某車間需要用一臺(tái)車床和一臺(tái)銑床加工A、B、C、D

四個(gè)零件。每個(gè)零件都需要先用車床加工，再用銑床

加工。車床和銑床加工每個(gè)零件所需的工時(shí)（包括

加工前的準(zhǔn)備時(shí)間以及加工后的處理時(shí)間）如下表。工時(shí)(小時(shí))ABCD車床8466銑床6725若以A、B、C、D零件順序安排加工，則共需29小時(shí)。

適當(dāng)調(diào)整零件加工順序，可產(chǎn)生不同實(shí)施方案，在各種

實(shí)施方案中，完成四個(gè)零件加工至少共需（1）小時(shí)。（1）A.25B.26C.27D.28B.26BADC

2024/7/554

of158解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)．

統(tǒng)籌方法2024/7/555

of158統(tǒng)籌方法一、計(jì)劃網(wǎng)絡(luò)圖：統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請(qǐng)畫出其統(tǒng)籌方法網(wǎng)絡(luò)圖。

工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購(gòu)配套零件外購(gòu)生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d2024/7/556

of158１２４５３abcde601383815工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購(gòu)配套零件外購(gòu)生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d123452024/7/557

of158

將上例的工序進(jìn)度表做一些擴(kuò)充如下，請(qǐng)畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。

工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b,ｄdde,ｆ,ｇ１２４５３abcde6013838152024/7/558

of158工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b,ｄdde,ｆ,ｇ１２４５３abcde601383815f102024/7/559

of158

為此需要設(shè)立虛工序。虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來(lái)表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時(shí)間。10152643a60b158e13dc38f１２４５３abcde6013838152024/7/560

of1581256734a6015bec13d388h510fg161257834a6015bec13d388h510f616g

在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。2024/7/561

of158練習(xí)工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購(gòu)零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h2024/7/562

o60b45echj35ig1030d204025f18152024/7/563

of158二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線在繪制出網(wǎng)絡(luò)圖之后，可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久。2024/7/564

of158把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件V1——表示整個(gè)工程開始事件V9——表示整個(gè)工程結(jié)束問(wèn)題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=42024/7/565

of158定義AOE網(wǎng)(ActivityOnEdge)——也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間路徑長(zhǎng)度——路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑——路徑長(zhǎng)度最長(zhǎng)的路徑叫關(guān)鍵路徑Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間e(i)——表示活動(dòng)ai的最早開始時(shí)間l(i)——表示活動(dòng)ai的最遲開始時(shí)間l(i)-e(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)——關(guān)鍵路徑上的活動(dòng)叫關(guān)鍵活動(dòng)，即l(i)=e(i)的活動(dòng)2024/7/566

of158問(wèn)題分析如何找e(i)=l(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)

（2）l(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(源點(diǎn))=0開始遞推(2)從Vl(匯點(diǎn))=Ve(匯點(diǎn))開始向回遞推2024/7/567

of158求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)Ve

Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)el

l－e

000266465877777101616141403020230030032024/7/568

of158某工程包括A、B、C、D、E、F、G

七個(gè)作業(yè)，

各個(gè)作業(yè)的緊前作業(yè)、所需時(shí)間、所需人數(shù)如下表：作業(yè)ABCDEFG緊前作業(yè)——ABBC，DE所需時(shí)間（周）1113232所需人數(shù)5935261該工程的計(jì)算工期為

周。2024/7/569

of158124635A11CE2B1D3F3G2作業(yè)ABCDEFG緊前作業(yè)——ABBC，DE所需時(shí)間（周）1113232所需人數(shù)5935261答案：7周2024/7/570

of158124635A11CE2B1D3F3G2V1V2V3V4V5V6頂點(diǎn)Ve

Vl011437031457ABCDEFG活動(dòng)el

l－e02001113443513ABCDEFG1周1132325人9352612024/7/571

of158124635A11CE2B1D3F3G2ABCDEFG活動(dòng)el

l－e02001113443513ABCDEFG1周1132325人935261B(9)A(5)D(5)A(5)C(3)D(5)A(5)C(3)D(5)C(3)F(6)F(6)F(6)2024/7/572

of1584.2貪心算法的基本要素

對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

2024/7/573

of1584.2貪心算法的基本要素1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。

2024/7/574

of1584.2貪心算法的基本要素2.最優(yōu)子結(jié)構(gòu)性質(zhì)

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2024/7/575

of1584.2貪心算法的基本要素3.貪心算法與動(dòng)態(tài)規(guī)劃算法的差異

貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，并以此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。2024/7/576

of1584.2貪心算法的基本要素0-1背包問(wèn)題：

給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品