手机

全国站

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

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

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

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

华中地区 | 河南 湖北 湖南

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

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

华南地区 | 广东 广西 海南

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

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

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

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

三、状态表示对动态规划性能的影响

我们分析问题的时候,总是从不同的角度去思考,以便能全面、本质地认识问题。分析问题的状态表示,我们也是尽可能从不同角度去思考。由此会得到对问题的不同状态表示,从动态规划原理来看,其中有些状态表示不能合乎要求,而在满足要求的那些状态表示中,我们可以以之为基础,构造动态规划模型,实现动态规划算法。在通常情况下,基于不同的状态表示的动态规划算法性能存在着差异,这主要从算法的时间复杂度和空间复杂度体现出来。

上面介绍了问题二的两种状态表示, 状态表示2-1从问题的自然特征来思考, 提出对一般多边形的表示方法,具有其通用性,状态表示2-2则根据多边形划分中关于顶点划分的性质来思考,进而提出了半连续多边形, 现在我们考虑关于多边形边的划分性质,提出状态表示2-3, 并比较三种状态表示,探讨状态表示对动态规划性能的影响。

状态表示2-3

定义2-3 多边形(A1,A2,,Ak)是由多边形(1,2,,N)划分而来的多边形,我们称多边形(A1,A2,,Ak)为连续多边形,当且仅当Ai+1 = Ai+1 ,

k0。图6中多边形(3,4,5,6,7)就是一个连续多边形。

性质2-3 对于一个多边形,它的任一条边一定与另一个顶点组成三角形。如图5,边(1,2)可以与顶点4等顶点相连,形成三角形。

根据性质2-3, 对多边形划分时,我们可以按需要选择边来与其他顶点相连,而不会遗漏多边形的任一种划分,自然也不会遗漏多边形的最优划分。

连续多边形(X,X+1,,,Y)可以用二元组(X,Y)来表示,则D(X,Y)表示连续多边形的划分区域数。

对于连续多边形(X,Y),只要我们选择边(X,Y)与顶点Z(XY)连接,那么(X,Y)划分为三部分:连续多边形(X,Z)、连续多边形(Z,Y)和三角形(X,Z,Y)。(X,Y)的最优划分包含了(X,Z)、(Z,Y)的最优划分,满足最优子结构性质。

注意到初始多边形是一个连续多边形,根据数学归纳法,它的子问题都是连续多边形。因此二元组(X,Y)是一个正确的状态表示。状态转移方程为

D(X,Y) = min(g(X,Y,Z) + D(X,Z)+D(Z,Y)), XY,

f(i,i) = 0, n+10,

当x,y,z在一条直线时,g(x,y,z) = 0, 否则g(x,y,z) = 1。

子问题空间复杂度是O(n2),在本文的假设条件下,使用基本堆空间可以处理顶点数700以内的多边形。下面是求连续多边形最优划分区域数的函数。

[算法2-3]:

function Dynamic(s, t : integer) : integer; {求连续多边形(s,t)的最优划分}

var j, tot : integer;

begin

if D[s, t][1] = 255 then

if t - s = 1 then D[s, t][1] := 0

else

begin

for j := s + 1 to t - 1 do {j 是边(s,t)要连接的顶点}

if 顶点j与顶点s、t连接合法 then

begin

Tot := Dynamic(s, j) + Dynamic(j, t); {子多边形的最优划分}

If 顶点s、t、j不在一条直线上 then Tot := Tot + 1;

if Tot D[s, t][1] then

begin

D[s, t][1] := Tot;

D[s, t][2] := j;

end;

end;

end;

Dynamic := D[s, t][1];

end;

图7

