《技術(shù)參考貪心策略》ppt課件-全文預(yù)覽
【正文】 。 試題背景 這道題同樣出自ＮＯＩ９７，＇９７國際大學(xué)生程序設(shè)計競賽的第二題（吉爾的又一個騎車問題）與本題是屬于本質(zhì)相同的題目。 阿隆想到這個旅游區(qū)游玩。在一些問題中，我們采用貪心策略對問題化簡，從而使程序具有更高的效率。 題目分析到這里，我們可以發(fā)現(xiàn)此題與 NOI93的求最長路徑問題有相似之處。所以說使換車次數(shù)最少的路線和使途經(jīng)車站數(shù)最少的方案不一定相同。 試題背景 出自ＮＯＩ９７ 試題分析 此題看上去很像一道搜索問題。聽人說，從ＣＵＰ飯店到Ｓ公園可能有也可能沒有直通巴士。 ［例３］最優(yōu)乘車問題 試題描述 Ｈ城是一個旅游勝地，每年都有成千上萬的人前來觀光．為方便游客，巴士公司在各個旅游景點及賓館、飯店等地都設(shè)置了巴士站，并開通了一些單向巴士線路。 討論：假設(shè)經(jīng)（Ｎ－ 3）次變換后得到３個數(shù)：a,b,max＇（ max＇ ≥ａ ≥ｂ），其中 max＇是（Ｎ－２）個數(shù)經(jīng)（Ｎ－３）次ｆ變換后所得的最大值，此時有兩種求值方式，設(shè)其所求值分別為， ，則有： ＝（ａ ｂ＋１） max＇＋１， ＝（ａ max＇＋１） ｂ+１ 所以 － ＝ max＇－ｂ ≥０若經(jīng)（Ｎ－２）次變換后所得的３個數(shù)為：ｍ，ａ，ｂ（ｍ ≥ａ ≥ｂ）且ｍ不為（Ｎ－２）次變換后的最大值，即ｍ＜ max＇則此時所求得的最大值為： ＝（ａ ｂ +１） ｍ +１ 此時 － ＝（１ +ａｂ）（ max＇－ｍ）＞０ 所以此時不為最優(yōu)解。 試題背景 這是 1997年福建隊選拔賽的一道題目。其實，大家通過對此題得深入分析便知：本題所給出的高精度正整數(shù)在具體做題時將它看作由若干個數(shù)字所組成的一串?dāng)?shù)，這是求解本題的一個重要突破。 [例 1]刪數(shù)問題 試題描述 鍵盤輸入一個高精度的正整數(shù) N，去掉其中任意 S個數(shù)字后剩下的數(shù)字按左右次序組成一個新的正整數(shù)。下面我們著重分析貪心策略在求解 P類問題中的應(yīng)用。諸如 Kruskal、 Prim、 Dijkstra等體現(xiàn) 貪心 思想的圖形算法更是廣泛地應(yīng)用于樹與圖的處理。 適宜于用貪心策略來求解的許多問題都可以歸結(jié)為在加權(quán)矩陣胚中找一個具有最大權(quán)值的獨立子集的問題，即給定一個加權(quán)矩陣胚， M=（ S， I），若能找出一個獨立且具有最大可能權(quán)值的子集 A，且 A不被 M中比它更大的獨立子集所包含，那么 A為最優(yōu)子集，也是一個最大的獨立子集。 矩陣胚 理論是一種能夠確定貪心策略何時能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問題時發(fā)揮著越來越重要的作用。在此，我們對兩種解題策略進行比較。 局部最優(yōu)解：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1