动规基础动态问题的数学描述

PAGEPAGE3动态规动态规划问题的数学描述它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C2，C3)；若选择由B2：在每一个阶段中都需有一次决策，决策也可以用一个变量来描述，称XkKSkK，S={D1，D2}，XkSkU1=X（kKUkXk（Uk），XkkSk(UkXk(k)∈Sk(k)。例如在图的第三阶段中，若从状态C1出发，就可作出二种不同的决策，其允许决策集合S3(C1)={D1，D2}。若选取的点是D2，则D2是状态C1在决策X3(C1)作用下的下个新的状态，记作X3(C1)=D2。k)所组成的有序总体称为策略。在实际问题中，可供选择的策略有一定的范PP称为状态转移方程。如上图的状态转移方程为UK+1=Xk（Uk）。性：如果从A->B->C->D是A至D的最短路线，那么从B到D的最短路线必是B->C->D。更一般地说:如果最短路线在第K阶段通过Pk，则由点Pk出发Pk出发到达终点的所有可能选择的不同路线来若以Uk表示第K阶段的一个决策点，从终点开始，依逆向求出倒数第一阶段、倒数第二阶段、倒数第三阶段、……、倒数第N-1阶段中各点到达前逐步倒推至起点A。达终点的最短路线的长度，Sk（Xk，Uk）KXkUk的距离。当K=4时，F4（D1）=min[8，11]=8=min[7，11]=7=min[12]=12=min[21，19，23]=19K=1=min[22，19，20]=19略。路线A->B2->C1->D1->E为从AE19。Fk（Uk）=min[Sk（Uk，Xk）+Fk+1（Xk）] F5（U5）=0动态规划问题的程序框图 框动态规划问题的PASCAL程序用动态规划的最优化原理求出A->E的最省费用。I,J,X:Integer;wayArray[1..Max,1..Max]ofInteger;NetDot:Array[1..Max]ofNe:Integer;{NetDot[j].Ne--从J点出发的决策}StrString;Write('Filename=',Str);Readln(N,St,En);{读入顶点数，起点，终点}ForI:=1toNDoForJ:=1toNDoRead(F,Way[I,J]);ForI:=1toNDoNetDot[En].Cost:=0;NetDot[En].Ne:=0; 以下两句倒推的求解。}ForJ:=NDownto1DoForX:=NDowntoJIf(Way[J,X]>0)And(NetDot[X].Cost<>MaxintAnd(Way[J,X]+NetDot[X].Cost<NetDot[J].Cost)最短}NetDot[J].Cost:=NetDot[X].Cost+Way[J,X]ThenWrin('NoWay')WhileX<>0DoWrite(X:3,'101025--1-1-1-1--10--1214-1-1-1--1-1-6104-1-110-1-1-11-10--391-1-1-65--1-1-1-1-1-10-1101-10-51-1-121-1-1-1File1 8动态规划算法的基本步骤标准动态规划的基本框架对fn+1(xn+1)初始化 {边界条件fork:=ndownto1forxk∈Xkfk(xk):=一个极值 {∞或 ift比fk(xkthenfk(xk):=t;fk(xk)的最优值}t:=一个极值 {∞或forx1∈X1iff1(x1)比t更优then {按照10式求出最优指标以自底向上的方式或自顶向下的化方法（备忘录法）计算出最优值一．最短路径问题问题描述S4，S5为起点，T1，T2，T3，T4，T5代表终点，试找出一条从起点到终点的最短路径。如图中所的S4->A3->B3->C2->T3最短路径的长度为26。算法分析实数类型三维数组d（N，M，3）此时，d(1，1，1)=max，d(1，1，2)=3，d(1，1，3)=maxd(2，1，1)=7，d(2，1，2)=6，d(2，1，3)=maxd(5，1，1)=4，d(5，1，2)=max，d(5，1，3)=maxd(1，2，1)=max，d(1，2，2)=6，d(1，2，3)=7以下的最短为其中e(I，J，1)表示从此点到达下一个点的最短路径;e(I，J，2)表示3表示(I+1，J+1)FORI=1toNEXTFORI=M-1TO1STEP-1FORJ=1TO求出d(I，J，1)+e(I-1，J+1，1)d(I，J，NEXTJNEXT当d(I，1，2)=2时:I，2程序maxn=maxm=20;TMAP=ARRAY[0..MAXN,0..MAXM,1..3]OFREAL;TMAKE=ARRAY[0..MAXN,0..MAXM,1..2]OFREAL;n,m:BYTE;PROCEDUREi,j,k:BYTE;FORi:=1TOnDOFORj:=1TOmDOFORk:=1TO3DOREAD(d[i,j,IFd[i,j,k]=0THENd[i,j,k]:=1e8;getn:=n－ORD(NOTODD(MM));PROCEDUREi,j,k,p:INTEGER;o,no:REAL;FORj:=m-1DOWNTO1FORi:=1TOgetn(j)DOo:=p:=FORk:=-1TO1DOno:=e[i+k,j+1,1]+d[i,j,k+2];IFno<oTHENp:=o:=e[i,j,1]:=e[i,j,2]:=p;PROCEDUREi,j,p:INTEGER;p:=1FORi:=2TOnIFe[i,1,1]<e[p,1,1]THENp:=WRIN('MinLength=',e[p,1,WRITE('Trailis','S',p);FORi:=1TOm-1DOWRITE('-IFi<m-1THENWRITE(chr(64+i))ELSEWRITE('T');p:=p+TRUNC(e[p,i,2]);SAMPLE50300670808126120 06200870000120000000SAMPLEMinLength=Trail S4->A4->B4->C3->问题描述

求最长不下降序列na(1)、a(2)、……、a(n)且a(i)<>a(j)(i<>j).例如3，18，7，14，10，12，23，41，16，24。若存在i1<i2<i3iea(i1)<a(i2a(ie)则称为长度e不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，算法分析存在长度为1的不下降序列；一般若从d（I，2）INFORI=1TONINPUT#1,D(I,1)D(I,2)=D(I,3)=0NEXTIFORI=N-1TO1STEP-1L=P=FORJ=I+1TOIFD(I,1)<D(J,1)ANDD(J,2)>LTHENL=D(J,2)P=JENDIFNEXTIFL>0THEND(I,2)=L+1D(I,3)=PENDNEXTDMAX=D(1,2)L=1FORI=2TON-IFD(I,2)>DMAXTHENDMAX=D(I,2)L=IENDIFNEXTWHILEL<>0PRINTD(L,L=D(L,3)程序TLIST=ARRAY[1..MAXN,1..3]OFINTEGER;PROCEDUREFORI:=1TONDOPROCEDUREFORI:=N-1DOWNTO1DOFORJ:=I+1TONIF(D[I,1]<D[J,1])AND(D[J,2]>L)THENIFL>0FORI:=1TONDOWRITE(D[I,1]:5);FORI:=2TON-1DOIFD[I,2]>DMAXTHENWRITE('RESULTIS:');WHILEL<>0DOWRIN('MAXLENGTH=',D[DMAX,2]);SAMPLE 4116SAMPLE 4116RESULTIS: 3710122341MAXLENGTH=6最小代价子母树问题描述最优化原理应在子问题求解中体现。有些问题也允许顺推算法分折 假设有n个权值 WPL=4×21×22×2WPL=4×11×32×3如何构造树呢？俗称算法。现叙述如下根据给定的n个权值 ，W(n)构成n棵叉树的集合 片叶子，对应于树叶的一种划分方案。记为(左3，右4)。对应添号形式是:(4+4)+8)+((5+4)+(3+5)))其代价和为91。图(b)对应于另一种划分方案记为(左4，右3)，其代价和是94。可见，由于树以有16)，(左2，右53，右4)，(4，右3)，(左5，右2)，(左6，右1)六种划分方法，对于每一种划分方法都对元一棵二元树，从中找出4，8，5，4，3，5210，2(5，4，3)，(4，3，5)共计5种。于是生成二片树叶的权。代价计算时应考虑3片树叶的划分状态可能(左1，右2)或(左2，右1)，3片树叶的代价应考虑以(左1，右2)划分时其状态有(4)，(4，8)，其中(4)的代价为0，(4，8)代价为12。代价和为12=0+12。以(左2，右1)划分时其状态有(4，4)，(8)，其中(4，4)的代价为8，8的代价为0。代价和为8。因为8比12小，3片树叶4，4，8的代价是它的权加上划分状态中代价小的。于是得出第一个代价为16+8=24。余类推。前面划分的可能情况。以树叶权重为4，4，8，5为例。它的划分方法有:1，3223，1)三种。(4，4，5)代价为29，0+29=29(代价和)。(8，5)代价为13，8+13二21(代价和)。24，(5)的代价为0，24024(代价和)。代价为21+21=42。其他代价可仿此计算。当权重为25，树叶是4，4，8，5，4。划分(左1，右4)的状态是(4)，(4，8，5，4)，代价和为0+42=42。划分(左2，右3)的状态是(4，4)，(8，5，4)，代价和为8+26=34。因为8，5，4326。划分(左3，右2)的状态是(4，4，8)，(5，4)。由图中查得代价和为24+9=33。划分(左4，右1)的状态是(4，4，8，5)，(4)，由图中查得代价和为42+0=42。于是关于权重为25，树叶为4，4，8，5，4的代价为25+33=58。划分(左1，右4)代价为0+39=39划分2，右3)代价12+19=31程序TLIST=ARRAY[1..MAXN,1..MAXN]OFINTEGER;PROCEDUREFORI:=1TONDOREAD(F,SUM[1,I]);FORI:=2TONDOFORJ:=1TON-I+1SUM[I,J]:=SUM[I-1,J]+SUM[1,I-PROCEDUREFORI:=2TONFORJ:=1TON-I+1DOFORK:=1TOI-1DOIFNO<OTHENPROCEDUREPRINT;A:ARRAY[1..MAXN]OFINTEGER;PROCEDUREIFX1=0THENEXIT;FORI:=1TONDOIFA[I]<>0THENIF(I=X1)OR(I=X2)THENWRITE('-');IFI>2THENIFX1<>X2END;{OFFORI:=1TONDOA[I]:=SUM[1,I];X1:=-WRIN('MINCOST=',B[N,1]); 4116SAMPLE-3 411621-7-141012234116-21-2110122341164210164222--8741-16-87-41--87-MINCOST=问题描述物品可以多次选取)，使其重量的和小于等于XK，而价值的和为最大。算法分析X(I)W(I)≤XKX(I)V(I)F0(Y)=0，Y，N=4，XK=10W1=2，当y=21个第一种物品，价值1，…，当y=10(即XK)，此时，可取5个第一种物品，价值为5。品，价值为3，取大者，所以F2(3)=3。价值为3，所以F2(4)=3。有2种考虑，第一种是全部取第一种，即F1(10)=5；第二种是由F2(7)+3=6+9，取大者，得到F2(10)=9。若后者大，则输出WN，计算F(N，XK-WN)。TLIST=ARRAY[1..MAXN]OFBYTE;TMAKE=ARRAY[0..MAXN,0..MAXXK]OFINTEGER;PROCEDUREFORI:=1TONDOREAD(W[I]);FORI:=1TONDOPROCEDUREFORI:=1TONDOFORJ:=1TOW[I]-1DOF[I,J]:=F[I-1,J];FORJ:=W[I]TOXKDOTHENF[I,J]:=F[I-1,J]ELSEF[I,J]:=F[I,J-PROCEDUREPRINT;WHILEI>0IFF[I,J]=F[I-1,J]THENELSE N('N=',N,'','XK=',XK); N('MAXFORI:=1TONDOWRIN(''''SAMPLE4234135SAMPLE4XK=:WORTH=1210233134504791(1)问题描DAn③下面给出盘子的个数为n的一般方法，用F4(n，a，b，c，d)表示四塔问题，从AD移动n个盘子，可以利用b，c作为工作单元，四塔问题可以分解为:F4(n，a，b，c，d)=>F4(r，a，c，d，b)+F3(n-为此，我们构造2个整型数组:F3(N),F4(N)程序PROGRAMTR=ARRAY[1..MAXN]OFINTEGER;TFUNC=ARRAY[1..MAXN]OFdouble;PROCEDUREWRITE('INPUTN:');FORI:=2TONDOF3[I]:=(F3[I-1]+1)*2-1;PROCEDUREFORI:=2TONDOFORJ:=1TOI-1IF2*F4[J]+F3[I-J]<KTHENK:=2*F4[J]+F3[I-

WRIN('TOTAL=',F4[N]);(*INPUTN:10INPUT:10TOTAL=INPUTN:TOTAL=问题描述设有一个NxM的方格如图所示，在方格中去掉某些点，方格边上的数字代A前进的方向只能向右，或向下，而被去掉点的代价可看成无穷大。算法分析B32，B3B1，B1B，B3B5，B5B，min{B3B+B1最小路径，B3B5+B5最小路径}。通常在方格中某个坐标点(i，i)，其最小路径路径}。为了记录求出的路径，用数组D(N，M，2)来记录，其中： 向下程序maxMN=30;TMAP=ARRAY[1..MAXMN,1..MAXMN]OFINTEGER;TMAKE=ARRAY[1..MAXMN,1..MAXMN,1..2]OFWORD;PROCEDUREINIT;i,j:BYTE;FORi:=1TOnDOFORJ:=1TOMIFA[I,J]=0THENA[I,J]:=MAXINT;PROCEDUREi,j:FORI:=N-1DOWNTO1DOFORJ:=M-1DOWNTO1FORI:=N-1DOWNTO1DOFORJ:=M-1DOWNTO1DOTHENBEGINPROCEDUREPRINT; N('GOTHISWAY:WRITE('');WHILE(I<N)OR(J<M)DOIFD[I,J,2]=1THENINC(J)ELSEWRIN('(',N:2,',',M:2,')');WRIN('MINCOST=',D[