我们来比较三种状态表示描述的子问题空间以及相应动态规划算法的时空性能。在图7中,动态规划的时间复杂度、空间复杂度与子问题空间增长是同阶的。事实上,这样的关系不仅仅局限于这个例子,它具有普遍意义。首先,动态规划空间花费主要是用来存储描述子问题的状态表示,因此空间复杂度自然随着子问题的增多而增大。其次,动态规划的时间花费主要取决于要解决的不同子问题的数目,随着子问题数目的增多,时间复杂度当然就增大了。

既然不同的状态表示会描述不同大小的子问题空间,那么原因何在呢?在这道题中,我们仅仅从多边形的定义来看,有这样的关系:{连续多边形} 是{半连续多边形}的子集,{半连续多边形}是{多边形}的子集。由此可知,应该是状态表示描述子问题不精确造成。

回顾状态表示2-1和状态表示2-2、2-3的分析,我们之所以采取状态表示2-1 是基于对多边形自然特征的认识,而没有考虑到在特定环境下多边形划分而成的子多边形与多边形本身有特殊的联系。比较状态表示2-2、2-3,两者都利用了多边形划分的性质,但显然研究的深度不同。状态表示2-3保证了每种划分都是对多边形的不同划分,因为至少有一条边所在的三角形是与其他划分中所在的三角形不一样。状态2-2就不能保证这一点,如下图所示的两种划分顺序得出了同一种划分。因为这种无意义的划分而产生的多边形属于{半连续多边形}-{连续多边形},如半连续多边形(1,3,5)。

状态表示的改进不仅仅使动态规划的性能提高,通常也会使算法实现更加简洁。比较算法[2-2]、[2-3]我们就可以看出这一点。算法[2-3]的程序见附录。

以上,我们主要讨论状态表示描述的子问题空间不同而影响动态规划。这是状态表示影响动态规划性能的主要原因,但是在算法实现过程中,由于某种原因我们可能对同一子问题采取了不同的描述方法,存储空间会产生极大的差异。下面这个例子说明了这个问题。

问题三: #这个操作符被定义为一个双目运算符,且两个运算对象为正整数,对于整数X,Y,# 号运算定义为(X#Y)=十进制数X各数字之和*十进制数Y的最大数字+十进制数Y的最小数字。例

