有关算法的实现和实用化 Assembly line scheduling ■ Strassen算法实现注意事项: 如何一般化? ■递归到什么程度? ■接口如何设计 接口说明书内容是什么 ■如何针对接口进行编程和编程测试 I A manufacturing problem, See p 325 for detail Problem analysis a For the above assembly_problem, please find Optimal solutions and optimal structural he fastest way to complete the work for any Optimal problems and its optimal sub- ven assembly work instance a What is a problem? 2 Afastest way from start to any station a What is an instance 3 a fastest way from any one to other station Space of sub-problems 清华太学未证想 Mathematical model of the Solution Solution: A way from start to the er a How to express a solution? a Sub-problem solution: a way from start to a a We use a string A=<a, az, a>to middle station solution, where a, belongs to (1, 2)means the ih station in line 1 or line 23 清华大学 宋斌恒 13 有关算法的实现和实用化 n Strassen算法实现注意事项： n 如何一般化？ n 递归到什么程度？ n 接口如何设计？ n 接口说明书内容是什么？ n 异常如何处理 n 如何针对接口进行编程和编程测试。 清华大学 宋斌恒 14 Assembly line scheduling n A manufacturing problem, See p.325 for detail. a1,1 a1,2 a1,3 a1,n a2,1 t2,1 a2,2 t1,1 a2,3 a2,n t2,2 t1,2 Start e2 e1 x2 x1 end Station1,1 Station1,2 Station1,3 Station1,n Station2,1 Station2,2 Station2,3 Station2,n 清华大学 宋斌恒 15 Problem n For the above assembly problem, please find the fastest way to complete the work for any given assembly work instance. n Thinking … … n What is a problem? n What is an instance ? 清华大学 宋斌恒 16 Analysis: n Optimal solutions and optimal structural. n Optimal problems and its optimal sub￾problems: 1. A fastest way from start to end 2. A fastest way from start to any station 3. A fastest way from any one to other station n ? Space of sub-problems 清华大学 宋斌恒 17 Solution n Solution: A way from start to the end n Sub-problem solution: a way from start to a middle station 清华大学 宋斌恒 18 Mathematical Model of the solution n How to express a solution? n We use a string A= <a1 ,a2 ,… ,an> to express a solution, where ai belongs to {1,2} means the i th station in line 1 or line 2