第二节 动态规划.doc

第二节动态规划动态规划是近来发展较快的一种组合算法,是运筹学的一个分支,是解决多阶段决策过程最优化的一种数学方法。我们可以用它来解决最优路径问题,资源分配问题,生产调度问题,库存问题,装载问题,排序问题,设备更新问题,生产过程最优控制问题等等。在生产和科学实验当中,有一类活动的过程,可将它分成若干个阶段,在它的每个阶段要作出决策,从而使全局达到最优。当各个阶段决策确定后,就组成一个决策序列,因而也就决定了整个过程的一条活动路线。这种把一个过程看作一个前后相关具有链状结构的多阶段过程就称为多阶段决策过程。所谓动态是指在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生,故有"动态"的含义。下面,我们结合最短路径问题来介绍动态规划的基本思想。求下图中点O到点U的最短距离(假设只许往上和往右走)。从点O到点U,可以按经过的路径,分成七个阶段,分别为:O->AB->CDE->FGHJ->KLMN->PQR->ST->U。最短路径有一个重要特性:如果点O经过点H到达点U是一条最短路径,则在这条最优路径上由点H出发到达点U的子路径,是由点H出发到达点U所有可能选择的不同路径的最短路径(证明略)。根据这一特点,寻找最短路径的时候,可以从最后一段开始,用由后向前逐段递推的方法,求出个点到点U的最短路径。如若考虑到从点O到点U的最短路径,也是该路径上个点到点的最短路径,令O点到U点的最短距离为dO,A点到U点的最短距离为dA,...,故有:dO=min{2+dA,1+dB},dA=min{3+dC,2+dD},dB=min{2+dD,3+dE},................dQ=min{5+dT,2+dS}.下面按照动态规划的方法,将上例从最后一段开始计算,由后向前逐步递推移至O点。计算步骤如下:阶段7:从S点或T点到达U点,这时各自只有一种选择,故:dS=2;dT=3;阶段6:出发点有P,Q,R三个,其中Q点到达U点有两种选择,或是经过S点,或是经过T点,故:dQ=min{2+dS,5+dT}=min{4,8}=4;dP=min{1+dS}=min{3}=3;dR=min{3+dT}=min{6}=6;阶段5:出发点有K,L,M,N四个,同理有:dK=min{3+dP}=min{6}=6;dL=min{2+dP,4+dq}=min{5,8}=5;dM=min{2+dQ,4+dR}=min{6,10}=6;dN=min{4+dR}=min{10}=10;阶段4:出发点有F,G,H,J四个,同理有:dF=min{2+dK}=min{8}=8;dG=min{1+dK,3+dL}=min{7,8}=7;dH=min{1+dL,1+d}=min{6,7}=6;dJ=min{3+dM,3+dN}=min{9,13}=9;阶段3:出发点有C,D,E三个,同理有:dC=min{2+dF,2+dG}=min{10,9}=9;dD=min{4+dG,2+dH}=min{11,8}=8;dE=min{1+dH,2+dJ}=min{7,11}=7;阶段2:出发点有A,B两个,同理有:dA=min{3+dC,2+dD}=min{12,10}=10;dB=min{2+dD,3+dE}=min{10,1