資源描述：
《算法設(shè)計(jì)技巧與分析 第8章 貪心算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、算法設(shè)計(jì)技巧與分析AlgorithmsDesignTechniquesandAnalysis南方醫(yī)科大學(xué)醫(yī)工學(xué)院信息技術(shù)系第8章貪心算法理解貪心算法的基本原理掌握貪心算法的算法實(shí)例（難點(diǎn)）掌握用貪心算法設(shè)計(jì)算法的方法（重點(diǎn)）TeachingRequestContent貪心算法原理算法實(shí)例單源最短路徑問題最小耗費(fèi)生成樹(Kruskal)最小耗費(fèi)生成樹(Prim)文件壓縮Example：PackageProblem0-1背包問題：給定n種物品和一個(gè)背包。物品i的體積是si，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大？背包
2、問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包。GreedyAlgorithmvoidKnapsack(intn,floatM,floatv[],floats[],floatx[]){Sort(n,v,s);//將各種物品按單位體積價(jià)值排序for(inti=1;i<=n;i++)x[i]=0;//將解向量初始化為零floatc=M;//將背包剩余容量初始化為Mfor(i=1;i<=n;i++){if(s[i]>c)break;x[i]=1;c-=s[i];}if(i<=n)x[i]=c/s[i];}首先
3、計(jì)算每種物品單位體積的價(jià)值vi/si，然后將盡可能多的單位體積價(jià)值最高的物品裝入背包。SingleSourceShortestPaths設(shè)：G=(V,E)為一個(gè)有向圖，每一條邊都具有非負(fù)長(zhǎng)度，有一個(gè)特異頂點(diǎn)s稱為源。求：從s到V中每一個(gè)其他頂點(diǎn)v的距離，即最短路徑δ(v)。假設(shè)：V={1,2,…,n}，并且s=1。BasePrincipleofDijkstra將頂點(diǎn)分為兩個(gè)集合X和Y，其中X包含的是距離已經(jīng)確定的頂點(diǎn)，令λ(y)為Y中頂點(diǎn)y只經(jīng)過X中頂點(diǎn)的最短路徑的長(zhǎng)度，則1.初始時(shí)X={1}，Y={2,3,…,n}；2.從Y中選定距離已經(jīng)確定的頂點(diǎn)y，將其移至X
4、；3.更新Y中與y相鄰的其他頂點(diǎn)的標(biāo)記；4.迭代直至Y為空。Example1234561129345131540112∞∞∞410198171317算法8.1 DIJKSTRA輸入:含權(quán)有向圖G=(V，E)，V=(1，2，···，n)。輸出:G中頂點(diǎn)1到其他頂點(diǎn)的距離。2.fory←2ton5.endif6.endfor1.X=｛1｝;Y←V-｛1｝;[1]←04.else[y]←3.ify相鄰于1then[y]←length[1，y]10.Y←Y-{y}{將頂點(diǎn)y從Y中刪除}7.forj←1ton-19.X←X∪{y}{將頂點(diǎn)y加入X}11.for每條邊(y，w
5、)14.endfor8.令yY，使得[y]為最小12.ifwYand[y]+length[y,w]<[w]then15.endfor13.[w]←[y]+length[y,w]在算法DIJKSTRA中，當(dāng)頂點(diǎn)y在第8步中被選中，如果標(biāo)記λ(y)是有限的，那么λ(y)=δ(y)。引理8.1TimeComplexity第8步：執(zhí)行了n-1次，每次時(shí)間是Θ(n)共需時(shí)間Θ(n2)第11步：for循環(huán)執(zhí)行了m次，m=
6、E
7、共需時(shí)間Θ(m)算法的時(shí)間復(fù)雜度：Θ(n2+m)定理8.1給出一個(gè)邊具有非負(fù)權(quán)的有向圖G和源頂點(diǎn)s，算法DIJKSTRA在時(shí)間內(nèi)找出從s到其它每一頂點(diǎn)距
8、離的長(zhǎng)度。AmendatoryAlgorithm思路：用最小堆數(shù)據(jù)結(jié)構(gòu)來(lái)保持集合Y中的頂點(diǎn)，使Y組中離V-Y最近的頂點(diǎn)y可以在Ο(logn)時(shí)間內(nèi)被選出。堆定義：是一個(gè)幾乎完全的二叉樹，總是保持父節(jié)點(diǎn)的鍵值不小于子節(jié)點(diǎn)的鍵值。堆運(yùn)算：SIFT-UP、SIFT-DOWN、DELETEMAX、DELETE、INSERT、MAKEHEAP算法8.2 SHORTESTPATH輸入:含權(quán)有向圖G=(V，E)，V=(1，2，···，n)。輸出:G中頂點(diǎn)1到其他頂點(diǎn)的距離，假設(shè)已有一個(gè)空堆H。2.fory←2ton3.ify鄰接于1then6.INSERT(H，y)7.else
9、5.key[y]←[y]4.[y]←length[1，y]1.Y←V-｛1｝;[1]←0;key(1)←[1]8.[y]←9.key(y)←[y]10.endif11.endfor12.forj←1ton-114.Y←Y-{y}{將頂點(diǎn)y從Y中刪除}19.endif13.y←DELETEMIN(H)15.for每個(gè)鄰接于y的頂點(diǎn)wY16.if[y]+length[y,w]<[w]then20.ifwHthenINSERT(H，w)18.key(w)←[w]17.[w]←[y]+length[y,w]21.elseSIFTUP(，(w))22.endif23.end
10、for24
