动态规划概念.ppt

文档介绍：如何运用动态规划算法解题
一、带权有向多段图问题
1阶段
2阶段
3阶段
4阶段
状态变量:A,B1,B2,C1,C2,C3,D
决策
状态转移
解题过程
设G[i]表示从起点A到点i的最段距离,D[i,j]为i到j的权值,则有如下状态转移方程
G[i]=min{G[j]+D[i,j]}
具体计算过程如下:
G[A]=0
G[B1]=min{G[A]+5}=5, G[B2]=min{G[A]+2}=2
G[C1]=min{G[B1]+3}=8,G[C2]=min{G[B1]+2,G[B2]+7}=7,
G[C3]=min{G[B2]+4}=6
G[D]=min{G[C1]+4,G[C2]+3, G[C3]+5}=10
概念
阶段:
把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同。
状态:
状态表示每个阶段开始面临的自然状况或客观条件。
决策:
一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。
策略:
由每个阶段的决策组成的序列称为策略。
状态转移方程:
给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k) )与x(k+1)确定的对应关系,
x(k+1)=Tk( x(k) , u(k) )
性质
最优性原理
作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。
无后效性原则
如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。