(9#30)=9*3+0=27,(30#9)=3*9+9=36

对于表达式我们约定或是一正数或是(表达式#表达式)。以下表达式是合法的表达式

a

(a#a)

((a#a)#a)

(a#(a#a)#(a#a)#a))

对于给定的十进制正数a和表达式的值K,计算具有K值的表达式中#的个数。具有k值的表达式可能有许多,并且具有不同的#个数,只需输出最小个数。a,k是均不大于1000000000的正整数。

运算时,我们描述的是正整数k的各位数字和、最大数字和最小数字两个信息(这里把最大、最小数字看成一个信息)以及得到k所用的最少 # 数,那么可以有两种状态表示。

状态表示3-1

我们用一元组(k)表示正数k, D(k)表示所用的#数目。(k)已经隐含了各数字和、最大数字和最小数字两个信息。

状态表示3-2

因为对每个数而言,各位数字和与最大数字、最小数字两个信息具有独立性,我们可以分别记录这两个信息。用一元组(X)表示各位数字和,用二元组(Y,Z)表示最大数字、最小数字。

我们对输入的数a进行特殊处理,而一次运算后的最大数字不超过738,状态表示3-1只要开一个数组,定义如下

Type NumBerType = array[1..738] of integer

因为一次运算后的数值最大是三位数,各位数值和不超过27,用来存储数值和的数组可定义为

Type TotalType = array[1..27] of integer

最大数字、最小数字与数大小无关,它们范围在[0,9],定义为

Type MaxMinType = array[0..9,0..9] of integer

状态表示3-1用一元组同时记录了两个信息,而状态表示3-2则分别记录了这两个信息。显然状态表示3-2所用的空间比状态表示3-1所用的要小的多。同样一个对象,只是由于我们采取不同的描述方法,所用的空间大小就迥然不同。程序见附录。

综上所述,状态表示对动态规划的性能的影响是多方面的。因此,在解决问题时,从各方面比较状态表示,根据具体情况选择高效的状态表示,才能进一步优化动态规划。

[标签:竞赛联赛,数学联赛]

网友关注

高三复习备考存在的问题及应对策略

黑龙江省2020年普通高校艺术类专业招生 舞蹈编导专业课全省统一考试考试说明及评分参考

教育部支持社会服务产业发展,提高家政、养老、育幼等领域紧缺人才培养培训质量发布《意见》

2020年度辽宁省招飞招生初选安排(持续更新)

2019年浙江省普通高校艺术专业招生统一考试编导类考试大纲

黑龙江:关于做好2020年普通高等学校招生报名工作的通知

黑龙江省2020年普通高校艺术类专业招生 舞蹈表演专业课全省统一考试考试说明及评分参考 一、报考条件

江西省2020年普通高考报名艺术、体育类专业及相关特殊类型招生兼报办法

关于做好福建省2020年招收民航飞行学员工作的通知

月考过后,高三生如何调整,才能快速突围

黑龙江关于做好2019年学业水平考试校考科目相关工作的通知

2020年高考作文预测:闲看庭前花开落

湖南:注意!明年艺术类全省统考时间提前

2019年山西省普通高校艺术类专业舞蹈类联考考试大纲

浙江2020年艺术类专业省统考时间表

黑龙江省2020年普通高校艺术类专业招生播音与主持艺术专业课全省统一考试考试说明及评分参考

下学期初中班主任工作计划范文

江苏2020年高考音乐类专业省统考声乐曲目库和伴奏音频公布

黑龙江省2020年普通高校艺术类专业招生音乐学类专业课全省统一考试考试说明及评分参考

2020年河北省普通高校艺术类体育类专业招生进一步扩大平行志愿实施范围

福建省教育厅关于做好2019年高职扩招考试录取有关工作的通知

2020年高考专业选择最全指南,看完你就明白了

北京:中国民用航空飞行学院2020年招收飞行技术专业学生的通知

中国民用航空招飞信息系统2020年度考生手册

湖北:多所本科高校无毕业清考,学业不达标只能延期毕业

2020年高考作文预测:苦干实干巧干,照亮人生之路

2020年河北省普通高校招生体育类招生平行志愿解读

江苏:3所“双一流”高校重启师范教育

2019年在江苏省招生艺术校考院校名单及报名时间汇总表

看完2019高考高分作文, 发现“好标题”都有这6个规律!

网友关注视频

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

高中语文知识清单高考语文总複习工具书第5次修订五全綵版五三曲一线科学备考基础知识手册知识大集结资料书参考书导书高一高二高三

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

高中数学必修5 高考数列选填真题技巧秒杀讲解

爆笑班主任 第一季 第221集 高考结束学生有多疯狂?山东王老师疯狂吐槽

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

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

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

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

2019高考语文试卷解析

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

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

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

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

良心推荐:2019高考数学全国3卷理科12题讲解,附答案

沈阳音乐学院郎亦农教授的女高音高考曲目解析课程 第9集 《赛吾里麦》演唱讲解,音乐表现一定要自然流畅

探秘历史 第二季 第211集 此人高考数学考了0分,因作文写3句话被重点大学录取

高级中学高考试卷分析专题教研评比活动

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

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

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

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

至考方休!高考之前必听的三首励志歌曲,每次坚持不住了都会听!

盘点今年最难的高考数学题

沈阳音乐学院郎亦农教授的女高音高考曲目解析课程 第1集 沈阳音乐学院郎亦农为你讲解女高音高考曲目

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

优秀!英语数学双满分,广西“最牛”高考状元730分刷新最高纪录

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

衍声高考琴行2019高本硕学生暑假音乐会 张俊瀚《陕北民歌主题变奏曲》《阿根廷舞曲》第三乐章

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