2. 从业资格
  3. 某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n（Sij，i=1或

某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n（Sij，i=1或

免费题库2022-08-02  39
问题 某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n（Sij，i=1或2，j=1，2，…，n），两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同（aij，i=1或2，j=1，2，…，n）。汽车底盘开始到进入两条装配线的时间（e1，e2）以及装配后到结束的时间（X1X2）也可能不相同。从一个工位加工后流到下一个工位需要迁移时间（tij，i=1或2，j=2，…n）。现在要以最快的时间完成一辆汽车的装配，求最优的装配路线。分析该问题，发现问题具有最优子结构。以L1为例，除了第一个工位之外，经过第j个工位的最短时间包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，如式（1）。装配后到结束的最短时间包含离开L1的最短时间或者离开L2的最短时间如式（2）。若j=1其他（1）（2）由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，该问题具有重复子问题的性质，故采用迭代方法求解。该问题采用的算法设计策略是（　　），算法的时间复杂度为（　　）以下是一个装配调度实例，其最短的装配时间为（　　），装配路线为（　　）问题1选项A.分治B.动态规划C.贪心D.回溯问题2选项A.Θ(lgn)B.Θ(n)C.Θ(n2)D.Θ(nlgn)问题3选项A.21B.23C.20D.26问题4选项A.S11→S12→S13B.S11→S22→S13C.S21→S12→S23D.S21→S22→S23
选项
答案 BBAB
解析 本题考查算法基础。
题目看似是非常复杂的，涉及到复杂的公式，以及算法逻辑，但如果我们先从后面两个空来分析，问题就简单得多。
求最短装配时间与装配路线，其实是一个求最短路径的过程。此时我们可以把从起点到各个结点的最短路径逐步求出。经过分析得出最短装配路线为：S11→S22→S13，长度为21。
解决了一个实际问题后，再来看所谓的迭代公式，其做法与之前手动求最短路径一致，算法是用一个数组将起点到各个结点的最短路径逐个求出，用已求出的最短路径来分析后面的最短路径，所以这符合动态规划法的特征，算法策略应是动态规划法。而算法的复杂度为Θ(n)，因为用一个单重循环就可以解决这个问题。
转载请注明原文地址:https://tihaiku.com/congyezige/2410399.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)