全国站

热门城市 | 全国 北京 上海 广东

华北地区 | 北京 天津 河北 山西 内蒙古

东北地区 | 辽宁 吉林 黑龙江

华东地区 | 上海 江苏 浙江 安徽 福建 江西 山东

华中地区 | 河南 湖北 湖南

西南地区 | 重庆 四川 贵州 云南 西藏

西北地区 | 陕西 甘肃 青海 宁夏 新疆

华南地区 | 广东 广西 海南

资    源
  • 资    源
当前位置:查字典高考网>高中频道>信息学联赛知识>信息学联赛知识:动态规划的状态表示(三)

信息学联赛知识:动态规划的状态表示(三)

来自:查字典高考网 2009-11-12

动态规划的状态表示(三)

四、多路径问题的状态表示

动态规划是一个非常高效的算法,但是对于一些问题它并不是一个理想的算法,这里面的原因很多,最主要的原因是它的维数障碍。

下面就多路径问题来说明这点。

问题四:

存在一个数字梯形,最上层有m个数字,最底层有n个数字,每一层比上一层多一个数字,共有n-m+1层数字,如图是m=2, n=4的数字梯形。从顶到底有多条路径,每一步可沿左斜线向下或沿右斜线向下。路径所经过的数字之和称为路径得分,从顶到底的m条不相交路径的得分总和称为m条路径得分,求出最小的m路径得分。

2 3 2 3

3 4 5 3 4 5

9 1 9 1 9 1 9 1

最小的m路径得分=15

显然,这个问题与问题一极其类似。

如果m=1, 那就是问题一所要解决的问题。

如果m=2, 与问题一采取的方法类似,可以用D[x,y,z]描述两条路径到达第x层y、z两个位置的总得分。状态转移方程是

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]

当m=3时,可以采取类似m=2采用的状态表示。

在状态转移方程中,第x层的得分只取决与x-1层的得分,利用这个性质,实现时只要用两个循环数组,空间复杂度为O(nm)。

当m恒定时,空间复杂度随n呈多项式变化。当n恒定时,随着m的增大空间复杂度呈指数形式增长。

比如n=100 ,

当 m=2时,需要104 byte;

当 m=3时,需要106 byte;

当m=4时,需要108 byte;

我们看到当m=3时,基本的堆空间就不够存储了。在这个问题中,空间需要增长极为迅速,同时时间复杂度也是指数阶的。目前动态规划无法有效地处理这类问题,科学家把动态规划这样的缺点称为动态规划的维数障碍。它是两方面的,包括空间和时间, 但是在空间要求方面的障碍显得特别突出。

不论从空间上还是时间上考虑,动态规划的维数障碍是难以克服的,这就在很大程度上限制了动态规划的应用。所以,我们必须寻找其他的方法来解决这类问题。就这道题而言,网络流是一个高效的算法。我们可以用最小费用流来解决问题,流网络大致构造如下:

把数字梯形看成是有向图,对任意数字U看成两个顶点u1、u2,容量c(u1,u2)=1, 费用g(u1,u2)=U。若数字U沿对角线可到达数字V,则 c(u2,v1)=1, g(u2,v1)=0; 增加超级源s, 对于第一层数字U分成的顶点u1, c(s,u1)=1, g(s,u1)=0; 增加超级汇t,对于最底层顶点U分成的顶点u2, c(u2,t)=1,g(u2,t)=0; 其他顶点之间的容量为0。

五、总结

动态规划实现并不复杂,适用于许多问题,在解决一般问题时是我们首选的算法之一。但是,动态规划的数学模型的建立不是件容易的事,其中最困难也最重要的是状态表示。通过以上分析,我们看到:

1、动态规划的状态表示描述的子问题必须满足最优子结构性质,否则无法建立正确的动态规划模型。

2、同一问题可能存在多种正确状态表示方法,它们对应的动态规划算法的性能各不相同,从中选择高效的状态表示是动态规划优化的一个重要内容。

3、对同一状态表示而言,优化它的实现方法对改进动态规划性能很有意义。

4、在应用动态规划方法解决问题时,应先估计问题的时间、空间,如果问题存在维数障碍,那么动态规划的状态表示很难满足较大规模问题的空间要求, 我们必须另寻其他方法。

【信息学联赛知识:动态规划的状态表示(三)】相关文章:

高中数学竞赛基本知识集锦(二)

2007年高中数学联赛四川赛区初赛试题参考答案及评分标准

