当前位置:首页 >> 学科竞赛 >>

pascal 语言之动态规划1


pascal 语言之动态规划篇(一) ------数塔问题

数塔问题描述
如图所示数塔,从顶部出发,在每一结点可以选择向 左走或是向右走,一起走到底层,要求找出一条路径,使 路径上的值最大(IOI 94)
13
11 8

12

7 15

26

6

14

8

12

7

13

24

11

数塔问题求解方法探讨
采用贪心算法
图示:
11 13

13

11

12

14

13

8

12

7 15

26

所得结果并非最优路径
6
14 8

12

7

13

24

11

数塔问题求解方法探讨
采用穷举算法
基本思路:从所有可能的路径中 找出一条最优路径
11 13

8

以本题为参考,可能存在 的路径是:1×2×2×2×2 即路径总数为2N-1! 当N较大时,是一个无法 完成的运算

12

7 15

26

6

14

8

不可取

12

7

13

24

11

数塔问题求解方法探讨
采用动态规划算法
基本思路:划分阶段,自顶向下 分析,自底部向上计算。
11 13

8

解决该类问题的最优算法选择

12

7 15

26

6

14

8

为什么?
12 7 13 24

11

数塔问题动态规划求解法
动态规划算法过程描述
1、阶段划分 第五阶段 第四阶段
11 13

8

第三阶段

12

7 15

26

第二阶段 第一阶段

6

14

8

12

7

13

24

11

数塔问题动态规划求解法
动态规划算法过程描述
2、分阶段决策 第五阶段 第四阶段
11 57 86 13

8 73

第三阶段

30 12

46 7

65 26

第二阶段 第一阶段

6 18

14 27

15 39

32 8

12

7

13

24

11

数塔问题动态规划求解法
动态规划算法过程描述
3、根据最优值确定路径 第五阶段
11 57 13 86

第四阶段

73 8

第三阶段

12 30

46 7

26 65

第二阶段 第一阶段

18 6

14 27

15 39

32 8

12

7

13

24

11

数塔问题动态规划求解法
动态规划算法程序设计
图形转化
由于直角三角形便于搜索 向上、向右,故先将原图形 变为直角三角形形态 数据存储及变量设定 Var a:array[1..50,1..50,1..3] of longint; x,y,n:integer; { 1)n 表示数塔层数 2)x,y用以标示行与列 3)a[x,y,1] 数组用于读入存储初始 数据; a[x,y,2] 为状态变化数组; a[x,y,3]}为路径记录数组。}
13

11

8

12

7

26

6

14

15

8

12

7

13

24

11

数塔问题动态规划求解法
对应数组值变过程
86 13

1表示路标向右

a[x,y,2]

1 0

a[x,y,3]

57 11

73 8

1 0

1 0
0表示路标向下

39 12

46 7

65 26

1 0

1 0

0

18 6

27 14

39 15

32 8

0

1 0

1 0

0

12

7

13

24

11

0

0

0

0

0

数塔问题动态规划求解法
自顶向下的路径追溯
13

初始化行坐标x=1,列坐标y=1

X=1,y=1 ,A[x,y,1] (13),y=y+1
1

11

8

X=2,y=2 A[x,y,1] (8),y=y+1
1 1

12

7

26

1

1

0

X=3,y=3 A[x,y,1] (26),y=y+0

6

14

15

8

0

1

1

0

X=4,y=3 A[x,y,1] (15),y=y+1

12

7

13

24

11

0

0

0

0

0

X=5,y=4 A[x,y,1] (24),y=y+0

数塔问题动态规划程序参考
program shuta1; var a:array[1..50,1..50,1..3] of longint; x,y,n:integer; begin readln(n); for x:=1 to n do for y:=1 to x do begin read(a[x,y,1]); a[x,y,2]:=a[x,y,1]; a[x,y,3]:=0; end; for x:=n-1 downto 1 do for y:=1 to x do if a[x+1,y,2]>a[x+1,y+1,2] then begin a[x,y,2]:=a[x,y,2]+a[x+1,y,2]; a[x,y,3]:=0; end else begin a[x,y,2]:=a[x,y,2]+a[x+1,y+1,2]; a[x,y,3]:=1; end; writeln('max=',a[1,1,2]); y:=1; for x:=1 to n-1 do begin write(a[x,y,1],'-->'); y:=y+a[x,y,3] end; writeln(a[n,y,1]); End.

