文档介绍：信息学奥林匹克竞赛
主题:动态规划-1
初2015级
2014年1月22日
1951年美国数学家贝尔曼 ,根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。他提出了解决这类问题的“最优化原理”。1957年发表了他的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用,取得了显著的效果。
动态规划不是万能的,它只适于解决一定条件的最优策略问题。
“满足一定条件”主要指下面两点:      (1)状态必须满足最优化原理;      (2)状态必须满足无后效性。
动态规划适于解决什么样的问题
动态规划是运筹学的一个分支。
与其说动态规划是一种算法,不如说是一种思维方法来得更贴切。
许多隐式图上的算法,例如求单源最短路径的Dijkstra算法、广度优先搜索算法,都渗透着动态规划的思想。
还有许多数学问题,表面上看起来与动态规划风马牛不相及,但是其求解思想与动态规划是完全一致的。
什么是动态规划?
(1)状态(state)     对于一个问题,所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个状态。
(2)状态变量(sk)     对每个状态k关联一个状态变量sk,它的值表示状态k所对应的问题的当前值。
(3)决策(decision)     决策是一种选择,对于每一个状态而言,你都可以选择某一种路线或方法,从而到达下一个状态。
(4)决策变量(dk)     在状态k下的决策变量dk的值表示对状态k当前所做出的决策。
动态规划的常用名词
(5)策略     策略是一个决策的集合,其中满足某些最优条件的策略称之为最优策略。
(6)状态转移函数(t)     从一个状态到另一个状态,可以依据一定的规则来前进。用一个函数t来描述规则,它将状态i和决策变量di映射到另一个状态j,记为t(i,di)=j
(7)状态转移方程(f)     状态转移方程f描述了状态变量之间的数学关系。一般来说,与最优化问题相应,状态转移方程表示si的值最优化的条件,或者是状态i所对应问题的最优解值的计算公式,用代数式表示就是:     si=f({(sj,dj)|i=t(j,dj),对决策变量dj所有可行的取值})
动态规划的常用名词
“最优化原理”:
-- 无论前面的状态和决策如何,对前面的决策所形成的当前状态而言,余下的诸决策必须构成最优策略。
-- 子问题的局部最优将导致整个问题的全局最优,即问题具有最优子结构的性质,也就是说一个问题的最优解只取决于其子问题的最优解,而非最优的解对问题的求解没有影响。
--并不是所有的“决策问题”都可以用“动态规划”来解决,运用“动态规划”来处理问题必须满足最优化原理。
最优化原理
例最短路径问题
因此由A点到E点的全过程的最短路径为
A—>B2一>C4—>D3—>E 最短路程长度为13。
例余数最少的路径
如图所示,有4个点,分别是A、B、C、D,相邻两点用两条连线C2k,C2k-1(1≤k≤3)表示两条通行的道路。连线上的数字表示道路的长度。定义从A到D的所有路径中,长度除以4所得余数最小的路径为最优路径。求一条最优路径。
最优化原理
无后效性原则:
-- 某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说,“未来与过去无关”,当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变。
--从图论的角度去考虑,如果把这个问题中的状态定义成图中的顶点,两个状态之间的转移定义为边,转移过程中的权值增量定义为边的权值,则构成一个有向无环加权图,因此,这个图可以进行“拓扑排序”,至少可以按他们拓扑排序的顺序去划分阶段。
无后效性
9
8
7
6
4
5
3
2
1
a1=6
a2=4
a3=5
a4=1
a5=1
a6=2
a7=9
a8=7
a9=4
a10=2
a11=4
例货郎担问题
对于平面给定的n个点,编程确定一条连结各点的、闭合的游历路线问题。图中给出了7个点的情况问题的解。
阶段与阶段之间没有什么必然的“顺序”。
例旅游路线问题
在货郎担问题的基础上,若规定这种游历路线先从最左边开始,严格地由左至右到最右边的点,然后再严格地由右至左到出发点,求整个路程最短的路径长度。
无后效性
(1)划分阶段
    (2)确定状态和状态变量     (3)确定决策并写出状态转移方程     (4)寻找边界条件     (5)程序设计实现。
动态规划设计方法的一般模式