蠻力貪婪法數(shù)據(jù)結構與算法pptx

DataStructuresandAlgorithms主講教師:黃襄念西華大學數(shù)學與計算機學院圖像處理與模式識別實驗室課程QQ群：101600501數(shù)據(jù)結構與算法本章授課內(nèi)容蠻力法：算法設計思想蠻力法：選擇排序蠻力法：窮舉查找蠻力法：0-1背包問題貪婪法：算法設計思想貪婪法：Prim算法貪婪法：Kruskal算法貪婪法：Dijkstra算法貪婪法：連續(xù)背包問題本章授課學時：3學時07:122／28問題求解框架實際問題數(shù)學模型求解算法數(shù)據(jù)組織程序?qū)崿F(xiàn)程序測試數(shù)學描述算法設計程序設計數(shù)據(jù)結構設計07:123／28蠻力法〔BruteForceAlgorithm〕蠻力法：直接基于問題本身描述的算法設計方法解決問題沒有或不用技巧〔簡單、直接〕簡例a和非負整數(shù)n，計算an的蠻力算法：

典型算法：各種窮舉法優(yōu)缺點優(yōu)點：算法設計簡單，易于設計缺點：算法的時間效率一般不高蠻力法：算法設計思想07:124／28蠻力法應用——一種重要的算法設計方法解決各種問題的一般方法常用于一些很根本又重要的算法——計算n個數(shù)的和——求數(shù)據(jù)集的最大元素，……可作為尺度，衡量同樣問題的其他算法的效率對于規(guī)模不大的問題〔蠻力法的速度可以接受時〕蠻力法是一種很好的解決方案！設計高效算法的代價很可能是不值得的：①算法可讀性變差，算法實現(xiàn)的復雜性增加軟件工程：不利于軟件的開發(fā)、測試、維護②時間效率得不到顯著的表達蠻力法：應用07:125／28排序問題中的蠻力法冒泡排序、選擇排序查找問題中的蠻力法順序查找、字符串匹配〔樸素的〕組合問題中的蠻力法窮舉查找：子集和問題、0-1背包問題圖問題中的蠻力法窮舉查找：哈密頓回路問題窮舉查找：貨郎擔〔旅行商，TSP，郵遞員〕問題計算幾何問題中的蠻力法窮舉查找：最近對問題、凸包問題蠻力法：應用例07:126／28排序算法設計舉例：對線性表(89,45,68,90,29,34,17)排為升序思考：什么是排序問題？最直接的排序方法？蠻力法：按從小到大順序挑出各個元素排列好蠻力法：選擇排序07:127／28組合問題的查找前述查找：給定集合中查找滿足條件的一個元素(key)組合問題的查找：給定集合中查找滿足條件的子集例：子集和問題在給定的整數(shù)集合中，查找滿足如下條件的子集：元素和=某個給定的整數(shù)〔約束條件〕應用例：食堂就餐〔50元錢能買多少食品，不找零〕窮舉查找設計生成算法，生成全部子集〔個數(shù)：〕對所有子集一一判定是否滿足約束條件：滿足的子集：解〔可行解〕不滿足的子集：不可行解蠻力法：窮舉查找2n冪集07:128／28背包問題〔KnapsackProblem〕：n個物品，重量(w1,...,wn),價值(v1,...,vn),一個承重量為W的背包求解：能夠放入背包(可行)、最有價值的子集(最優(yōu))連續(xù)背包物品可以按任意比例切分，比例系數(shù)(0.0~1.0)離散背包〔0-1背包〕物品不能切分。0：不放入，1：放入0-1背包的蠻力法(窮舉查找)生成n個物品集合的全部子集〔所有組合〕計算每個子集的重量(≤W)，計算可行解的價值最優(yōu)解：可行解中價值最大者蠻力法：0-1背包問題07:129／28貪婪法／貪心法〔GreedyAlgorithm〕常用于解決最優(yōu)化問題貪婪法：算法設計思想全局最優(yōu)解由一系列的局部最優(yōu)解構成下山：一步一步走迭代法，非直接法最速下山法從始點出發(fā)，根據(jù)當前局部最優(yōu)決策，使目標函數(shù)f(X)→min最快f(x1,x2)變化最快方向？——梯度方向(+,-)正梯度：函數(shù)值增大負梯度：函數(shù)值減小07:1210／28每一步的決策是可行解〔滿足約束條件〕局部最優(yōu)〔貪婪〕不可逆轉(zhuǎn)〔后續(xù)步驟不能改變它〕優(yōu)缺點優(yōu)點：算法較簡單，時空效率較高缺點：存在視界局限〔局部最優(yōu)不一定是全局最優(yōu)〕，對某些優(yōu)化問題，不能獲得最優(yōu)解！貪婪法：貪婪策略與特點負梯度只是局部最好方向，相鄰兩次迭代的方向垂直，整個搜索軌跡呈現(xiàn)鋸齒形！假設函數(shù)性態(tài)很壞，震蕩現(xiàn)象嚴重，甚至計算不收斂。07:1211／28生成樹(SpanningTree,ST)包含連通圖全部頂點的一個連通無環(huán)子圖(邊數(shù)=n-1)最小生成樹(MinimumSpanningTree,MST)帶權連通圖所有生成樹中，權重之和最小的那一棵貪婪法：Prim算法1324132413241324ADCB1235ADCB123ADCB135ADCB125

w(T1)=6

w(T2)=9

