手机

全国站

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

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

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

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

华中地区 | 河南 湖北 湖南

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

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

华南地区 | 广东 广西 海南

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

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

来自:查字典高考网 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、在应用动态规划方法解决问题时,应先估计问题的时间、空间,如果问题存在维数障碍,那么动态规划的状态表示很难满足较大规模问题的空间要求, 我们必须另寻其他方法。

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

网友关注视频

2019 广西:帅气学霸高考730分 数学英语满分!

凤凰县高级中学高考试卷分析专题教研会

高考同学看过来,难度系数三颗星的奥数1

外国数学老师挑战中国高考题,一顿“凶猛操作”下来,被虐惨!

2019高考数学第四题技巧秒出答案

学渣男高考英语全写B,老师给老爸说成绩,老爸直接听懵了!

这!就是专业 第20集 长沙理工大学—数据科学专业

高职高考数学公式

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

这!就是专业 第1集 川农动物科学专业解读

高考作文:全国2卷 材料作文破题分析 2019高考助力

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

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

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

这!就是专业 第47集 江苏理工学院

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

张雪峰高考志愿填报指南 第15集 高考填报志愿,想学电子信息类专业,推荐报这六所高校,不出错

高中信息技术

【高考英语】七选五解析,不算太难

2019高考语文试卷解析

高考英语作文分析2

这!就是专业 第15集 中国矿业大学——数学专业

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

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

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

北京新闻 2019 5.9万余北京考生今日高考 语文试题鼓励创造性阅读与表达

高考阅卷名师给考生的高考作文密训课 第5集 高考作文审题实操方法精讲(三)

你高考成绩高吗?这道题目怎能成立?高难度奥数,能不能把你难住

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

这!就是专业 第31集 阜阳师范学院信息工程学院