动态规划初步.doc

1
2
第八讲 动态规划初步
一、动态规划简介
动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家贝尔曼〔〕提出了解决这类问题的“最优化原那么〞，1957年length(line)) and (line[i]=' ') do i:=i+1;
current:=0;
while (i<=length(line)) and (line[i]<>' ') do
begin
current:=current*10+ord(line[i])-ord('0');
i:=i+1
end;
total:=total+1;
height[total]:=current
end;
longest[1]:=1;
for i:=2 to total do
begin
maxlong:=1;
for j:=1 to i-1 do
begin
if height[i]<=height[j]
then if longest[j]+1>maxlong
then maxlong:=longest[j]+1;
longest[i]:=maxlong
end;
end;
maxlong:=longest[1];
for i:=2 to total do
if longest[i]>maxlong then maxlong:=longest[i];
writeln(maxlong);
sys[1]:=height[1]; tail:=1;
for i:=2 to total do
begin
minheight:=maxint;
1
3
for j:=1 to tail do
if sys[j]>height[i] then
if sys[j]<minheight then
begin minheight:=sys[j]; select:=j end;
if minheight=maxint
then begin tail:=tail+1; sys[tail]:=height[i] end
else sys[select]:=height[i]
end;
writeln(tail)
end.
二、动态规划的几个根本概念
想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指标函数。
阶段：把所给问题的过程，恰当地分为假设干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量。
状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问题过程中的状况，又称不可控因素。
决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定〔或选择〕，从而确定下一阶段的状态，这种决定称为决策，在最优控制中也称为控制。描述决策的变量，称为决策变量。
策略：由所有阶段的决策组成的决策函数序列称为全过程策略，简称策略。
状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过程。
指标函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数。指标函数的最优值，称为最优值函数。
三、确定动态规划的思路
1、采用动态规划来解决问题，必须符合两个重要的条件。
〔1〕“过去的历史只能通过当前状态去影响它未来的开展，当前的状态是对以往历史的一个总结〞，这种特性称为无后效性，是多阶段决策最优化问题的特征。
〔2〕作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简言之，一个最优策略的子策略总是最优的。这就是最优化原理。
2、如果碰到一个问题，能够满足以上两个条件的话，那么就可以去进一步考虑如何去设计使用动态规划：