动态规划（二）

复习：动态规划解题四步骤 描述一个最优解的结构； 递归地定义最优解的值； 以“自底向上”的方式计算最优解的值； 从已计算的信息中构建最优解的形成路径。

复习：可以应用动态规划解题的两个基本条件是什么？ 题目性质具有“最优子结构”特征，即问题的一个最优解中包含着子问题的最优解。 重叠子问题 ，即求解问题的解时要反复计算若干个相同子问题。 同理，求解各个子问题时又要反复计算若干子子问题，这些子子问题可能是新产生的，也可能是重复产生的。

讨论：装配线调度问题 装配线调度问题: 汽车厂的总装车间有两条装配线. 每条装配线上都有n个装配点,编号分别为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. 汽车可以在两条装配线上随意地调度. 请问: 在如图(见下页)所示的装配线中, 怎样安排汽车的装配点, 使得装配时间最短? E1 E2 A1,1 A2,1 A1,2 A2,2 A1,3 A2,3 A1,4 A2,4 …… A1,n-1 A2,n-1 A1,n A2,n T1,1 T2,1 T1,2 T1,3 T1,n-1 T2,2 T2,3 T2,n-1

分析：装配线调度问题 你怎样分析出装配线调度问题具备“最优子结构”性质？ 提示：在分析问题的时候，可能需要引进一些符号来表示一些数学量。想一想，在本问题中我们需要引进哪些符号来表示哪些数学量？ 提示2：你必需引进一些符号来表达所有的已知量，也必需引进适当的符号来表示出问题的解以及子问题的解。 2 4 7 8 9 5 3 6 A2,n-1 1

分析：装配线调度问题-续 你怎样分析出装配线调度问题具备“重叠子问题”性质？ 提示：在这里只需要定性地分析和描述重叠子问题性质。也就是说你自己要在心里面清楚问题具备重叠子问题性质。 2 4 7 8 9 5 3 6 A2,n-1 1

分析：装配线调度问题-续 你怎样递归地定义最优解的值？用子问题的最优解表示问题的最优解 提示：在书写递归式的时候要注意两个方面：一是通项公式怎么写？通项的取值范围是什么？二是递归的边界条件怎么写？ 没有通项公式就还没有写出递归式；没有边界条件，递归式就不会结束。 2 4 7 8 9 5 3 6 A2,n-1 1

分析：装配线调度问题-续 你怎样“自底向上”地求解本问题（将递归式转化为递推式）？ 提示：在思考递推式时，我们要考虑怎样表示第一项？怎样由第一项表示第二项？等等。 要求：在纸上实现整个程序，并用测试数据进行测试。 2 4 7 8 9 5 3 6 A2,n-1 1

分析：装配线调度问题-续 你怎样输出最优解的形成路径？ 提示：修改程序，增加一个记录每一步最优解位置的数据结构。在动态规划求得最优解的值完成后，用另一个过程输出最优解的形成路径。 要求：在纸上实现整个程序，并上机调试程序。 2 4 7 8 9 5 3 6 A2,n-1 1

思考：装配线调度问题 假设汽车在最后一站装配完成后，离开装配线还需要个“离开时间”，如下图所示，则程序又要作怎样的修改？ 2 4 7 8 9 5 3 6 A2,n-1 1

For k :=2 to n begin t1 := m[1,k-1]; t2 := m[2,k-1] + t[2,k-1]; if t1 < t2 then begin m[1,k] := t1+ a[1,k]; w[1,k] := 1; end else begin m[1,k] := t2 + a[1,k]; w[1,k] := 2; end; m[2,k]

Procedure print(I,j :integer); Var k:integer; Begin if j > 1 then begin k := w[I,j]; pirnt(k,j-1); End; writeln(‘S’,I,’,’, j);

了解动态规划的有关概念 什么是多阶段决策问题？ 什么是阶段、状态、决策？

多阶段决策问题 多阶段决策问题：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。 装配线调度问题就是一个典型的多阶段决策问题。

阶段 阶段(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阶段的状态是B1，则第3、4阶段的过程演变就与第1阶段的状态无关。 通常还要求状态是直接或间接可以观测的。

状态-续 描述状态的变量称状态变量。变量允许取值的范围称允许状态集合。 用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在最短通路问题中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)可取什么值？ A B1 B2 C2 C1 C3 D 5 2 3 7 4

动态规划的基本思想 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。 因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。