动态规划初步.ppt

动态规划初步4415468184动态规划初步
动态规划初步
一、引入
【例题1】
设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示:
若要求从根结点开始,
请找出一条路径,使
路径之和最大,只要
输出路径的和。
动态规划初步
13
15
14
11
24
13
12
11
8
7
6
8
7
26
12
动态规划初步
【问题分析】
①贪心法往往得不到最优解:
贪心法问题所在:眼光短浅。
根据贪心法,则13-11-21和45,而实质上13-8-40和61。
动态规划初步
②若用穷举法:从根结点开始,将所有可能的路径求和,找出最大值,但算法时间复杂性使问题解成为不可能。
当 N=1 P=1
N=2 P=2
N=3 P=4
……
N=K P=2K-1。当N=50,P=249=500万亿条路径。
动态规划初步
数据结构
a:array[1..n,1..n] of integer;
13
11
8
12
7
26
6
14
15
8
12
7
13
24
11
动态规划初步
b[i,j]=min{a[i,j]+a[i+1,j], a[i,j]+a[i+1,j+1]}
b[i,j]表示从点[I,j]出发到底部的最小值
program shuta{二维数组};
var a:array[1..1000,1..1000]of longint;
i,j,n:longint;
begin
read(n);
for i:=1 to n do
for j:=1 to i do
read(a[i,j]);
for i:=n-1 downto 1 do
for j:=1 to i do
if a[i+1,j]>a[i+1,j+1] then a[i,j]:=a[i,j]+a[i+1,j]
else a[i,j]:=a[i,j]+a[i+1,j+1];
writeln(a[1,1]);
end.
动态规划初步
总之,动态规划所处理的问题是一个“多阶段决策问题”,目的是得到一个最优解(方案)。大概思想如下图所示:
多阶段决策问题
动态规划初步
二、动态规划的几个基本概念
1、阶段和阶段变量
用动态规划求解一个问题时,需要将问题的全过程恰当地划分成若干个相互联系的阶段,以便按一定的次序去求解。描述阶段的变量称为阶段变量,通常用K表示。
阶段的划分一般是根据时间和空间的自然特征来定的,一般要便于把问题转化成多阶段决策的过程。