首页
登录
从业资格
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(Sij,i=1或
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(Sij,i=1或
免费题库
2022-08-02
37
问题
某汽车加工工厂有两条装配线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
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在信息管理中,哪些是信息进行加工处理的最基本方式:__()__①变化、排序、核
某汽车租赁公司建立汽车租赁管理系统,其数据库的部分关系模式如下: 用户:US
某工厂的信息管理数据库的部分关系模式如下所示:职工(职工号,姓名,年龄,月工资,
某工厂的仓库管理数据库的部分关系模式如下所示:仓库(仓库号,面积,负责人,电话)
在异步通信中,每个字符包含1位起始位、7位数据位和2位终止位,若每秒钟传送500
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
随机试题
Poetrygoestothebackwatertorefreshitselfasoftenasitgoestothema
--Hehardlyhasanythingnowadays,____?
根据《生产安全事故报告和调查处理条例》,下列不属于事故调查报告应包括的内容的是(
用白盒测试技术对下面流程图进行测试,设计的测试用例如下表所示。至少采用测试用例(
根据《中华人民共和国招投标法》,以下做法正确的是()。A.某项目于3月18日
患者女,45岁。患有拇指狭窄性腱鞘炎2周,最好的治疗方法是A.腱鞘切开术 B
产后子宫恢复至孕前大小是在A、产后1周 B、产后10天 C、产后15天 D
完形-----顿悟说认为完形是一种{},是对事物关系的认知。
下列可激活补体旁路途径的物质是( )。A.MBL B.C-反应蛋白 C.抗
女性,55岁,右耳垂下无痛性肿块逐渐缓慢长大6年。触诊肿块界限清楚,活动,约4c
最新回复
(
0
)