noip动态规划课件.ppt

动态规划; 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些有哪些信誉好的足球投注网站或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。;第一节 动态规划的基本模型;【例1】最短路径问题。下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？;具体计算过程如下： S1： K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3； S2： K = 3 有 F3（C1）= MIN{ D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2）} = MIN{ 5+3，6+4 } = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6 S3： K = 2 有 F2（B1）= MIN{ D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9 F2（B2）= MIN{ D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4）} = MIN{ 8+8，4+6 } = 10 S4： K = 1 有 F1（A）= MIN{ D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2）} = MIN{ 5+9，3+10} = 13 因此由A点到E点的全过程最短路径为A→B2→C4→D3→E；最短路程长度为13。 从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。 在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。;动态规划的基本概念和基本模型构成 ;最优化原理与无后效性 ;动态规划设计方法的一般模式 ;【例1】对应的Pascal程序如下： var d : array[1..4,1..4,1..4] of integer; f : array[1..5,1..4] of integer; i,j,k,min : integer; begin fillchar(d,sizeof(d),0); d[1,1,1] := 5; d[1,1,2] := 3; d[2,1,1] := 1; d[2,1,2] := 6; d[2,1,3] := 3; d[2,2,2] := 8; d[2,2,4] := 4; d[3,1,1] := 5; d[3,1,2] := 6; d[3,2,1] := 5; d[3,3,3] := 8; d[3,4,3] := 3; d[4,1,1] := 3; d[4,2,1] := 4; d[4,3,1] := 3; fillchar(f,sizeof(f),255); f[5,1] := 0; for i := 4 downto 1 do for j := 1 to 4 do for k := 1 to 4 do if d[i,j,k] 0 then if f[i,j] d[i,j,k]+f[i+1,k] then f[i,j] :=