文档介绍：动态规划基本原理近年来,涉及动态规划的各种竞赛题越来越多,每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决;而竞赛对选手运用动态规划知识的要求也越来越高,,,多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,,,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,:如图所示的是一个带权有向的多段图,要求从A到D的最短路径的长度(下面简称最短距离).我们可以搜索,枚举图中的每条路径,但当图的规模大起来时,:从图中可以看到,A点要到达D点必然要经过B1和B2中的一个,所以A到D的最短距离必然等于B1到D的最短距离加上5,,B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2,…….我们设G[i]为点i到点D的距离,显然G[C1]=4,G[C2]=3,G[C3]=5,根据上面的分析,有:G[B1]=min{G[C1]+3,G[C2]+2}=5,G[B2]=min{G[C2]+7,G[C3]+4}=9,再就有G[A]=min{G[B1]+5,G[B2]+2}=10,所以A到D的最短距离是10,最短路径是A(B1(C2(,,以便于求解,过程不同,,阶段变量是离散的,,,且在任意两个不同的时刻之间允许有无穷多个决策时,,第一个阶段就是点A,而第二个阶段就是点A到点B,第三个阶段是点B到点C,,它不以人们的主观意志为转移,,它既是该阶段某路的起点,,第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段是三个状态C1,C2和C3,,,状态是离散的,,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但从分析的观点,,状态可以有多个分量(多维情形),因而用向量来代表;,:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,,当这段的始点给定时,不受以前线路(所通过的点),,从该状态演变到下一阶段某个状态的一种选择(行动),,,因状态满足无后效性,,可供选取的策略有一定的范围限制,(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对