全國(guó)

        熱門(mén)城市 | 全國(guó) 北京 上海 廣東

        華北地區(qū) | 北京 天津 河北 山西 內(nèi)蒙古

        東北地區(qū) | 遼寧 吉林 黑龍江

        華東地區(qū) | 上海 江蘇 浙江 安徽 福建 江西 山東

        華中地區(qū) | 河南 湖北 湖南

        西南地區(qū) | 重慶 四川 貴州 云南 西藏

        西北地區(qū) | 陜西 甘肅 青海 寧夏 新疆

        華南地區(qū) | 廣東 廣西 海南

        • 微 信
          高考

          關(guān)注高考網(wǎng)公眾號(hào)

          (www_gaokao_com)
          了解更多高考資訊

        首頁(yè) > 高中頻道 > 信息學(xué)聯(lián)賽知識(shí) > 信息學(xué)聯(lián)賽知識(shí):動(dòng)態(tài)規(guī)劃的狀態(tài)表示(三)

        信息學(xué)聯(lián)賽知識(shí):動(dòng)態(tài)規(guī)劃的狀態(tài)表示(三)

        2009-11-12 23:01:29網(wǎng)絡(luò)

          動(dòng)態(tài)規(guī)劃的狀態(tài)表示(三)

          四、多路徑問(wèn)題的狀態(tài)表示

          動(dòng)態(tài)規(guī)劃是一個(gè)非常高效的算法,但是對(duì)于一些問(wèn)題它并不是一個(gè)理想的算法,這里面的原因很多,最主要的原因是它的維數(shù)障礙。

          下面就多路徑問(wèn)題來(lái)說(shuō)明這點(diǎn)。

          問(wèn)題四:

          存在一個(gè)數(shù)字梯形,最上層有m個(gè)數(shù)字,最底層有n個(gè)數(shù)字,每一層比上一層多一個(gè)數(shù)字,共有n-m+1層數(shù)字,如圖是m=2, n=4的數(shù)字梯形。從頂?shù)降子卸鄺l路徑,每一步可沿左斜線向下或沿右斜線向下。路徑所經(jīng)過(guò)的數(shù)字之和稱(chēng)為路徑得分,從頂?shù)降椎膍條不相交路徑的得分總和稱(chēng)為m條路徑得分,求出最小的m路徑得分。

          2 3 2 3

          3 4 5 3 4 5

          9 1 9 1 9 1 9 1

          最小的m路徑得分=15

          顯然,這個(gè)問(wèn)題與問(wèn)題一極其類(lèi)似。

          如果m=1, 那就是問(wèn)題一所要解決的問(wèn)題。

          如果m=2, 與問(wèn)題一采取的方法類(lèi)似,可以用D[x,y,z]描述兩條路徑到達(dá)第x層y、z兩個(gè)位置的總得分。狀態(tài)轉(zhuǎn)移方程是

          D[x,y,z] = Max{D[x-1,y,z],D[x-1,y,z-1],D[x-1,y-1,z],D[x-1,y-1,z-1]}

          +A[x,y]+A[x,z],

          D[1,y,z] = A[1,y]+A[1,z]

          當(dāng)m>=3時(shí),可以采取類(lèi)似m=2采用的狀態(tài)表示。

          在狀態(tài)轉(zhuǎn)移方程中,第x層的得分只取決與x-1層的得分,利用這個(gè)性質(zhì),實(shí)現(xiàn)時(shí)只要用兩個(gè)循環(huán)數(shù)組,空間復(fù)雜度為O(nm)。

          當(dāng)m恒定時(shí),空間復(fù)雜度隨n呈多項(xiàng)式變化。當(dāng)n恒定時(shí),隨著m的增大空間復(fù)雜度呈指數(shù)形式增長(zhǎng)。

          比如n=100 ,

          當(dāng) m=2時(shí),需要104 byte;

          當(dāng) m=3時(shí),需要106 byte;

          當(dāng)m=4時(shí),需要108 byte;

          我們看到當(dāng)m=3時(shí),基本的堆空間就不夠存儲(chǔ)了。在這個(gè)問(wèn)題中,空間需要增長(zhǎng)極為迅速,同時(shí)時(shí)間復(fù)雜度也是指數(shù)階的。目前動(dòng)態(tài)規(guī)劃無(wú)法有效地處理這類(lèi)問(wèn)題,科學(xué)家把動(dòng)態(tài)規(guī)劃這樣的缺點(diǎn)稱(chēng)為動(dòng)態(tài)規(guī)劃的維數(shù)障礙。它是兩方面的,包括空間和時(shí)間, 但是在空間要求方面的障礙顯得特別突出。

          不論從空間上還是時(shí)間上考慮,動(dòng)態(tài)規(guī)劃的維數(shù)障礙是難以克服的,這就在很大程度上限制了動(dòng)態(tài)規(guī)劃的應(yīng)用。所以,我們必須尋找其他的方法來(lái)解決這類(lèi)問(wèn)題。就這道題而言,網(wǎng)絡(luò)流是一個(gè)高效的算法。我們可以用最小費(fèi)用流來(lái)解決問(wèn)題,流網(wǎng)絡(luò)大致構(gòu)造如下:

          把數(shù)字梯形看成是有向圖,對(duì)任意數(shù)字U看成兩個(gè)頂點(diǎn)u1、u2,容量c(u1,u2)=1, 費(fèi)用g(u1,u2)=U。若數(shù)字U沿對(duì)角線可到達(dá)數(shù)字V,則 c(u2,v1)=1, g(u2,v1)=0; 增加超級(jí)源s, 對(duì)于第一層數(shù)字U分成的頂點(diǎn)u1, c(s,u1)=1, g(s,u1)=0; 增加超級(jí)匯t,對(duì)于最底層頂點(diǎn)U分成的頂點(diǎn)u2, c(u2,t)=1,g(u2,t)=0; 其他頂點(diǎn)之間的容量為0。

          五、總結(jié)

          動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)并不復(fù)雜,適用于許多問(wèn)題,在解決一般問(wèn)題時(shí)是我們首選的算法之一。但是,動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型的建立不是件容易的事,其中最困難也最重要的是狀態(tài)表示。通過(guò)以上分析,我們看到:

          1、動(dòng)態(tài)規(guī)劃的狀態(tài)表示描述的子問(wèn)題必須滿(mǎn)足最優(yōu)子結(jié)構(gòu)性質(zhì),否則無(wú)法建立正確的動(dòng)態(tài)規(guī)劃模型。

          2、同一問(wèn)題可能存在多種正確狀態(tài)表示方法,它們對(duì)應(yīng)的動(dòng)態(tài)規(guī)劃算法的性能各不相同,從中選擇高效的狀態(tài)表示是動(dòng)態(tài)規(guī)劃優(yōu)化的一個(gè)重要內(nèi)容。

          3、對(duì)同一狀態(tài)表示而言,優(yōu)化它的實(shí)現(xiàn)方法對(duì)改進(jìn)動(dòng)態(tài)規(guī)劃性能很有意義。

          4、在應(yīng)用動(dòng)態(tài)規(guī)劃方法解決問(wèn)題時(shí),應(yīng)先估計(jì)問(wèn)題的時(shí)間、空間,如果問(wèn)題存在維數(shù)障礙,那么動(dòng)態(tài)規(guī)劃的狀態(tài)表示很難滿(mǎn)足較大規(guī)模問(wèn)題的空間要求, 我們必須另尋其他方法。

         

        [標(biāo)簽:競(jìng)賽聯(lián)賽 梯形 五大模型 數(shù)學(xué)聯(lián)賽]

        分享:

        高考院校庫(kù)(挑大學(xué)·選專(zhuān)業(yè),一步到位!)

        高考院校庫(kù)(挑大學(xué)·選專(zhuān)業(yè),一步到位!)

        高校分?jǐn)?shù)線

        專(zhuān)業(yè)分?jǐn)?shù)線

        日期查詢(xún)
        • 歡迎掃描二維碼
          關(guān)注高考網(wǎng)微信
          ID:gaokao_com

        • 👇掃描免費(fèi)領(lǐng)
          近十年高考真題匯總
          備考、選科和專(zhuān)業(yè)解讀
          關(guān)注高考網(wǎng)官方服務(wù)號(hào)


        主站蜘蛛池模板: 久久精品夜色国产亚洲av| 动漫乱理伦片在线观看| 9自拍视频在线观看| 日本精品啪啪一区二区三区| 亚洲精品无码专区在线| 色噜噜狠狠色综合欧洲| 国产真实乱子伦精品视手机观看| japmassage日本按摩| 日本免费xxxx| 亚洲午夜久久久影院伊人| 男女一进一出无遮挡黄| 无码丰满少妇2在线观看| 亚洲日韩aⅴ在线视频| 精品国产一区二区三区免费| 国产在线精品国自产拍影院同性| 91大神在线看| 女人让男人直接桶| 久久99精品国产免费观看| 极品美女一级毛片免费| 亚洲精品你懂的| 精品人人妻人人澡人人爽人人| 国产区在线视频| bbw巨大丰满xxxx| 在线毛片免费观看| 一级毛片60分钟在线播放久草高清在线 | 精品99在线观看| 国产乱妇无码大片在线观看| 中文字幕天天干| 国语自产偷拍精品视频偷蜜芽| 东北美女野外bbwbbw免费| 日本漫画yy漫画在线观看| 亚洲一区二区三区在线观看网站| 波多野结衣全部作品电影| 免费看美女让人桶尿口| 老扒系列40部分阅读| 国产在视频线在精品| 思99热精品久久只有精品| 日本三浦理惠子中文字幕| 亚洲人成中文字幕在线观看| 波多野结衣一区二区三区高清av| 十九岁日本电影免费完整版观看|