第2章 貪婪法.ppt

《第2章 貪婪法.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第2章貪婪法貪婪法的設(shè)計(jì)思想貪婪法解背包問題MST（最小生成樹）問題Prim（普里姆）算法Kruskal（克魯斯卡爾）算法單源（單起點(diǎn)）最短路徑問題Dijkstra（狄斯奎諾）算法本章習(xí)題貪婪法設(shè)計(jì)思想貪婪法（Greedyalgorithms）設(shè)計(jì)思想貪婪法常用來解決最優(yōu)化問題。猶如登山一樣，一步一步向前推進(jìn)。從某個(gè)初始點(diǎn)出發(fā)，根據(jù)當(dāng)前局部的而不是全局的最優(yōu)決策，以滿足約束方程為條件，使目標(biāo)函數(shù)值增加最快或最慢為規(guī)則，決定本步的局部最優(yōu)解。如最速上山法各步的方向選擇——梯度。計(jì)算機(jī)學(xué)家把貪婪法作為一種通用設(shè)計(jì)技術(shù)，通過一系列步驟來構(gòu)造問題的解，每一步對當(dāng)前獲得的局部最優(yōu)解進(jìn)行擴(kuò)展

2、，直到全局最優(yōu)解為止。每一步選擇滿足（與動態(tài)規(guī)劃法不同）：1.可行解：滿足約束條件。2.局部最優(yōu)；當(dāng)前步驟下，所有選擇中的局部最佳選擇（貪婪）。3.不可取消：當(dāng)前局部解一旦得到，后續(xù)步驟無法改變。貪婪法認(rèn)為，全局最優(yōu)解是由一系列步驟的局部最優(yōu)解構(gòu)成。優(yōu)點(diǎn)：比動態(tài)規(guī)劃法的時(shí)間和空間效率高，算法設(shè)計(jì)也較簡單。但對于某些問題，貪婪法不能獲得全局最優(yōu)解。因此，算法設(shè)計(jì)時(shí)，需考慮問題是否適合用貪婪法解，即貪婪法得到的解是否全局最優(yōu)解。簡例：找零錢簡例：找零錢已知：有4種面額的硬幣：25分、10分、5分、1分。要求：用最少數(shù)量的硬幣支付48分零錢。（目標(biāo)值48：問題規(guī)模）算法步驟：1.支付面

3、額滿足約束條件（≤48分）的最大硬幣（25分）；（貪婪）2.計(jì)算目標(biāo)函數(shù)值48-25=23；判斷是否達(dá)到要求（0分）：若是，算法停止，否則，返回1步。計(jì)算結(jié)果：25，10，10，1，1，1?！?個(gè)錢幣算法策略：總是作出當(dāng)前最佳選擇——局部最優(yōu)。每一步選擇最大硬幣，是為了把余下的數(shù)量減到最小。結(jié)果討論：針對這4種面額，貪婪法的確能給出全局最優(yōu)解?，F(xiàn)在換為3種面額：7分、5分、1分，找零錢11分。貪婪法結(jié)果：7,1,1,1,1共5個(gè)錢幣。最優(yōu)解：5,5,1共3個(gè)錢幣。因此，貪婪法不一定能得到全局最優(yōu)解。貪婪法的兩個(gè)性質(zhì)（基本要素）用貪婪法的兩個(gè)性質(zhì)判斷問題是否適用貪婪法求解貪婪選擇

4、：所求問題的全局最優(yōu)解，可通過一系列的局部最優(yōu)選擇來達(dá)到。每次選擇就得到一個(gè)局部最優(yōu)解，將所求問題化簡為規(guī)模更小的子問題。最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解中包含它的子問題最優(yōu)解。換句話說，全局最優(yōu)解是由局部最優(yōu)解組成。貪婪法與動態(tài)規(guī)劃法的區(qū)別動態(tài)規(guī)劃法，第k步所作出的選擇依賴于第k-1步內(nèi)若干個(gè)子問題解（與未來選擇有關(guān)），只有在解出k-1步所有子問題后，才能作出選擇。貪婪法僅在當(dāng)前狀態(tài)下作局部最優(yōu)選擇（與未來選擇無關(guān)）。然后，再去解作出這個(gè)選擇后產(chǎn)生的子問題。正由于這種差別，動態(tài)規(guī)劃法通常以自底向上方式求解各個(gè)子問題，而貪婪法則通常以自頂向下的方式進(jìn)行。貪婪法不能得到最優(yōu)解時(shí)，動態(tài)規(guī)劃法

5、可以得到最優(yōu)解。用前面講過的“數(shù)塔”、“多段圖”等問題來比較這兩種算法的不同。背包問題背包問題（KnapsackProblem）兩類背包問題：1.物品可以分割的背包問題。貪婪法求得最優(yōu)解。2.物品不可以分割的0-1背包問題。貪婪法不一定能求得最優(yōu)解。背包問題：承重W的背包，n個(gè)重量為w1...wn、價(jià)值v1...vn的物品。求這些物品中最有價(jià)值子集，且能裝入背包中。最優(yōu)化模型：xk(0≤xk≤1)表示物品k(k=1,...,n)放入背包的比例系數(shù)三種貪婪裝入的策略：1.價(jià)值最大：滿足約束條件下，每次裝入價(jià)值最大的物品。不一定能找到最優(yōu)解，原因是背包承重量消耗太快。2.重量最小：滿

6、足約束條件下，每次裝入重量最輕的物品。不一定能找到最優(yōu)解，原因是裝入的物品總價(jià)值增加太慢。3.單位價(jià)值最大：滿足約束條件下，每次裝入單位重量的價(jià)值最大的物品。該策略能夠找到最優(yōu)解。（價(jià)值重量比）背包問題的貪婪算法背包問題的貪婪算法//解向量初始化為0，一個(gè)都沒裝入背包//背包的當(dāng)前承重量//背包中物品總價(jià)值//單位價(jià)值降序排序，重排wv數(shù)組//n個(gè)物品循環(huán)，當(dāng)前物品為第i個(gè)//判斷當(dāng)前物品是否超重//當(dāng)前物品完整的裝入背包即xi=1//背包當(dāng)前承重量減小//當(dāng)前放入物品的價(jià)值記入總價(jià)值//當(dāng)前物品超重，放入一部分，裝滿背包問：當(dāng)前物品超重時(shí)，為什么不取后面的物品，而是取當(dāng)前物品的

7、一部分裝入背包？有限期的計(jì)算機(jī)作業(yè)調(diào)度給定n個(gè)作業(yè)j1,j2,…,jn。對于每一個(gè)作業(yè)ji，有一個(gè)與聯(lián)系的限期di>0和收益p≥0，di，pi均為整數(shù)，1≤i≤n。對于作業(yè)ji，只有在限期di內(nèi)完成，才能得到收益pi。假定只有一臺處理機(jī)為這批作業(yè)服務(wù)，處理機(jī)每次只能處理一個(gè)作業(yè)，并且完成任一作業(yè)需一個(gè)單位時(shí)間?？尚薪猓哼@批作業(yè)的一個(gè)子集J，且J中每一作業(yè)均能在限期內(nèi)完成，調(diào)度的總收益是該子集J中各作業(yè)收益的和。最優(yōu)解：具有最大收益的可行解稱為最優(yōu)解。本問題的目標(biāo)函數(shù)∑pi可以作為