w(T3)=807:1212／28普利姆(Prim)算法策略：初始子樹開始，逐步擴展子樹，直到生成MST算法：初始子樹任選一個頂點v0子樹擴展〔貪婪〕參加頂點：不在樹中、到樹的距離最近的一個頂點頂點到樹的距離：到樹中所有頂點的最短距離算法停止全部頂點都已參加樹中〔形成一棵樹〕說明：MST不唯一，但權之重和相同算法過程圖：下頁貪婪法：Prim最小生成樹算法07:1213／28貪婪法：Prim算法過程圖為何參加頂點時，只考慮邊緣點？每個邊緣點到子樹的最短距離是？參加子樹中的頂點是哪一個？子樹邊緣點邊緣點邊緣點邊緣點？12457324507:1214／28MST應用例右圖：6個社區(qū)A~F權值：已測繪的距離任務：修建道路連通6個社區(qū)要求：造價本錢最低問題分析：連通性與本錢最低要求①連通無環(huán)圖(樹)；②總里程最短(MST)問題求解：選用Prim算法頂點集分2個子集：樹中頂點集、候選頂點集頂點增加2個屬性：樹中最近鄰接點名稱、邊長(權)例如：子樹頂點集{A,B},F(B,4),D(-,∞)貪婪法：Prim算法例BCFAED帶權圖G07:1215／28算法過程圖例Prim算法例

樹中頂點集候選頂點集BCFAED初始樹BCFAED07:1216／28Prim算法例

樹中頂點集候選頂點集BCFAEDBCFAEDBCFAEDMST不唯一時間效率O(n2),與邊數(shù)無關適合于稠密圖07:1217／28Kruskal算法(克魯斯卡爾,避環(huán)法)策略：初始森林開始，逐步合并森林，直到生成MSTKruskal算法//網(wǎng)G=<V,E,W>{G的邊集E排序：權值小→大初始森林：MST的邊集ET=Φwhile(|ET|<=n-1)//MST有多少邊？{從E取下一條邊{u,v};E=E-{u,v};if({u,v}與ET中邊不構成回路)ET=ET∪{u,v};//{u,v}參加MST}}貪婪法：Kruskal最小生成樹算法如何判斷參加邊是否構成回路？BCFAED判斷u,v是否屬于同一棵樹(極小連通子圖)O(eloge),e邊數(shù)07:1218／28貪婪法：Kruskal算法過程圖BCFAED

樹中邊集ET

有序候選邊集EBC,EF,AB,BF,CF1

2344AF,DF,AE,CD,DE55668ΦBCFAEDBC,

EF,AB,BF,CF

1

2344AF,DF,AE,CD,DE5566

8BCBCFAEDBC,EFBC,

EF,

AB,BF,CF

1

2

344AF,DF,AE,CD,DE5566

807:1219／28貪婪法：Kruskal算法過程圖BCFAED

樹中邊集ET

有序候選邊集EBC,EF,AB,

BF,CF

123

44AF,DF,AE,CD,DE55668BC,EF,ABBCFAEDBC,EF,AB,BF,CF

12344AF,DF,AE,CD,DE5566

8BCFAEDBC,EF,AB,BF,CF

12344AF,DF,AE,CD,DE5566

8BC,EF,AB,BFBC,EF,AB,BF,DF不唯一07:1220／28單源最短路徑問題給定加權連通圖，求一個源點到其余頂點的最短路徑與MST區(qū)別——整棵樹權值和最小〔不要求任意兩頂點最近〕與完全最短路徑問題區(qū)別〔Floyd算法〕——每個頂點到其余頂點的最短路徑與貨郎擔〔旅行商〕問題區(qū)別——經(jīng)過帶權連通圖全部頂點僅一次的最短回路貪婪法：Dijkstra算法ADCB1234ADCB123ADCB124帶權圖MST單源最短路徑樹07:1221／28解單源最短路徑問題——Dijkstra算法貪婪法：Dijkstra算法子樹邊緣點邊緣點非邊緣點124584225Dijkstra與Prim很類似Dijkstra：到起點v0

距離最近Prim：到子樹距離最近07:1222／28背包問題的數(shù)學模型〔優(yōu)化模型〕貪婪法：連續(xù)背包問題目標函數(shù)約束條件n

個物品：重量:

(w1,...,wn)

價值:(v1,...,vn)背包承重量:W物品k

放入背包的比例系數(shù):xk0-1背包連續(xù)背包三種貪婪策略價值貪婪重量貪婪價值／重量貪婪能找到最優(yōu)解嗎？07:1223／28貪婪法：連續(xù)背包問題解法//解向量(空背包)//背包的當前承重量//背包中物品總價值//排序(降序)：價值/重量//n個物品循環(huán)//未超重//整個裝入背包：xi=1//背包當前承重量減小//物品價值記入總價值//物品超重：放入一局部07:1224／28設計蠻力算法：判斷一個鄰接矩陣表示的連通圖是否具有歐拉回路。該算法的效率類型如何？完備子圖問題：給定一個圖G和正整數(shù)k，確定該圖是否包含一個大小為k的完備子圖即具有k個頂點的完全子圖。請為該問題設計一個窮舉查找算法。貪婪法求連續(xù)背包問題最優(yōu)解：n=7,W=15,

(w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1)(v1,v2,v3,v4,v5,v6,v7)=(10,5,15,7,6,18,3)應用Prim算法之前，是否需要檢查圖的連通性？該算法本身能完成這種檢查？如何應用Prim算法求不帶權的連通圖的生成樹？