暴雨与狂风华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传
动态规划(Dynamic Programming)算法设计与分析 Algorithms Design& Analysis第八讲：动态规划华中科技大学软件学院邱德红主讲 2005年4月 An algorithm design technique (like divide and conquer)(和分治法一样,是一种算法设计技术) Divide and conquer(分治法)– Partition the problem into independent subproblems (分割成独立的子问题)– Solve the subproblems recursively (递归解决子问题)– Combine the solutions to solve the original problem (合并求得初始问题的解)1
2
Dynamic Programming Applicable when subproblems are not independent (子问题非独立)– Subproblems share subsubproblems (子问题求解依赖其子问题的解)– A divide and conquer approach would repeatedly solve the common subproblems(分治法通过递归方式解决性质相同的子问题)– Dynamic programming solves every subproblem just once and stores the answer in a table (动态规划每次解决一个子问题，并将结果存储在表格中)
动态规划(Dynamic Programming) Used for optimization problems(适合优化问题)– A set of choices must be made to get an optimal solution (通过适当的选择来获得问题的最优解)– Find a solution with the optimal value (minimum or maximum) (找到具有最优解决方案及其最优值：装配线排程方案以及该方案的生产时间)– There may be many solutions that return the optimal value: an optimal solution (导致最优的解决方案可能不止一个)3 4
动态规划算法(Dynamic Programming Algorithm)1. Characterize the structure of an optimal solution (描述最优解的结构特征) 2. Recursively define the value of an optimal solution (定义最优解决方案的递归形式) 3. Compute the value of an optimal solution in a bottomup fashion(以自底向上的方式计算最优解决方案的值) 4. Construct an optimal solution from computed information (从计算信息构造出最优解决方案)
装配线排程问题 (Assembly Line Scheduling) Automobile factory with two assembly lines(汽车厂两条装配线)– Each line has n stations: S1,1, . . ., S1,n and S2,1, . . ., S2,n(每条装配线有n个工序站台)– Corresponding stations S1, j and S2, j perform the same function but can take different amounts of time a1, j and a2, j (每条装配线的第j个站台的功能相同,但是效率不一致)– Entry times e1 and e2 and exit times x1 and x2(上线和下线时间)
5
6
华中科技大学管理学院
华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传
装配线(Assembly Line) After going through a station, can either (在一个工序台 Si,j作业完成之后，汽车可以):– stay on same line at no cost, or(立即(时间为0)进入本装配线的下一工序台)– transfer to other line: cost after Si,j is ti,j, j= 1, . . ., n– 1(变换到另一装配线,耗时ti,j )
装配线排程(Assembly Line Scheduling) Problem: what stations should be chosen from line 1 and wh
ich from line 2 in order to minimize the total time through the factory for one car?(如何充分利用两条装配线,使得组装一辆汽车的时间最短?)
7
8
解决方法之一(One Solution) Brute force(蛮力法)– Enumerate all possibilities of selecting stations (计算装配线排程所有可能的组合情况)– Compute how long it takes in each case and choose the best one (比较并选择出最短时间的组合)
1.构建最优解(Structure of the Optimal Solution) Let’s consider all possible ways to get from the starting point through station S1,j (考虑所有从起点到达S1,j可能途径) Through S1, j - 1, then directly to S1, j (从S1, j - 1直接到S1, j ) Through S2, j - 1, then transfer over to S1, j (从S2, j - 1转换到S1, j ) S1,j-1 a1,j-1 t2,j-1 a2,j-19
– We have two choices of how to get to S1, j:(两种可能)
Problem:
1
2
3
4
n
1
0
0
1
1 1 if choosing line 1 at step j (= n)(反之标记为1)
0 if choosing line 2 at step j (= 3)第j步由第2条装配线执行，标记为0
S1,j a1,j
– There are 2n possible ways to choose stations(共有2n排程方法)– Infeasible when n is large(如果n很大,蛮力法计算将不可接受)
S2,j-1
10
1.构建最优解(Structure of the Optimal Solution) Suppose that the fastest way through S1, j is through S1, j– 1 (如果到达S1, j的最快装配路线来自S1, j– 1)– We must have taken a fastest way from entry through S1, j– 1(那么必须是从装配线起点经过S1, j– 1的最快装配路线)– If there were a faster way through S1, j - 1, we would use it instead(因为如果存在更快的经过S1, j - 1的装配路线，则可用之替换) Similarly for S2, j– 1(如果经过S1, j的最快装配路线来自S1, j– 1,同样分析)S1,j-1 S1,j a1,j-1 t2,j-1 a2,j-1 S2,j-111
最优化解的结构(Optimal Substructure) Generalization: an optimal solution to the problem find the fastest way through S1, j contains within it an optimal solution to subproblems: find the fastest way through S1, j - 1 or S2, j - 1.(寻求从起点到达S1, j最快装配路线，可分解为寻求从起点经过S1, j - 1 or S2, j - 1最快装配路线问题) This is referred to as the optimal substructure property(我们将这种具有分解递归特征的解的形式称为最优化结构特征) We use this property to construct an optimal solution to a problem from optimal solutions to subproblems(利用这种优化构造特征，从子问题的最优化解获得整个问题的最优化的解)
a1,j
12
华中科技大学管理学院
