《动态规划 2.ppt》由会员分享，可在线阅读，更多相关《动态规划 2.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划（二）复习：动态规划解题四步骤1.描述一个最优解的结构；2.递归地定义最优解的值；3.以“自底向上”的方式计算最优解的值；4.从已计算的信息中构建最优解的形成路径。复习：可以应用动态规划解题的两个基本条件是什么？复习：可以应用动态规划解题的两个基本条件是什么？题目性质具有“最优子结构”特征，即问题的一个最优解中包含着子问题的最优解。重叠子问题，即求解问题的解时要反复计算若干个相同相同子问题。同理，求解各个子问题时又要反复计算若干子子问题，这些子子问题可能是新产生的，也可能是重复产生的。讨论：装配线调度问题装配线调度问题装配线调度问题:汽车厂的总装车间有两条装配线.每条装配线上都有n个装
2、配点,编号分别为j=1,2,n.我们标记第I条(I=1,2)装配线的第j个装配点为Si,j.我们规定S1,j 和S2,j做的工作相同,但由于效率,技术等原因使S1,j和S2,j的工作时间却不同.我们标记Ai,j为Si,j的工作时间.汽车底盘进入两条装配线的进入时间分别标记为E1和E2.汽车除了在一条装配线上流动外,还可以转移到另一条装配线上去.我们把在Si,j工作完后转移到另一条装配线的时间标记为Ti,j.汽车可以在两条装配线上随意地调度.请问:在如图(见下页)所示的装配线中,怎样安排汽车的装配点,使得装配时间最短?E1E2A1,1A2,1A1,2A2,2A1,3A2,3A1,4A2,4A1,
3、n-1A2,n-1A1,nA2,nT1,1T2,1T1,2T1,3T1,n-1T2,2T2,3T2,n-1分析：装配线调度问题1.你怎样分析出装配线调度问题具备“最优子结构”性质？提示：在分析问题的时候，可能需要引进一些符号来表示一些数学量。想一想，在本问题中我们需要引进哪些符号来表示哪些数学量？提示2：你必需引进一些符号来表达所有的已知量，也必需引进适当的符号来表示出问题的解以及子问题的解。24789536448A2,n-14722314121A2,n-15223分析：装配线调度问题-续2.你怎样分析出装配线调度问题具备“重叠子问题”性质？提示：在这里只需要定性地分析和描述重叠子问题性质。也
4、就是说你自己要在心里面清楚问题具备重叠子问题性质。24789536448A2,n-14722314121A2,n-15223分析：装配线调度问题-续3.你怎样递归地定义最优解的值？用子问题的最优解表示问题的最优解提示：在书写递归式的时候要注意两个方面：一是通项公式怎么写？通项的取值范围是什么？二是递归的边界条件怎么写？没有通项公式就还没有写出递归式；没有边界条件，递归式就不会结束。24789536448A2,n-14722314121A2,n-15223分析：装配线调度问题-续4.你怎样“自底向上”地求解本问题（将递归式转化为递推式）？提示：在思考递推式时，我们要考虑怎样表示第一项？怎样由第一
5、项表示第二项？等等。要求：在纸上实现整个程序，并用测试数据进行测试。24789536448A2,n-14722314121A2,n-15223分析：装配线调度问题-续5.你怎样输出最优解的形成路径？提示：修改程序，增加一个记录每一步最优解位置的数据结构。在动态规划求得最优解的值完成后，用另一个过程输出最优解的形成路径。要求：在纸上实现整个程序，并上机调试程序。24789536448A2,n-14722314121A2,n-15223思考：装配线调度问题假设汽车在最后一站装配完成后，离开装配线还需要个“离开时间”，如下图所示，则程序又要作怎样的修改？24789536448A2,n-1472231
6、4121A2,n-1522352For k:=2 to n begin t1:=m1,k-1;t2:=m2,k-1+t2,k-1;if t1 1 then begin k:=wI,j;pirnt(k,j-1);End;writeln(S,I,j);End;了解动态规划的有关概念什么是多阶段决策问题？什么是阶段、状态、决策？多阶段决策问题多阶段决策问题：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。装配线调度问题就是一个典型的多阶段决策问题
7、。阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序求解最优化问题。阶段变量一般用k=1,2,.,n表示。在最短通路问题中由A出发为k=1，由Bi(i=1,2)出发为k=2，依此下去从Di(i=1,2,3)出发为k=4，共n=4个阶段。思考：装配线调度问题可分为多少个阶段？状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性无后向性。所谓无后向性即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。例如，在最短通路问题中，假设第2阶段的状态
8、是B1，则第3、4阶段的过程演变就与第1阶段的状态无关。通常还要求状态是直接或间接可以观测的。状态-续描述状态的变量称状态变量。变量允许取值的范围称允许状态集合。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在最短通路问题中x2可取B1，B2，X2=B1,B2。n个阶段的决策过程有n+1个状态变量，x n+1表示xn演变的结果，在例1中x5取。状态变量简称为状态。思考：在装配线调度问题中，每个阶段有几个状态？是什么？决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称
9、为控制(control)。描述决策的变量称决策变量。变量允许取值的范围称允许决策集合。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。在最短通路问题中u2(B1)可取C1,C2决策变量简称决策。思考：u2(B2)可取什么值？AB1B2C2C1C3D523274435动态规划的基本思想动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把对于重复出现的子问题，只在第一次遇到时加以求解，并把对于重复出现的子问题，只在第一次遇到时加以求解，并把对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解答案保存起来，让以后再遇到时直接引用，不必重新求解答案保存起来，让以后再遇到时直接引用，不必重新求解答案保存起来，让以后再遇到时直接引用，不必重新求解。