动态规划 2.ppt

1、动态规划（二）,复习：动态规划解题四步骤,描述一个最优解的结构； 递归地定义最优解的值； 以“自底向上”的方式计算最优解的值； 从已计算的信息中构建最优解的形成路径。,复习：可以应用动态规划解题的两个基本条件是什么？,题目性质具有“最优子结构”特征，即问题的一个最优解中包含着子问题的最优解。 重叠子问题 ，即求解问题的解时要反复计算若干个相同子问题。 同理，求解各个子问题时又要反复计算若干子子问题，这些子子问题可能是新产生的，也可能是重复产生的。,讨论：装配线调度问题,装配线调度问题: 汽车厂的总装车间有两条装配线. 每条装配线上都有n个装配点,编号分别为j=1,2,n. 我们标记第I条(I=

2、1,2)装配线的第j个装配点为Si,j . 我们规定S1,j 和S2,j做的工作相同, 但由于效率, 技术等原因使S1,j和S2,j的工作时间却不同. 我们标记Ai,j为Si,j的工作时间. 汽车底盘进入两条装配线的进入时间分别标记为E1和E2. 汽车除了在一条装配线上流动外, 还可以转移到另一条装配线上去. 我们把在Si,j工作完后转移到另一条装配线的时间标记为Ti,j. 汽车可以在两条装配线上随意地调度. 请问: 在如图(见下页)所示的装配线中, 怎样安排汽车的装配点, 使得装配时间最短?,分析：装配线调度问题,你怎样分析出装配线调度问题具备“最优子结构”性质？ 提示：在分析问题的时候，可

3、能需要引进一些符号来表示一些数学量。想一想，在本问题中我们需要引进哪些符号来表示哪些数学量？ 提示2：你必需引进一些符号来表达所有的已知量，也必需引进适当的符号来表示出问题的解以及子问题的解。,分析：装配线调度问题-续,你怎样分析出装配线调度问题具备“重叠子问题”性质？ 提示：在这里只需要定性地分析和描述重叠子问题性质。也就是说你自己要在心里面清楚问题具备重叠子问题性质。,分析：装配线调度问题-续,你怎样递归地定义最优解的值？用子问题的最优解表示问题的最优解 提示：在书写递归式的时候要注意两个方面：一是通项公式怎么写？通项的取值范围是什么？二是递归的边界条件怎么写？ 没有通项公式就还没有写出递

4、归式；没有边界条件，递归式就不会结束。,分析：装配线调度问题-续,你怎样“自底向上”地求解本问题（将递归式转化为递推式）？ 提示：在思考递推式时，我们要考虑怎样表示第一项？怎样由第一项表示第二项？等等。 要求：在纸上实现整个程序，并用测试数据进行测试。,分析：装配线调度问题-续,你怎样输出最优解的形成路径？ 提示：修改程序，增加一个记录每一步最优解位置的数据结构。在动态规划求得最优解的值完成后，用另一个过程输出最优解的形成路径。 要求：在纸上实现整个程序，并上机调试程序。,思考：装配线调度问题,假设汽车在最后一站装配完成后，离开装配线还需要个“离开时间”，如下图所示，则程序又要作怎样的修改？,

5、For k :=2 to n begin t1 := m1,k-1; t2 := m2,k-1 + t2,k-1; if t1 t2 then begin m1,k := t1+ a1,k; w1,k := 1; end else begin m1,k := t2 + a1,k; w1,k := 2; end; m2,k,Procedure print(I,j :integer); Var k:integer; Begin if j 1 then begin k := wI,j; pirnt(k,j-1); End; writeln(S,I, j); End;,了解动态规划的有关概念,什么是多

6、阶段决策问题？ 什么是阶段、状态、决策？,多阶段决策问题,多阶段决策问题：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。 装配线调度问题就是一个典型的多阶段决策问题。,阶段,阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序求解最优化问题。阶段变量一般用k=1,2,.,n表示。在最短通路问题中由A出发为k=1，由Bi(i=1,2)出发为k=2，依此下去从Di(i=1,2,3)出发为k=4，共n=

7、4个阶段。 思考：装配线调度问题可分为多少个阶段？,状态,状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性。 所谓无后向性即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。例如，在最短通路问题中，假设第2阶段的状态是B1，则第3、4阶段的过程演变就与第1阶段的状态无关。 通常还要求状态是直接或间接可以观测的。,状态-续,描述状态的变量称状态变量。变量允许取值的范围称允许状态集合。 用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在最短通路问题

8、中x2可取B1，B2，X2=B1,B2。 n个阶段的决策过程有n+1个状态变量，x n+1表示xn演变的结果，在例1中x5取。 状态变量简称为状态。 思考：在装配线调度问题中，每个阶段有几个状态？是什么？,决策,当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。 描述决策的变量称决策变量。变量允许取值的范围称允许决策集合。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。在最短通路问题中u2(B1)可取C1,C2 决策变量简称决策。 思考： u2(B2)可取什么值？,动态规划的基本思想,动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复