2007年江苏省高中数学联赛初赛试题参考答案及评分标准

高中数学联赛培训讲义(三)

2007数学考试重点:和、差、倍角的三角函数 (2)

信息学联赛知识:基本程序题集

高中数学竞赛基本知识集锦(一)

高中数学竞赛基本知识集锦(三)

信息学联赛知识:贪心策略的特点与在信息学竞赛中的应用

2005年全国高中数学联赛考点诠释(二)

[标签:竞赛联赛,梯形,五大模型,数学联赛]

网友关注

陕西省2009年成人高考成绩查询系统

2008年全国各地成人高考成绩查询:福建

天津省2009年成人高考成绩11月中上旬公布

2008年全国各地成人高考成绩查询:天津

湖北省2009年成人高考成绩查询系统

四川省2009年成人高考成绩11月初公布

上海市2009年成人高考成绩将于11月上旬公布

内蒙古2009年成人高考成绩查询系统开通

宁夏省2009年成人高考成绩11月初公布

新疆2009年成人高考成绩查询通知

江西省2009年成人高考成绩查询系统

2009年重庆成人高考成绩查询时间

贵州2009年成人高考成绩查询时间公布

山西:2009年成人高考成绩查询通知

四川绵阳2009年成人高考成绩查询通知

湖南省2009年成人高考录取信息查询方式

天津市2009年成人高考成绩查询通知

广东省2009年成人高考成绩今日10时公布

云南省2009年成人高考成绩查询系统

江苏省2009年成人高考特殊专业加试成绩查询

安徽:2009年成人高考成绩查询通知

2008年全国各地成人高考成绩查询:浙江

福建省2009年成人高考成绩11月初可网上查询

甘肃2009年成人高考成绩查询系统10月30日14时开通

江苏省2009年成人高考成绩查询时间为11月2日11时

广西省2009年成人高考成绩11月6日12时起可查询

浙江省2009年成人高考成绩查询系统

江苏2009年成人高考成绩查询

贵州省2009年成人高考成绩查询系统

2009年成人高考海南专升本成绩3月6日起可查询

网友关注视频

2019高考语文试卷解析

2019高考语文全国2卷小说阅读解析

高考政治一轮:《经济生活》第九课(社会主义市场经济)练习

加油吧考生:2019高考咨询大直播 第43集 科学填报志愿 规划精彩人生

招办面对面 第2集 中国科学技术大学

2019年高考试卷解析,数学套路不好用了

NBA流言收割机 第6集 神预测?高考数学试题暗示猛龙勇士4

他高考作文仅得6分,总分428分,被985高校录取,却被导师拒绝!

一站到底:高考语文老师上台,穿长衫说Rap,全场笑翻了!

小品:马云被宋小宝调侃当年数学高考考一分!

2019全国高考志愿填报攻略 第50集 天津市高考历史三年本科录取排名

老师好:这大概是高考前所有班主任都会干的事,取消一切副课!

最新高考数学全国2卷第12题视频解读

励志歌曲《阳光总在风雨后》送给高考的莘莘学子,祝金榜题名!

初二辍学,3次高考落榜,如今却成为最成功的音乐人之一

创艺第二届:2019届高考录取表彰大会暨“核桃音乐节”合影——你只管努力,剩下的交给创艺

高考帮:这!就是专业 第8集 安徽师范大学

探秘历史 第二季 第479集 河南叛逆高考生,写下8000字批判作文,现状如何?

招办面对面 第76集 阜阳师范学院信息工程学院

高考英语作文分析2

张雪峰高考志愿填报指南 第28集 高考志愿分析,材料科学与工程专业,就业很一般,建议慎重选择

这!就是专业 第43集 河北经贸大学—计算机科学与技术专业

amc传媒音乐影像 第一季 第598集 西安原创乐队走进英泰青卓 用音乐助力高考学子

看懂图片,你也会做高考地理题,解析2019年高考文综地理4

这四首励志歌曲,送给为梦起航的高考学子们,听完心潮澎湃!

一边扔试卷一边玩摇滚?这个学校的高考减压方式,真是帅到没朋友

张雪峰高考志愿填报指南 第47集 高考志愿,令人头疼的数学系,才是专业万金油,毕业后机会多

视频|2019全国高考今日开考: 语文特级教师评析上海卷高考作文

视频|上海高考作文: 寻找“中国味” 专家

2019高考·语文试题有亮点 凸显时代主题 厚植家国情怀