数塔问题动态规划求解法
如果该类数塔问题仅仅是为了最优解,则 状态划分可以自上而下进行。
13 13

第一阶段
8

11

第二阶段

24 11

21 8

36 12 12

7

26

第三阶段
8

31 7

47 26

6

14

15

第四阶段

42 6

50 14

62 15

55 8

12

7

13

24

11

第五阶段

54 12

57 7

75 13

86 24

66 11

数塔问题动态规划程序参考

program dtghst; var a,b:array[0..100,0..100] of longint; i,j,n:integer; max:longint; begin readln(n); fillchar(a,sizeof(a),0); for i:=1 to n do for j:=1 to i do read(a[i,j]); b:=a; b[1,1]:=a[1,1];

for i:=2 to n do for j:=1 to i do if b[i-1,j-1]>b[i-1,j] then b[i,j]:=b[i-1,j-1]+b[i,j] else b[i,j]:=b[i-1,j]+b[i,j]; max:=0; for i:=1 to n do if b[n,i]>max then max:=b[n,i]; writeln('max=',max); end.

动态规划求解问题方法

1.确定阶段和阶段变量 阶段:过程的划分,包括时间、空间的划分, 阶段数:n 阶段变量:描述阶段的变量用k 表示,k=1,2,…..,n 2.确定状态和状态变量 状态:描述过程的必要信息。 状态应具有无后效性: 若给定了某阶段状态,则在这阶 段以后过程的发展不受这阶段以前各阶段状态的影响.

动态规划求解问题方法

3.设定决策变量进行目标决策 决策:决定(选择),从一个阶段的状态到 下一个阶段状态的选择。 决策变量:描述决策的变量,

4.选择适当的策略,形成顺序序列。
5.构造状态转移方程,使得状态沿着序列方向发展。 6.确定最终指标或最优值。

动态规划求解问题的类型

1、最优调度 2、资源分配 3、最优路径 4、最优控制 5、设备更新 6、库存问题 7、背包问题 等等……


赞助商链接
相关文章:
动态规划——基本原理
关键词:pascal语言 1/2 相关文档推荐 动态规划基本原理 10页 免费 动态规划的...让我们先来看下面的例子: 如图所示的是一个带权有向的多段图, 要求从 A ...
动态规划——复制书稿
关键词:pascal语言 同系列文档 动态规划——轮船问题 动态规划——石子归并1...< bk-1 < bk = m, 这样,第 I 号抄写员得到的书稿是从 bi-1+1 到第...
Pascal动态规划 模型二
同系列文档 Pascal动态规划模型一1/2 相关文档推荐 Pascal 动态规划 模型三 2...Pascal动态规划 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题...
pascal中级教程第八章动态规划
pascal中级教程第八章动态规划_财会/金融考试_资格考试/认证_教育专区。pascal中级教程第八章动态规划第八章 8.1 动态规划 字串距离源程序名 可执行文件名 输入文...
动态规划专题
关键词:pascal语言动态规划专题 1/2 相关文档推荐 动态规划专题 123页 免费 专题...动态规划一、动态规划的基本思想: 动态规划的基本思想:动态规划算法通常用于求解...
NOIP-Pascal
noip pascal语言 动态规划 142页 8财富值 Pascal动态规划 22页 免费 Pascal动态...9. 10. 一台计算机如果要利用电话线上网,就必须配置能够对数字信号和模拟信号...
pascal教程9--数学问题
关键词:pascal语言教材 1/3 同系列文档 朝鲜历届领导人资料 朝鲜现状 为什么南北...pascal教程8--动态规划 16页 20财富值 pascal教程1--回溯法 24页 20财富值 ...
pascal教程
free pascal 语言入门(1) 21页 免费如要投诉违规内容,请到百度文库投诉中心;如...第一节 图论及其基本算法 第二节 动态规划 第一章 简单程序 无论做任何事情,...
信息技术竞赛
Pascal 语言 第一章 开始编写 pascal 语言程序 第二章 Pascal 语言基础知识 第...第四章 动态规划的递归函数法 第五章 动态规划分类 1 数学知识及相关算法 第...
Pascal教程(整理版)-莆田一中[1]
115 第二节 动态规划......122 1 《Pascal 语言学习教程》 莆田一中信息学奥赛兴趣小组 群号码:14779638 莆田一中程序测评系统网址:http://10.1.1.10/Judge...
更多相关标签: