技術(shù)參考貪心策略ppt課件(已改無(wú)錯(cuò)字)
2023-06-12 08:29:00 本頁(yè)面
【正文】 ｂ、ｃ、ｄ、ｅ）， 共有３條巴士線（線路Ａ：ａ → ｄ；線路Ｂ：ａ → ｂ → ｃ → ｅ；線路Ｃ：ｄ → ｅ）。此時(shí)要使換車次數(shù)最少，應(yīng)乘坐線路Ｂ的巴士，路線為：ａ → ｂ → ｃ → ｅ，換車次數(shù)為０；要使途經(jīng)車站數(shù)最少，乘坐線路應(yīng)為ａ → ｄ → ｅ，換車次數(shù)為１。所以說(shuō)使換車次數(shù)最少的路線和使途經(jīng)車站數(shù)最少的方案不一定相同。這使不能用搜索發(fā)求解此問(wèn)題的原因之一。 原因之二，來(lái)自對(duì)數(shù)學(xué)模型的分析。我們根據(jù)題中所給數(shù)據(jù)來(lái)建立一個(gè)圖后會(huì)發(fā)現(xiàn)該圖中存在大量的環(huán)，因而不適合用搜索法求解。 題目分析到這里，我們可以發(fā)現(xiàn)此題與 NOI93的求最長(zhǎng)路徑問(wèn)題有相似之處。其實(shí)，此題完全可以套用上文所提到的 Dijkstra算法來(lái)求解。 以上三道題只是使用了單一的貪心策略來(lái)求解的。而從近幾年的信息學(xué)奧林匹克競(jìng)賽的命題方向上看，題目更加靈活，同時(shí)測(cè)試數(shù)據(jù)較大，規(guī)定的出解時(shí)間較短。在一些問(wèn)題中，我們采用貪心策略對(duì)問(wèn)題化簡(jiǎn)，從而使程序具有更高的效率。 試題描述 某旅游區(qū)的街道成網(wǎng)格狀（見圖），其中東西向的街道都是旅游街，南北向的街道都是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道。游客在旅游街上只能從西向東走，在林蔭道上既可以由南向北走，也可以從北向南走。 阿隆想到這個(gè)旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示所有旅游街相鄰兩個(gè)路口之間的道路值得瀏覽得程度，分值從 １００到１００的整數(shù)，所有林蔭道不打分。所有分值不可能全是負(fù)值 例如下圖是被打過(guò)分的某旅游區(qū)的街道圖： 阿隆可以從任一路口開始瀏覽，在任一路口結(jié)束瀏覽。請(qǐng)你寫一個(gè)程序，幫助阿隆尋找一條最佳的瀏覽路線，使得這條路線的所有分值總和最大。 試題背景 這道題同樣出自ＮＯＩ９７，＇９７國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的第二題（吉爾的又一個(gè)騎車問(wèn)題）與本題是屬于本質(zhì)相同的題目。 試題分析 由于林蔭道不打分，也就是說(shuō)，無(wú)論游客在林蔭道中怎么走，都不會(huì)影響得分。因題可知，若游客需經(jīng)過(guò)某一列的旅游街，則他一定要經(jīng)過(guò)這一列的Ｍ條旅游街中分值最大的一條，才會(huì)使他所經(jīng)路線的總分值最大。這是一種貪心策略。貪心策略的目的是降維，使題目所給出的一個(gè)矩陣便為一個(gè)數(shù)列。下一步便是如何對(duì)這個(gè)數(shù)列進(jìn)行處理。在這一步，很多人用動(dòng)態(tài)規(guī)劃法求解，這種算法的時(shí)間復(fù)雜度為Ｏ（ｎ 2），當(dāng)林蔭道較多時(shí)，效率明顯下降。其實(shí)在這一步我們同樣可以采用貪心法求解。這時(shí)的時(shí)間復(fù)雜度為Ｏ（ｎ）。 貪心策略在求 P類較優(yōu)解問(wèn)題中的應(yīng)用 正如其他學(xué)科奧林匹克競(jìng)賽一樣，國(guó)際信息學(xué)奧賽的發(fā)展同樣經(jīng)歷了一個(gè)逐步成熟的發(fā)展過(guò)程?；仡櫴嗄曩愂碌陌l(fā)展，我們不妨將國(guó)際信息學(xué)奧賽的發(fā)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1